C++ In a Nutshell

Name

nth_element function template — Reorders a range to properly place an item at the nth position

Synopsis

template<typename RandIter>
  void nth_element(RandIter first, RandIter nth, RandIter last);
template<typename RandIter, typename Compare>
  void nth_element(RandIter first, RandIter nth, RandIter last, Compare comp);

The nth_element function template reorders the range [first, last) so that *nth is assigned the value that would be there if the entire range were sorted. It also partitions the range so that all elements in the range [first, nth) are less than or equal to the elements in the range [nth, last).

The order is not stable—that is, if there are multiple elements that could be moved to position nth and preserve the sorted order, you cannot predict which element will be moved to that position.

Figure 13-10 illustrates how the nth_element function template works.

Figure 13-10. Reordering a range with nth_element

Technical Notes

Precondition: nth is in the range [first, last).

Postcondition: *i < *nth for all i in [first, nth), !(*j < *nth) for all j in [nth, last), and !(*k < *nth) for all k in [nth + 1, last).

Complexity is linear for the average case but is allowed to perform worse in the worst case.

See Also

partition function template, partial_sort function template, sort function template