Библиотека алгоритмов

Библиотека алгоритмов определяет функции для различных целей (например, поиск, сортировка, подсчёт, обработка), работающие с диапазонами элементов.

Ограниченные алгоритмы (начиная с C++20)

C++20 предоставляет ограниченные версии большинства алгоритмов в пространстве имён std::ranges. В этих алгоритмах диапазон можно задать либо парой итератор–сентинел, либо одним аргументом range; также поддерживаются проекции и вызываемые объекты — указатели на члены. Кроме того, типы возвращаемых значений большинства алгоритмов изменены так, чтобы возвращать всю потенциально полезную информацию, вычисленную во время выполнения алгоритма.

std::vector<int> v{7, 1, 4, 0, -1};
std::ranges::sort(v); // constrained algorithm

Параллельные алгоритмы (начиная с C++17)

Параллельный алгоритм — это шаблон функции из библиотеки алгоритмов с параметром шаблона с именем ExecutionPolicy или ограниченный понятием execution-policy (начиная с C++26). Такой параметр шаблона называется параметром шаблона политики выполнения ; он описывает способ, которым выполнение параллельного алгоритма может быть распараллелено.

Если не указано иное, параллельным алгоритмам разрешается создавать произвольное количество копий элементов диапазонов при условии, что и std::is_trivially_copy_constructible_v<T>, и std::is_trivially_destructible_v<T> являются true, где T — тип элементов.

Политики выполнения

Алгоритмы стандартной библиотеки поддерживают несколько политик выполнения, а библиотека предоставляет соответствующие типы и объекты политик выполнения. Пользователи могут статически выбрать политику выполнения, вызвав параллельный алгоритм с объектом политики выполнения соответствующего типа.

Реализации стандартной библиотеки (но не пользователи) могут определять дополнительные политики выполнения в качестве расширения. Семантика параллельных алгоритмов, вызванных с объектом политики выполнения типа, определяемого реализацией, определяется реализацией.

Определено в заголовке <execution>
Определено в пространстве имён std::execution
sequenced_policyparallel_policyparallel_unsequenced_policyunsequenced_policy (C++17)(C++17)(C++17)(C++20)	типы политик выполнения (класс)
seqparpar_unsequnseq (C++17)(C++17)(C++17)(C++20)	глобальные объекты политик выполнения (константа)
Определено в пространстве имён std
is_execution_policy (C++17)	проверяет, представляет ли класс политику выполнения (шаблон класса)
execution-policy (C++26)	указывает, что тип представляет политику выполнения (понятие только для описания*)

Немодифицирующие операции над последовательностями

Пакетные операции

Определено в заголовке <algorithm>
for_each	применяет унарный функциональный объект к элементам диапазона (шаблон функции и функциональный объект-алгоритм)
ranges::for_each (C++20)
for_each_n (C++17)	применяет функциональный объект к первым N элементам последовательности (шаблон функции и функциональный объект-алгоритм)
ranges::for_each_n (C++20)

Операции поиска

