 

Category: algorithms   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 functors 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 backwardcompatibility header algo.h.
Requirements on types
For the first version, the one that takes three arguments:

RandomAccessIterator
is a model of RandomAccessIterator.

RandomAccessIterator
is mutable.

RandomAccessIterator
's value type is LessThanComparable.

The ordering relation on
RandomAccessIterator
's value type is a strict weak ordering, as defined in the LessThanComparable requirements.
For the second version, the one that takes four arguments:

RandomAccessIterator
is a model of RandomAccessIterator.

RandomAccessIterator
is mutable.

StrictWeakOrdering
is a model of StrictWeakOrdering.

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, " "));
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 runtime complexity of partial_sort
.
See also
partial_sort
, partition
, sort
, StrictWeakOrdering, LessThanComparable