This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.
Section: 28.7.8 [alg.min.max] Status: CD1 Submitter: Matt Austern Opened: 2007-08-30 Last modified: 2017-02-03
Priority: Not Prioritized
View all other issues in [alg.min.max].
View all issues with CD1 status.
The complexity for minmax_element (28.7.8 [alg.min.max] par 16) says "At most max(2 * (last - first ) - 2, 0) applications of the corresponding comparisons", i.e. the worst case complexity is no better than calling min_element and max_element separately. This is gratuitously inefficient. There is a well known technique that does better: see section 9.1 of CLRS (Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein).
Change 28.7.8 [alg.min.max] to:
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);
Returns: make_pair(m, M), where m is
min_element(first, last) or min_element(first, last, comp)and M is max_element(first, last) or max_element(first, last, comp).
Complexity: At most
max(2 * (last - first ) - 2, 0)applications of the corresponding comparisons.