This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++14 status.
Section: 27.8.3 [alg.nth.element] Status: C++14 Submitter: Peter Sommerlad Opened: 2012-07-06 Last modified: 2016-01-28
Priority: Not Prioritized
View all other issues in [alg.nth.element].
View all issues with C++14 status.
Discussion:
The specification of nth_element refers to operator< whereas all sorting without a compare function is based on operator<. While it is true that for all regular types both operators should be defined accordingly, all other sorting algorithms only rely on existence of operator<. So I guess the paragraph p1
After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Also for any iterator i in the range [first,nth) and any iterator j in the range [nth,last) it holds that: !(*i > *j) or comp(*j, *i) == false.
should read
After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Also for any iterator i in the range [first,nth) and any iterator j in the range [nth,last) it holds that: !(*j < *i) or comp(*j, *i) == false.
Note only "!(*i > *j)" was changed to "!(*j < *i)" and it would be more symmetric with comp(*j, *i) as well.
In theory this might be a semantic change to the spec, but I believe the mistake is unintended.[ 2012-10 Portland: Move to Ready ]
This is clearly correct by inspection, moved to Ready by unanimous consent.
[2013-04-20 Bristol]
Proposed resolution:
This wording is relative to N3376.
Change 27.8.3 [alg.nth.element] p1 as indicated:
template<class RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);-1- After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted. Also for any iterator i in the range [first,nth) and any iterator j in the range [nth,last) it holds that:
!(*i > *j)!(*j < *i) or comp(*j, *i) == false.