Для использования любого обобщенного алгоритма необходимо включить в программу заголовочный файл
#include algorithm
А для любого из четырех численных алгоритмов – adjacent_differences(), accumulate(), inner_product() и partial_sum() – включить также заголовок
#include numeric
Все существующие алгоритмы для удобства изложения распределены нами на девять категорий (они перечислены ниже). В Приложении алгоритмы рассматриваются в алфавитном порядке, и для каждого приводится пример применения.
12.5.1. Алгоритмы поиска
Тринадцать алгоритмов поиска предоставляют различные способы нахождения определенного значения в контейнере. Три алгоритма equal_range(), lower_bound() и upper_bound() выполняют ту или иную форму двоичного поиска. Они показывают, в какое место контейнера можно вставить новое значение, не нарушая порядка сортировки.
adjacent_find(), binary_search(), count(),count_if(), equal_range(),
find(), find_end(), find_first_of(), find_if(), lower_bound(),
upper_bound(), search(), search_n()
12.5.2. Алгоритмы сортировки и упорядочения
Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения элементов контейнера. Разбиение (partition) – это разделение элементов контейнера на две группы: удовлетворяющие и не удовлетворяющие некоторому условию. Так, можно разбить контейнер по признаку четности/нечетности чисел или в зависимости от того, начинается слово с заглавной или со строчной буквы. Устойчивый (stable) алгоритм сохраняет относительный порядок элементов с одинаковыми значениями или удовлетворяющих одному и тому же условию. Например, если дана последовательность:
{ "pshew", "honey", "Tigger", "Pooh" }
то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале слова генерирует последовательность, в которой относительный порядок слов в каждой категории сохранен:
{ "Tigger", "Pooh", "pshew", "honey" }
При использовании неустойчивой версии алгоритма сохранение порядка не гарантируется. (Отметим, что алгоритмы сортировки нельзя применять к списку и ассоциативным контейнерам, таким, как множество (set) или отображение (map).)
inplace_merge(), merge(), nth_element(), partial_sort(),
partial_sort_copy(), partition(), random_shuffle(), reverse(),
reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),
stable_partition()
12.5.3. Алгоритмы удаления и подстановки
Рассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шесть различных перестановок: abc, acb, bac, bca, cab и cba, лексикографически упорядоченных на основе оператора “меньше”. Таким образом, abc – это первая перестановка, потому что каждый элемент меньше последующего. Следующая перестановка – acb, поскольку в начале все еще находится a – наименьший элемент последовательности. Соответственно перестановки, начинающиеся с b, предшествуют тем, которые начинаются с с. Из bac и bca меньшей является bac, так как последовательность ac лексикографически меньше, чем ca. Если дана перестановка bca, то можно сказать, что предшествующей для нее будет bac, а последующей – cab. Для перестановки abc нет предшествующей, а для cba – последующей.
next_permutation(), prev_permutation()
12.5.4. Алгоритмы перестановки
Рассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шесть различных перестановок: abc, acb, bac, bca, cab и cba, лексикографически упорядоченных на основе оператора “меньше”. Таким образом, abc – это первая перестановка, потому что каждый элемент меньше последующего. Следующая перестановка – acb, поскольку в начале все еще находится a – наименьший элемент последовательности. Соответственно перестановки, начинающиеся с b, предшествуют тем, которые начинаются с с. Из bac и bca меньшей является bac, так как последовательность ac лексикографически меньше, чем ca. Если дана перестановка bca, то можно сказать, что предшествующей для нее будет bac, а последующей – cab. Для перестановки abc нет предшествующей, а для cba – последующей.
next_permutation(), prev_permutation()