Component type: function
Prototype Nth_element is an overloaded name; there are actually two nth_element functions.
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering comp);
Description Nth_element is similar to partial_sort, in that it partially orders a range of elements: it arranges the range [first, last) such that the element pointed to by the iterator nth is the same as the element that would be in that position if the entire range [first, last) had been sorted. Additionally, none of the elements in the range [nth, last) is less than any of the elements in the range [first, nth) . [1]
The two versions of nth_element differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp.
The postcondition for the first version of nth_element is as follows. There exists no iterator i in the range [first, nth) such that *nth < *i, and there exists no iterator j in the range [nth + 1, last) such that *j < *nth.
The postcondition for the second version of nth_element is as follows. There exists no iterator i in the range [first, nth) such that comp(*nth, *i) is true, and there exists no iterator j in the range [nth + 1, last) such that comp(*j, *nth) is true.
Definition Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
Requirements on types For the first version, the one that takes three arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• RandomAccessIterator's value type is LessThan Comparable.
• The ordering relation on RandomAccessIterator's value type is a strict weak ordering, as defined in the LessThan Comparable requirements.
For the second version, the one that takes four arguments:
• RandomAccessIterator is a model of Random Access Iterator.
• RandomAccessIterator is mutable.
• StrictWeakOrdering is a model of Strict Weak Ordering.
• RandomAccessIterator's value type is convertible to StrictWeakOrdering's argument type.
Preconditions • [first, nth) is a valid range.
• [nth, last) is a valid range. (It follows from these two conditions that [first, last) is a valid range.)
Complexity On average, linear in last – first. [2]
Example int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
nth_element(A, A + 6, A + N);
copy(A, A + N, ostream_iterator<int>(cout, ' '));
// The printed result is '5 2 6 1 4 3 7 8 9 10 11 12'.
Notes [1] The way in which this differs from partial_sort is that neither the range [first, nth) nor the range [nth, last) is be sorted: it is simply guaranteed that none of the elements in [nth, last) is less than any of the elements in [first, nth). In that sense, nth_element is more similar to partition than to sort. Nth_element does less work than partial_sort, so, reasonably enough, it is faster. That's the main reason to use nth_element instead of partial_sort.
[2] Note that this is significantly less than the run-time complexity of partial_sort.
See also partial_sort, partition, sort, StrictWeakOrdering, LessThan Comparable