Определено в заголовке <algorithm>
all_ofany_ofnone_of (C++11)(C++11)(C++11)	проверяют, true ли предикат для всех, любого или ни одного из элементов диапазона (шаблон функции и функциональный объект-алгоритм)
ranges::all_ofranges::any_ofranges::none_of (C++20)(C++20)(C++20)
ranges::containsranges::contains_subrange (C++23)(C++23)	проверяют, содержит ли диапазон заданный элемент или поддиапазон (функциональный объект-алгоритм)
findfind_iffind_if_not (C++11)	находят первый элемент, удовлетворяющий заданным критериям (шаблон функции и функциональный объект-алгоритм)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)
ranges::find_lastranges::find_last_ifranges::find_last_if_not (C++23)(C++23)(C++23)	находят последний элемент, удовлетворяющий заданным критериям (функциональный объект-алгоритм)
find_end	находит последнюю последовательность элементов в заданном диапазоне (шаблон функции и функциональный объект-алгоритм)
ranges::find_end (C++20)
find_first_of	ищет любой из элементов заданного набора (шаблон функции и функциональный объект-алгоритм)
ranges::find_first_of (C++20)
adjacent_find	находит первые два соседних элемента, которые равны друг другу (или удовлетворяют заданному предикату) (шаблон функции и функциональный объект-алгоритм)
ranges::adjacent_find (C++20)
countcount_if	возвращают количество элементов, удовлетворяющих заданным критериям (шаблон функции и функциональный объект-алгоритм)
ranges::countranges::count_if (C++20)(C++20)
mismatch	находит первую позицию, в которой два диапазона различаются (шаблон функции и функциональный объект-алгоритм)
ranges::mismatch (C++20)
equal	определяет, совпадают ли два набора элементов (шаблон функции и функциональный объект-алгоритм)
ranges::equal (C++20)
search	ищет первое вхождение последовательности элементов (шаблон функции и функциональный объект-алгоритм)
ranges::search (C++20)
search_n	ищет первое вхождение в диапазоне заданного количества последовательных копий элемента (шаблон функции и функциональный объект-алгоритм)
ranges::search_n (C++20)
ranges::starts_with (C++23)	проверяет, начинается ли диапазон с другого диапазона (функциональный объект-алгоритм)
ranges::ends_with (C++23)	проверяет, заканчивается ли диапазон другим диапазоном (функциональный объект-алгоритм)

Операции свёртки (начиная с C++23)

Определено в заголовке <algorithm>
indirectly-binary-left-foldableindirectly-binary-right-foldable (C++23)(C++23)	указывает, что вызываемый тип можно использовать в алгоритмах свёртки (понятие только для описания*)
ranges::fold_left (C++23)	выполняет свёртку диапазона элементов слева направо (функциональный объект-алгоритм)
ranges::fold_left_first (C++23)	выполняет свёртку диапазона элементов слева направо, используя первый элемент в качестве начального значения (функциональный объект-алгоритм)
ranges::fold_right (C++23)	выполняет свёртку диапазона элементов справа налево (функциональный объект-алгоритм)
ranges::fold_right_last (C++23)	выполняет свёртку диапазона элементов справа налево, используя последний элемент в качестве начального значения (функциональный объект-алгоритм)
ranges::fold_left_with_iter (C++23)	выполняет свёртку диапазона элементов слева направо и возвращает пару (итератор, значение) (функциональный объект-алгоритм)
ranges::fold_left_first_with_iter (C++23)	выполняет свёртку диапазона элементов слева направо, используя первый элемент в качестве начального значения, и возвращает пару (итератор, optional) (функциональный объект-алгоритм)

Модифицирующие операции над последовательностями

Операции копирования

Определено в заголовке <algorithm>
copycopy_if (C++11)	копирует диапазон элементов в новое место (шаблон функции и функциональный объект-алгоритм)
ranges::copyranges::copy_if (C++20)(C++20)
copy_n (C++11)	копирует заданное количество элементов в новое место (шаблон функции и функциональный объект-алгоритм)
ranges::copy_n (C++20)
copy_backward	копирует диапазон элементов в обратном порядке (шаблон функции и функциональный объект-алгоритм)
ranges::copy_backward (C++20)
move (C++11)	перемещает диапазон элементов в новое место (шаблон функции и функциональный объект-алгоритм)
ranges::move (C++20)
move_backward (C++11)	перемещает диапазон элементов в новое место в обратном порядке (шаблон функции и функциональный объект-алгоритм)
ranges::move_backward (C++20)

Операции обмена

Определено в заголовке <algorithm> (до C++11)
Определено в заголовке <utility> (начиная с C++11)
Определено в заголовке <string_view>
swap	обменивает значения двух объектов (шаблон функции)
Определено в заголовке <algorithm>
swap_ranges	обменивает два диапазона элементов (шаблон функции и функциональный объект-алгоритм)
ranges::swap_ranges (C++20)
iter_swap	обменивает элементы, на которые указывают два итератора (шаблон функции)

Операции преобразования

