nth_element

nth_element

template<class RanIt>
    void nth_element(RanIt first, RanIt nth, RanIt last);
template<class RanIt, class Pred>
    void nth_element(RanIt first, RanIt nth, RanIt last, Pred pr);

The first template function reorders the sequence designated by iterators in the range [first, last) such that for each N in the range [0, nth - first) and for each M in the range [nth - first, last - first), the predicate !(*(first + M) < *(first + N)) is true. Moreover, for N equal to nth - first and for each M in the range (nth - first, last - first) the predicate !(*(first + M) < *(first + N)) is true. Thus, if nth != last, the element *nth is in its proper position if elements of the entire sequence were sorted in ascending order, ordered byoperator<. Any elements before this one belong before it in the sort sequence, and any elements following it belong after it.

The function evaluates the ordering predicate X < Y a number of times proportional to last - first, on average.

The second template function behaves the same, except that it replaces operator<(X, Y) with pr(X, Y).

Sample programs: nth_element and nth_element (predicate version).