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.

2339. Wording issue in nth_element

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