Определено в заголовке <algorithm>
transform	применяет функцию к диапазону элементов, сохраняя результаты в целевом диапазоне (шаблон функции и функциональный объект-алгоритм)
ranges::transform (C++20)
replacereplace_if	заменяет все значения, удовлетворяющие заданным критериям, другим значением (шаблон функции и функциональный объект-алгоритм)
ranges::replaceranges::replace_if (C++20)(C++20)
replace_copyreplace_copy_if	копирует диапазон, заменяя элементы, удовлетворяющие заданным критериям, другим значением (шаблон функции и функциональный объект-алгоритм)
ranges::replace_copyranges::replace_copy_if (C++20)(C++20)

Операции генерации

Определено в заголовке <algorithm>
fill	присваивает заданное значение каждому элементу диапазона посредством копирующего присваивания (шаблон функции и функциональный объект-алгоритм)
ranges::fill (C++20)
fill_n	присваивает заданное значение N элементам диапазона посредством копирующего присваивания (шаблон функции и функциональный объект-алгоритм)
ranges::fill_n (C++20)
generate	присваивает каждому элементу диапазона результаты последовательных вызовов функции (шаблон функции и функциональный объект-алгоритм)
ranges::generate (C++20)
generate_n	присваивает N элементам диапазона результаты последовательных вызовов функции (шаблон функции и функциональный объект-алгоритм)
ranges::generate_n (C++20)

Операции удаления

Определено в заголовке <algorithm>
removeremove_if	удаляет элементы, удовлетворяющие заданным критериям (шаблон функции и функциональный объект алгоритма)
ranges::removeranges::remove_if (C++20)(C++20)
remove_copyremove_copy_if	копирует диапазон элементов, пропуская те, которые удовлетворяют заданным критериям (шаблон функции и функциональный объект алгоритма)
ranges::remove_copyranges::remove_copy_if (C++20)(C++20)
unique	удаляет последовательные повторяющиеся элементы в диапазоне (шаблон функции и функциональный объект алгоритма)
ranges::unique (C++20)
unique_copy	создаёт копию части диапазона элементов без последовательных повторений (шаблон функции и функциональный объект алгоритма)
ranges::unique_copy (C++20)

Операции изменения порядка

Определено в заголовке <algorithm>
reverse	изменяет порядок элементов в диапазоне на обратный (шаблон функции и функциональный объект алгоритма)
ranges::reverse (C++20)
reverse_copy	создаёт копию диапазона в обратном порядке (шаблон функции и функциональный объект алгоритма)
ranges::reverse_copy (C++20)
rotate	циклически сдвигает порядок элементов в диапазоне (шаблон функции и функциональный объект алгоритма)
ranges::rotate (C++20)
rotate_copy	копирует и циклически сдвигает диапазон элементов (шаблон функции и функциональный объект алгоритма)
ranges::rotate_copy (C++20)
shift_leftshift_right (C++20)(C++20)	сдвигает элементы в диапазоне (шаблон функции и функциональный объект алгоритма)
ranges::shift_leftranges::shift_right (C++23)(C++23)
random_shuffleshuffle (до C++17)(C++11)	случайным образом переставляет элементы в диапазоне (шаблон функции и функциональный объект алгоритма)
ranges::shuffle (C++20)

Операции выборки

Определено в заголовке <algorithm>
sample (C++17)	выбирает N случайных элементов из последовательности (шаблон функции и функциональный объект алгоритма)
ranges::sample (C++20)

Сортировка и связанные операции

Требования

Некоторые алгоритмы требуют, чтобы последовательность, представленная аргументами, была «отсортирована» или «разбита на разделы». Если это требование не выполнено, поведение не определено.

Последовательность является отсортированной относительно компаратора comp, если для каждого итератора iter, указывающего на последовательность, и каждого неотрицательного целого числа n, такого что iter + n[1] является допустимым итератором, указывающим на элемент последовательности, comp(*(iter + n), *iter) == false[1].

(до C++20)

