c++ STL min_element

Question

I want to find the minimum element in an array, but if the minimum element appears more than once, then I want the last occurrence of the element. I used std::min_element() with my comp() function.

vector<int>::iterator it=min_element(input.begin(), input.end(),comp); cout << *it << endl; cout << distance(input.begin(), it); bool comp(int a, int b) { if (a <= b) return true; else return false; }

This code is giving an error saying invalid comparator on input 3 3 4.

Just apply min_element over reverse iterators; you'll get last occurrence for free. — Igor Tandetnik
– Igor Tandetnik, Commented Dec 30, 2018 at 16:20
comp does not satisfy the requirements of a strict weak ordering. Your program therefore exhibits undefined behavior. — Igor Tandetnik
– Igor Tandetnik, Commented Dec 30, 2018 at 16:21
if (a <= b) -- std::min_element wants to know if a < b, not if a <= b. Your code answers the wrong question. — PaulMcKenzie
– PaulMcKenzie, Commented Dec 30, 2018 at 16:25
@PaulMcKenzie looking into possible implementations it should actually work, but it does not satisfy Compare requirement. Interesting question was it a good idea to put this requirement for comparator in this case — Slava
– Slava, Commented Dec 30, 2018 at 16:37
@Slava "looking into possible implementations it should actually work" Dangerous thinking. Just the other week I had to dispel this when someone thought a broken comparator should be fine due to how they would personally implement stable_sort! Naturally it was crashing. Always code to the contract, period! — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Dec 30, 2018 at 16:45

Lightness Races in Orbit · Accepted Answer · 2018-12-30 16:47:07Z

3

Give min_element reverse iterators instead:

vector<int>::reverse_iterator it=min_element(input.rbegin(), input.rend(),comp);

Then convert it back to a "normal" iterator iff you need to.

And don't forget to correct your comparator; it needs to be < not <=.

answered Dec 30, 2018 at 16:47

Lightness Races in Orbit

387k77 gold badges670 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lightness Races in Orbit Over a year ago

@RohitPandit Because that is not the meaning that is expected of your comparator. It can't just do "anything" it needs to do what the standard expects.

Jarod42 · Accepted Answer · 2018-12-30 21:31:39Z

You might abuse of std::minmax_element which returns the last biggest element contrary to std::max_element:

auto last_min_it = std::minmax_element(input.begin(), input.end(), std::greater<>{}).second;

I would probably use reverse iterator with std::min_element, though:

auto min_rev_it = std::min_element(input.rbegin(), input.rend());

Ilio Catallo · Accepted Answer · 2018-12-30 19:24:12Z

If your data are stored in a vector, then the use of a reverse iterator should suffice, as already suggested.

More generally, the Standard Library does not provide a min_element_last function, as also commented in 1. In this respect, a possible implementation of min_element_last may read:

template <typename I> using ValueType = typename std::iterator_traits<I>::value_type; template <typename I, typename R> // I models ForwardIterator // R models StrictWeakOrdering on ValueType<I> I min_element_last(I first, I last, R cmp) { if (first == last) return last; I curr = first; ++first; while (first != last) { if (!cmp(*curr, *first)) { curr = first; } ++first; } return curr; } template <typename I> // I models ForwardIterator // ValueType<I> models TotallyOrdered I min_element_last(I first, I last) { using T = ValueType<I>; return min_element_last(first, last, std::less<T>()); }

The advantage would be the possibility of using min_element_last also with iterators that only model the ForwardIterator concept.

Collectives™ on Stack Overflow

c++ STL min_element

3 Answers 3

1 Comment

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Linked

Related