Issue 2325: minmax_element()'s behavior differing from max

2325. `minmax_element()`'s behavior differing from `max_element()`'s should be noted

Section: 26.8.9 [alg.min.max] Status: C++17 Submitter: Stephan T. Lavavej Opened: 2013-09-21 Last modified: 2017-07-30

Priority: 3

View other active issues in [alg.min.max].

View all other issues in [alg.min.max].

View all issues with C++17 status.

Discussion:

26.8.9 [alg.min.max]/23 says that max_element() finds the first biggest element, while /25 says that minmax_element() finds the last biggest element. This significant difference is unusual — it means that minmax_element(args) is not equivalent to make_pair(min_element(args), max_element(args)), whereas the other major "two for one" algorithm equal_range(args) is equivalent to make_pair(lower_bound(args), upper_bound(args)). minmax_element()'s behavior is intentional — it is a fundamental consequence of the 3N/2 algorithm — but the Standardese does not draw attention to this in any way. This wording came from LWG 715's resolution (which changed the semantics but didn't mention it), citing CLRS for the algorithm — but CLRS doesn't mention the behavior for equivalent elements! The wording here deeply confused me (as an STL maintainer fixing an incorrect implementation) until I walked through the algorithm by hand and figured out the fundamental reason. It would be really nice for the Standard to provide a hint that something magical is happening here.

[2014-06-06 Library reflector vote]

The issue has been identified as Tentatively Ready based on six votes in favour.

Proposed resolution:

This wording is relative to N3691.

Add a footnote to 26.8.9 [alg.min.max]/25 as indicated:
```
template<class ForwardIterator>
  pair<ForwardIterator, ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class Compare>
  pair<ForwardIterator, ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
```
-25- Returns: make_pair(first, first) if [first,last) is empty, otherwise make_pair(m, M), where m is the first iterator in [first,last) such that no iterator in the range refers to a smaller element, and where M is the last iterator [Footnote: This behavior intentionally differs from max_element().] in [first,last) such that no iterator in the range refers to a larger element.

2325. minmax_element()'s behavior differing from max_element()'s should be noted

2325. `minmax_element()`'s behavior differing from `max_element()`'s should be noted