Последовательность является отсортированной относительно comp и proj для компаратора comp и проекции proj, если для каждого итератора iter, указывающего на последовательность, и каждого неотрицательного целого числа n, такого что iter + n[1] является допустимым итератором, указывающим на элемент последовательности, bool(std::invoke(comp, std::invoke(proj, *(iter + n)),                        std::invoke(proj, *iter))) [1] является false. Последовательность является отсортированной относительно компаратора comp, если она отсортирована относительно comp и std::identity{} (проекции тождества).

(начиная с C++20)

Последовательность [start, finish) является разбитой на разделы относительно выражения f(e), если существует целое число n такое, что для всех i в [0, std::distance(start, finish)), f(*(start + i))^[1] является true тогда и только тогда, когда i < n.

Операции разбиения на разделы

Определено в заголовке <algorithm>
is_partitioned (C++11)	определяет, разбит ли диапазон на разделы с помощью заданного предиката (шаблон функции и функциональный объект алгоритма)
ranges::is_partitioned (C++20)
partition	разделяет диапазон элементов на две группы (шаблон функции и функциональный объект алгоритма)
ranges::partition (C++20)
partition_copy (C++11)	копирует диапазон, распределяя элементы по двум группам (шаблон функции и функциональный объект алгоритма)
ranges::partition_copy (C++20)
stable_partition	разделяет элементы на две группы, сохраняя их относительный порядок внутри каждой группы (шаблон функции и функциональный объект алгоритма)
ranges::stable_partition (C++20)
partition_point (C++11)	находит точку разделения в диапазоне, разбитом на разделы (шаблон функции и функциональный объект алгоритма)
ranges::partition_point (C++20)

Операции сортировки

Определено в заголовке <algorithm>
sort	сортирует диапазон элементов (шаблон функции и функциональный объект алгоритма)
ranges::sort (C++20)
stable_sort	сортирует диапазон элементов, сохраняя относительный порядок эквивалентных элементов (шаблон функции и функциональный объект алгоритма)
ranges::stable_sort (C++20)
partial_sort	сортирует первые N элементов диапазона (шаблон функции и функциональный объект алгоритма)
ranges::partial_sort (C++20)
partial_sort_copy	копирует и частично сортирует диапазон элементов (шаблон функции и функциональный объект алгоритма)
ranges::partial_sort_copy (C++20)
is_sorted (C++11)	проверяет, отсортирован ли диапазон (шаблон функции и функциональный объект алгоритма)
ranges::is_sorted (C++20)
is_sorted_until (C++11)	находит наибольший отсортированный поддиапазон (шаблон функции и функциональный объект алгоритма)
ranges::is_sorted_until (C++20)
nth_element	находит N-й элемент, который находился бы на этой позиции после сортировки диапазона (шаблон функции и функциональный объект алгоритма)
ranges::nth_element (C++20)

Операции бинарного поиска (в диапазонах, разбитых на разделы)

Определено в заголовке <algorithm>
lower_bound	с помощью бинарного поиска находит первый элемент, не меньший заданного значения (шаблон функции и функциональный объект алгоритма)
ranges::lower_bound (C++20)
upper_bound	с помощью бинарного поиска находит первый элемент, больший заданного значения (шаблон функции и функциональный объект алгоритма)
ranges::upper_bound (C++20)
equal_range	с помощью бинарного поиска находит диапазон элементов, равных заданному значению (шаблон функции и функциональный объект алгоритма)
ranges::equal_range (C++20)
binary_search	с помощью бинарного поиска определяет, существует ли элемент в диапазоне (шаблон функции и функциональный объект алгоритма)
ranges::binary_search (C++20)

Операции над множествами (в отсортированных диапазонах)

Определено в заголовке <algorithm>
includes	определяет, является ли одна последовательность подпоследовательностью другой (шаблон функции и функциональный объект алгоритма)
ranges::includes (C++20)
set_union	вычисляет объединение двух множеств (шаблон функции и функциональный объект алгоритма)
ranges::set_union (C++20)
set_intersection	вычисляет пересечение двух множеств (шаблон функции и функциональный объект алгоритма)
ranges::set_intersection (C++20)
set_difference	вычисляет разность двух множеств (шаблон функции и функциональный объект алгоритма)
ranges::set_difference (C++20)
set_symmetric_difference	вычисляет симметрическую разность двух множеств (шаблон функции и функциональный объект алгоритма)
ranges::set_symmetric_difference (C++20)

