11 Algorithms library [algorithms]

11.5 Sorting and related operations [alg.sorting]

11.5.2 Nth element [alg.nth.element]

template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>, class Proj = identity> requires Sortable<I, Comp, Proj> I nth_element(I first, I nth, S last, Comp comp = Comp{}, Proj proj = Proj{}); template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity> requires Sortable<iterator_t<Rng>, Comp, Proj> safe_iterator_t<Rng> nth_element(Rng&& rng, iterator_t<Rng> nth, Comp comp = Comp{}, Proj proj = Proj{});

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, unless nth == last. Also for every iterator i in the range [first,nth) and every iterator j in the range [nth,last) it holds that: invoke(comp, invoke(proj, *j), invoke(proj, *i)) == false.

Returns: last.

Complexity: Linear on average.