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);

1
#

Requires: RandomAccessIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.

2
#

Effects: После nth_­element элемента в позиции, на которую указывает, nth находится элемент, который был бы в этой позиции, если бы весь диапазон был отсортирован, если только nth == last. Также для каждого итератора i в диапазоне [first, nth) и каждого итератора j в диапазоне [nth, last) он содержит: !(*j < *i) или comp(*j, *i) == false.

3
#

Complexity: Для перегрузок нет ExecutionPolicy, в среднем линейная. Для перегруженных с ExecutionPolicy, O(N) применения предиката, и O(NlogN) свопы, где N=last - first.