Глава 18. Классы-контейнеры________________________________485

зона. В версии copy первые resuit_last - result_first упорядоченных элементов из диапазона [first, last) копируются в целевой диапазон

[result_first, result_last). Если величина last - first меньше, чем result_last - resuit_first, то только last - first упорядоченных элементов КОПИРУЮТСЯ В Диапазон [result_first, result_first + (last-first)). В

версии с копированием возвращается указатель на следующий элемент за последним из целевого диапазона.

template <class RandomAccessIterator> void partial_sort (RandomAccessIterator first,

RandomAccessIterator middle,

RandomAccessIterator last) ;

template <class RandomAccessIterator, class Compare>

void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp); .

template <class Input Iterator,class RandomAccessIterator> RandomAccessIterator partial sort_copy (Inputlterator first,

Inputlterator last,

RandomAccessIterator result_first,

RandomAccessIterator result_last) ;

template <class Inputlterator,class RandomAccessIterator,

class Compare> RandomAccessIterator partial_sort_copy (Inputlterator first,

Inputlterator last,

RandomAccessIterator result first,

RandomAccessIterator result last,

Compare comp) ;

nth_element. Алгоритм nth_element (п-й элемент) помещает в п-й позиции входной последовательности элемент, который должен был бы стоять на этом месте в упорядоченной последовательности. Кроме того, вся последовательность разбита на две части вокруг этого элемента таким образом, что перед ним находятся элементы меньше его, а за ним — все элементы большие или равные ему. Этот алгоритм — простой способ нахождения медианы последовательности.

template <class RandomAccessIterator> void nth_eiement (RandomAccessIterator first,

RandomAccessIterator nth, '

RandomAccessIterator last);

template <class RandomA-ccessIterator, class Compare>

void nth_eleitient (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last. Compare comp);