2163. nth_element requires inconsistent post-conditions

Section: 26.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.

1. Change 26.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.