2339. Wording issue in nth_element

Section: 26.8.3 [alg.nth.element] Status: C++14 Submitter: Christopher Jefferson Opened: 2013-10-19 Last modified: 2017-07-05

Priority: 0

View all other issues in [alg.nth.element].

View all issues with C++14 status.

Discussion:

The wording of nth_element says: 

template<class RandomAccessIterator>
  void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                   RandomAccessIterator last);

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 every iterator i in the range [first,nth) and every iterator j in the range [nth,last) it holds that: !(*j < *i) or comp(*j, *i) == false.

That wording, to me, implies that there must be an element at 'nth'. However, gcc at least accepts nth == last, and returns without effect (which seems like the sensible option).

Is it intended to accept nth == last? If so, then I would suggest adding this to the wording explicitly, say:

After nth_element the element in the position pointed to by nth, if any, is the element that would be in that position if the whole range were sorted. Also for every iterator i in the range [first,nth) and every iterator j in the range [nth,last) it holds that: !(*j < *i) or comp(*j, *i) == false.

[Issaquah 2014-02-11: Move to Immediate]

Proposed resolution:

This wording is relative to N3797.

  1. Modify 26.8.3 [alg.nth.element]/1 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, unless nth == last. Also for every iterator i in the range [first,nth) and every iterator j in the range [nth,last) it holds that: !(*j < *i) or comp(*j, *i) == false.