CODEWITHSUNDEEP
c++stl
updogliu
updogliu

Reputation: 6255

What the effect of std::nth_element(a.begin(), a.end(), a.end())?

I read the description of std::nth_element at http://www.sgi.com/tech/stl/nth_element.html

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

Note that the preconditions are

  1. [first, nth) is a valid range.
  2. [nth, last) is a valid range.

My question is:

Is it valid to call std::nth_element(a.begin(), a.end(), a.end())? If so, what's its effect? It doesn't violate the preconditions above, anyway. Anywhere in the language standard (or other documents) stated that nth must be pointing to an element in a?

Upvotes: 8

Views: 559

Answers (3)

Andreas Brinck
Andreas Brinck

Reputation: 52519

It's valid and is probably, but not guaranteed by the standard, a null operation. With the given data, the two preconditions become:

[a.begin(), a.end()) is a valid range.
[a.end(), a.end()) is a valid range.

Which are both true, the second interval is empty though. From the standard 25.3.2/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) or comp(*j, *i) == false.

If the whole range was sorted the original a.end() would be at a.end() and for the second part the range [nth, last) is empty so there are no elements for which to evaluate the !(*i > *j) and comp(*j, *i) == false conditions.

Upvotes: 6

Dmitry Egorenkov
Dmitry Egorenkov

Reputation: 1055

No, it is not valid because nth has to be within the range [first, last).

Upvotes: 0

Frerich Raabe
Frerich Raabe

Reputation: 94299

No, std::nth_element(a.begin(), a.end(), a.end()) is not valid - it violates the second precondition, which requires that the nth iterator (the second argument) points to a valid element. a.end() doesn't point to a valid element though.

Upvotes: 0

Related Questions