Операции слияния (в отсортированных диапазонах)

Определено в заголовке <algorithm>
merge	сливает два отсортированных диапазона (шаблон функции и функциональный объект алгоритма)
ranges::merge (C++20)
inplace_merge	выполняет слияние двух упорядоченных диапазонов на месте (шаблон функции и функциональный объект алгоритма)
ranges::inplace_merge (C++20)

Операции с кучей

Диапазон [first, last) с произвольным доступом является кучей относительно компаратора comp, если bool(comp(first[(i - 1) / 2], first[i])) является false для всех целых чисел i из (0, last - first).

(до C++20)

Диапазон [first, last) с произвольным доступом является кучей относительно comp и proj для компаратора comp и проекции proj, если bool(std::invoke(comp, std::invoke(proj, first[(i - 1) / 2]),                        std::invoke(proj, first[i])) является false для всех целых чисел i из (0, last - first). Диапазон [first, last) с произвольным доступом является кучей относительно компаратора comp, если диапазон является кучей относительно comp и std::identity{} (проекции тождества).

(начиная с C++20)

Кучу можно создать с помощью std::make_heap и ranges::make_heap(начиная с C++20).

Подробнее о свойствах кучи см. в статье максимальная куча.

Определён в заголовке <algorithm>
push_heap	добавляет элемент в максимальную кучу (шаблон функции и функциональный объект алгоритма)
ranges::push_heap (C++20)
pop_heap	удаляет наибольший элемент из максимальной кучи (шаблон функции и функциональный объект алгоритма)
ranges::pop_heap (C++20)
make_heap	создаёт максимальную кучу из диапазона элементов (шаблон функции и функциональный объект алгоритма)
ranges::make_heap (C++20)
sort_heap	преобразует максимальную кучу в диапазон элементов, отсортированных по возрастанию (шаблон функции и функциональный объект алгоритма)
ranges::sort_heap (C++20)
is_heap (C++11)	проверяет, является ли заданный диапазон максимальной кучей (шаблон функции и функциональный объект алгоритма)
ranges::is_heap (C++20)
is_heap_until (C++11)	находит наибольший поддиапазон, являющийся максимальной кучей (шаблон функции и функциональный объект алгоритма)
ranges::is_heap_until (C++20)

Операции нахождения минимума и максимума

Определён в заголовке <algorithm>
max	возвращает большее из заданных значений (шаблон функции и функциональный объект алгоритма)
ranges::max (C++20)
max_element	возвращает наибольший элемент диапазона (шаблон функции и функциональный объект алгоритма)
ranges::max_element (C++20)
min	возвращает меньшее из заданных значений (шаблон функции и функциональный объект алгоритма)
ranges::min (C++20)
min_element	возвращает наименьший элемент диапазона (шаблон функции и функциональный объект алгоритма)
ranges::min_element (C++20)
minmax (C++11)	возвращает меньший и больший из двух элементов (шаблон функции и функциональный объект алгоритма)
ranges::minmax (C++20)
minmax_element (C++11)	возвращает наименьший и наибольший элементы диапазона (шаблон функции и функциональный объект алгоритма)
ranges::minmax_element (C++20)
clamp (C++17)	ограничивает значение заданными граничными значениями (шаблон функции и функциональный объект алгоритма)
ranges::clamp (C++20)

Операции лексикографического сравнения

Определён в заголовке <algorithm>
lexicographical_compare	лексикографически сравнивает два диапазона (шаблон функции и функциональный объект алгоритма)
ranges::lexicographical_compare (C++20)
lexicographical_compare_three_way (C++20)	сравнивает два диапазона с помощью трёхстороннего сравнения (шаблон функции)

Операции перестановок

Определён в заголовке <algorithm>
next_permutation	создаёт следующую лексикографически большую перестановку элементов диапазона (шаблон функции и функциональный объект алгоритма)
ranges::next_permutation (C++20)
prev_permutation	создаёт следующую лексикографически меньшую перестановку элементов диапазона (шаблон функции и функциональный объект алгоритма)
ranges::prev_permutation (C++20)
is_permutation (C++11)	определяет, является ли последовательность перестановкой другой последовательности (шаблон функции и функциональный объект алгоритма)
ranges::is_permutation (C++20)

Числовые операции

Определён в заголовке <numeric>
iota (C++11)	заполняет диапазон последовательными приращениями начального значения (шаблон функции и функциональный объект алгоритма)
ranges::iota (C++23)
accumulate	суммирует или свёртывает диапазон элементов (шаблон функции)
inner_product	вычисляет скалярное произведение двух диапазонов элементов (шаблон функции)
adjacent_difference	вычисляет разности между соседними элементами диапазона (шаблон функции)
partial_sum	вычисляет частичные суммы диапазона элементов (шаблон функции)
reduce (C++17)	аналогичен std::accumulate, но вычисления могут выполняться не по порядку (шаблон функции)
exclusive_scan (C++17)	аналогичен std::partial_sum, но исключает i-й входной элемент из i-й суммы (шаблон функции)
inclusive_scan (C++17)	аналогичен std::partial_sum, но включает i-й входной элемент в i-ю сумму (шаблон функции)
transform_reduce (C++17)	применяет вызываемый объект, а затем выполняет свёртку без гарантии порядка (шаблон функции)
transform_exclusive_scan (C++17)	применяет вызываемый объект, а затем вычисляет исключительное сканирование (шаблон функции)
transform_inclusive_scan (C++17)	применяет вызываемый объект, а затем вычисляет включительное сканирование (шаблон функции)

Специализированные алгоритмы <memory>

Специализированные алгоритмы <random> (начиная с C++26)

Определён в заголовке <random>
ranges::generate_random (C++26)	заполняет диапазон случайными числами, полученными от генератора равномерно распределённых случайных битов (функциональный объект алгоритма)

Примечания

Макрос проверки поддержки возможностей	Значение	Стандарт	Возможность
__cpp_lib_algorithm_default_value_type	202403L	(C++26)	Инициализация списком в алгоритмах
__cpp_lib_algorithm_iterator_requirements	202207L	(C++23)	Итераторы ranges в качестве входных данных для алгоритмов, не относящихся к ranges
__cpp_lib_clamp	201603L	(C++17)	std::clamp
__cpp_lib_constexpr_algorithms	201806L	(C++20)	Constexpr для алгоритмов
	202306L	(C++26)	Стабильная сортировка constexpr
__cpp_lib_execution	201603L	(C++17)	Политики выполнения
	201902L	(C++20)	std::execution::unsequenced_policy
__cpp_lib_freestanding_algorithm	202311L	(C++26)	Средства для freestanding-сред в <algorithm>
__cpp_lib_parallel_algorithm	201603L	(C++17)	Параллельные алгоритмы
	202506L	(C++26)	Параллельные алгоритмы диапазонов
__cpp_lib_robust_nonmodifying_seq_ops	201304L	(C++14)	Повышение надёжности немодифицирующих операций над последовательностями (двухдиапазонные перегрузки для std::mismatch, std::equal и std::is_permutation)
__cpp_lib_sample	201603L	(C++17)	std::sample
__cpp_lib_shift	201806L	(C++20)	std::shift_left и std::shift_right

Библиотека C

Определён в заголовке <cstdlib>
qsort	сортирует диапазон элементов неопределённого типа (функция)
bsearch	выполняет поиск элемента неопределённого типа в массиве (функция)

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были ретроактивно применены к ранее опубликованным стандартам C++.

DR	Применяется к	Опубликованное поведение	Исправленное поведение
LWG 193	C++98	требовалось, чтобы *first был наибольшим элементом кучи	могут существовать элементы, равные *first
LWG 2150	C++98	определение отсортированной последовательности было неверным	исправлено
LWG 2166	C++98	требование к куче недостаточно точно соответствовало определению максимальной кучи	требование улучшено

См. также

Документация по C для алгоритмов