Глава 14. Алгоритмы

357

cout « endl; return 0;

} Результат работы программы:

24 -91 -5 5 -15 -1 -10 3-2 4

unique, unique_copy

Алгоритм unique выполняет удаление из последовательности соседних элементов, равных друг другу или удовлетворяющих критерию, заданному с помощью бинарного предиката pred. Размер последовательности при этом не изменяется¹. Алгоритм возвращает итератор на новый логический конец данных.

tempiate<class For>

For unique(For first, For last); tempiate<class For, class BinPred>

For unique(For first, For last, BinPred pred);

Алгоритм unique_copy выполняет те же действия с копией последовательности:

tempiate<class In, class Out>

Out unique_copy(In first, In last, Out result); tempiate<class In, class Out, class BinPred>

Out unique_copy(In first. In last, Out result. BinPred pred);

Алгоритмы, связанные с сортировкой

Алгоритмы этой категории упорядочивают последовательности, выполняют поиск элементов, слияние последовательностей, поиск минимума и максимума, лексикографическое сравнение, перестановки и т. п.

Таблица 14.3. Алгоритмы, связанные с сортировкой

Алгоритм	Выполняемая функция
binary_search	Поиск заданного значения
equal_range	Нахождение последовательности элементов с заданным значением
inplacejnerge	Слияние отсортированных последовательностей одного диапазона
Iexi cographi cal_compare	Лексикографически первая из двух последовательностей
lower_bound	Нахождение первого вхождения заданного значения

продолжение J

¹ Для списков предпочтительнее пользоваться одноименным методом класса list.

358

Часть III. Стандартная библиотека

Таблица 14.3 (продолжение)

Алгоритм	Выполняемая функция
max	Большее из двух значений
rnax_element	Наибольшее значение в последовательности
merge	Слияние отсортированных последовательностей
min	Меньшее из двух значений
rnin element	Наименьшее значение в последовательности
next_permutation	Следующая перестановка в лексикографическом порядке
nth_element	Помещение n-го элемента на заданное место
partial_sort	Частичная сортировка
partial_sort_copy	Частичная сортировка с копированием
partition	Перемещение вперед элементов, удовлетворяющих условию
prev_permutation	Предыдущая перестановка в лексикографическом порядке
sort	Сортировка
stable_partition	Перемещение вперед элементов, удовлетворяющих условию, с сохранением их относительного порядка
stable_sort	Сортировка, сохраняющая порядок для одинаковых элементов
upper_bound	Нахождение первого элемента, большего, чем заданное значение

Рассмотрим эти алгоритмы подробнее. Для каждого из алгоритмов существует две формы: одна использует операцию <, а другая — функцию сравнения, заданную пользователем. Обратите внимание на то, что многим алгоритмам требуются итераторы произвольного доступа.

binary_search

Алгоритм binary_search выполняет поиск значения value в отсортированной последовательности, заданной итераторами first и last. Возвращается только факт, найдено искомое значение или нет. Двоичным поиск называется потому, что выполняется путем последовательного деления интервала пополам («как поймать льва в пустыне»).

tempiate<class For, class T>

bool binary_search(For first. For last, const T& value); tempiate<class For, class T, class Compare> bool binary_search(For first. For last. const T& value. Compare comp);