### 2163. `nth_element` requires inconsistent post-conditions

**Section:** 27.8.3 [alg.nth.element] **Status:** C++14
**Submitter:** Peter Sommerlad **Opened:** 2012-07-06 **Last modified:** 2016-01-28 10:19:27 UTC

**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`.