28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.2 Nth element [alg.nth.element]

template<class RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator> void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> void nth_element(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable.
The type of *first shall satisfy the requirements of MoveConstructible and of MoveAssignable.
Effects: 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: !(*j < *i) or comp(*j, *i) == false.
Complexity: For the overloads with no ExecutionPolicy, linear on average.
For the overloads with an ExecutionPolicy, applications of the predicate, and swaps, where .