Difference in the behavior of max_element and minmax_element in C ++ STL

Question

In C ++ max_element , if there are several elements that are maximal, it returns the first such element. While minmax_element (C ++ 11) returns the last max element.

Is there a reason for standards for this behavior?

From cplusplus.com

If more than one equivalent element has the highest value, the second iterator points to the last of these elements.

The comparison is performed using any operator <for the first version, or for the second; An element is the largest if no other element is compared with it less. If more than one element satisfies this condition, the iterator returns points to the first of such elements.

Answer 1

Documentation for increasing their library includes rationale

The definition problem arises when you try to create minmax_element using the procedure suggested in (Cormen, Leiserson, Rivest: "Introduction to Algorithms", section 9.1). It should be possible to derive an algorithm using only 3n / 2 comparisons if [first, last] has n elements, but if you try to write the function first_min_first_max_element (), which returns both std :: min_element and std :: max_element in a pair, trivial implementation does not work. The problem, quite subtly, is related to equal elements: I had to think for a while to find a way to make only three comparisons per pair and return the first minimum and first maximum elements. For a long time, it seemed that any attempt to do this would consume four comparisons per pair in the worst case. This implementation reaches three.

It is not possible (or even desirable) to change the value of max_element, but it is still useful to provide a minmax_element function that returns a pair of min_element and max_element. Although it is simple enough to call min_element and max_element, this performs 2 (n-1) comparisons and requires two passes above the input. In contrast, minmax_element will perform fewer comparisons and perform one pass over the input. The savings can be significant when the type of the iterator is not a source pointer or even just a model of the InputIterator concept (although in this case the interface must be changed, since the type of the return value cannot be copied, so it would be possible to return a value, for example).