Библиотека алгоритмов
Библиотека алгоритмов определяет функции для различных целей (например, поиска, сортировки, подсчета, манипуляции), которые работают с диапазонами элементов.
Ограниченные алгоритмы (начиная с C++20)
C++20 предоставляет ограниченные версии большинства алгоритмов в пространстве имён std::ranges. В этих алгоритмах диапазон может быть задан либо как итератор-страж пара, либо как единый диапазон аргумент, также поддерживаются проекции и вызываемые объекты-указатели на члены. Кроме того, типы возвращаемых значений большинства алгоритмов были изменены, чтобы возвращать всю потенциально полезную информацию, вычисленную во время выполнения алгоритма.
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 | |
(C++17)(C++17)(C++17)(C++20) |
типы политик выполнения (класс) |
(C++17)(C++17)(C++17)(C++20) |
глобальные объекты политик выполнения (константа) |
Определено в пространстве имён
std | |
(C++17) |
проверяет, представляет ли класс политику выполнения (шаблон класса) |
(C++26) |
указывает, что тип представляет политику выполнения (концепт, используемый только для пояснения*) |
Немодифицирующие операции над последовательностями
Пакетные операции
Определён в заголовке
<algorithm> | |
| применяет унарный функциональный объект к элементам из диапазона (шаблон функции & алгоритмический функциональный объект) | |
(C++20) |
|
(C++17) |
применяет функциональный объект к первым N элементам последовательности (шаблон функции & алгоритмический функциональный объект) |
(C++20) |
|
Операции поиска
Определены в заголовке
<algorithm> | |
(C++11)(C++11)(C++11) |
проверяет, выполняется ли предикат true для всех, хотя бы для одного или ни для одного из элементов в диапазоне(шаблон функции & алгоритм, функциональный объект) |
(C++20)(C++20)(C++20) |
|
(C++23)(C++23) |
проверяет, содержит ли диапазон данный элемент или поддиапазон (алгоритм, функциональный объект) |
(C++11) |
находит первый элемент, удовлетворяющий определённым критериям (шаблон функции & алгоритм, функциональный объект) |
(C++20)(C++20)(C++20) |
|
(C++23)(C++23)(C++23) |
находит последний элемент, удовлетворяющий определённым критериям (алгоритм, функциональный объект) |
| находит последнюю последовательность элементов в заданном диапазоне (шаблон функции & алгоритм, функциональный объект) | |
(C++20) |
|
| ищет любой элемент из заданного набора (шаблон функции & алгоритм, функциональный объект) | |
(C++20) |
|
| находит первые два смежных элемента, которые равны (или удовлетворяют заданному предикату) (шаблон функции & алгоритм, функциональный объект) | |
(C++20) |
|
| возвращает количество элементов, удовлетворяющих определённым критериям (шаблон функции & алгоритм, функциональный объект) | |
(C++20)(C++20) |
|
| находит первую позицию, где два диапазона различаются (шаблон функции & алгоритм, функциональный объект) | |
(C++20) |
|
| определяет, одинаковы ли два набора элементов (шаблон функции & алгоритм, функциональный объект) | |
(C++20) |
|
| ищет первое вхождение диапазона элементов (шаблон функции & алгоритм, функциональный объект) | |
(C++20) |
|
| ищет первое вхождение нескольких последовательных копий элемента в диапазоне (шаблон функции & алгоритм, функциональный объект) | |
(C++20) |
|
(C++23) |
проверяет, начинается ли диапазон с другого диапазона (алгоритм, функциональный объект) |
(C++23) |
проверяет, заканчивается ли диапазон другим диапазоном (алгоритм, функциональный объект) |
Сворачивающие операции (начиная с C++23)
|
Определено в заголовочном файле
<algorithm>
|
|
|
(C++23)
|
левостороннее свертывание диапазона элементов
(объект-функция алгоритма) |
|
(C++23)
|
левостороннее свертывание диапазона элементов с использованием первого элемента в качестве начального значения
(объект-функция алгоритма) |
|
(C++23)
|
правостороннее свертывание диапазона элементов
(объект-функция алгоритма) |
|
(C++23)
|
правостороннее свертывание диапазона элементов с использованием последнего элемента в качестве начального значения
(объект-функция алгоритма) |
|
(C++23)
|
левостороннее свертывание диапазона элементов и возврат
пары
(итератор, значение)
(объект-функция алгоритма) |
|
левостороннее свертывание диапазона элементов с использованием первого элемента в качестве начального значения и возврат
пары
(итератор,
optional
)
(объект-функция алгоритма) |
|
Операции модификации последовательностей
Операции копирования
Определено в заголовке
<algorithm> | |
(C++11) |
копирует диапазон элементов в новое расположение (шаблон функции & объект функции алгоритма) |
(C++20)(C++20) |
|
(C++11) |
копирует заданное количество элементов в новое расположение (шаблон функции & объект функции алгоритма) |
(C++20) |
|
| копирует диапазон элементов в обратном порядке (шаблон функции & объект функции алгоритма) | |
(C++20) |
|
(C++11) |
перемещает диапазон элементов в новое расположение (шаблон функции & объект функции алгоритма) |
(C++20) |
|
(C++11) |
перемещает диапазон элементов в новое расположение в обратном порядке (шаблон функции & объект функции алгоритма) |
(C++20) |
|
Операции обмена
Определено в заголовке
<algorithm> (до C++11) | |
Определено в заголовке
<utility> (начиная с C++11) | |
Определено в заголовке
<string_view> | |
| обменивает значения двух объектов (шаблон функции) | |
Определено в заголовке
<algorithm> | |
| обменивает два диапазона элементов (шаблон функции & алгоритм, функциональный объект) | |
(C++20) |
|
| обменивает элементы, на которые указывают два итератора (шаблон функции) | |
Операции преобразования
Определено в заголовке
<algorithm> | |
| применяет функцию к диапазону элементов, сохраняя результаты в целевом диапазоне (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| заменяет все значения, удовлетворяющие определённым критериям, другим значением (шаблон функции & объект-функция алгоритма) | |
(C++20)(C++20) |
|
| копирует диапазон, заменяя элементы, удовлетворяющие определённым критериям, другим значением (шаблон функции & объект-функция алгоритма) | |
(C++20)(C++20) |
|
Генерирующие операции
Определено в заголовке
<algorithm> | |
| присваивает копированием заданное значение каждому элементу в диапазоне (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| присваивает копированием заданное значение N элементам в диапазоне (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| присваивает результаты последовательных вызовов функции каждому элементу в диапазоне (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| присваивает результаты последовательных вызовов функции N элементам в диапазоне (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
Операции удаления
Определено в заголовочном файле
<algorithm> | |
| удаляет элементы, удовлетворяющие определённым критериям (шаблон функции & объект-функция алгоритма) | |
(C++20)(C++20) |
|
| создаёт копию диапазона, пропуская элементы, удовлетворяющие определённым критериям (шаблон функции & объект-функция алгоритма) | |
(C++20)(C++20) |
|
| удаляет последовательные повторяющиеся элементы в диапазоне (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| создаёт копию диапазона, не содержащую последовательных повторяющихся элементов (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
Операции изменения порядка
Определено в заголовке
<algorithm> | |
| изменяет порядок элементов в диапазоне на обратный (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| создаёт копию диапазона с обратным порядком элементов (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| выполняет циклический сдвиг порядка элементов в диапазоне (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| копирует и выполняет циклический сдвиг диапазона элементов (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
(C++20)(C++20) |
выполняет сдвиг элементов в диапазоне (шаблон функции & функциональный объект алгоритма) |
(C++23)(C++23) |
|
(до C++17)(C++11) |
случайным образом переупорядочивает элементы в диапазоне (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
Операции выборки
Определён в заголовке
<algorithm> | |
(C++17) |
выбирает N случайных элементов из последовательности (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
Требования
Некоторые алгоритмы требуют, чтобы последовательность, представленная аргументами, была «отсортирована» или «разделена». Поведение не определено, если это требование не выполнено.
|
Последовательность отсортирована относительно компаратора |
(до C++20) |
|
Последовательность отсортирована относительно Последовательность отсортирована относительно компаратора |
(начиная с C++20) |
Последовательность [start, finish) является разделённой относительно выражения f(e) если существует целое число n такое, что для всех i в [0, std::distance(start, finish)), f(*(start + i))[1] является true тогда и только тогда, когда i < n.
Операции разделения
Определено в заголовке
<algorithm> | |
(C++11) |
определяет, разделён ли диапазон по заданному предикату (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
| разделяет диапазон элементов на две группы (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
(C++11) |
копирует диапазон, разделяя элементы на две группы (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
| разделяет элементы на две группы, сохраняя их относительный порядок внутри каждой группы (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
(C++11) |
находит точку разделения разделённого диапазона (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
Операции сортировки
Определено в заголовке
<algorithm> | |
| сортирует диапазон элементов (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| сортирует диапазон элементов, сохраняя относительный порядок эквивалентных элементов (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| сортирует первые N элементов диапазона (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| копирует и частично сортирует диапазон элементов (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
(C++11) |
проверяет, отсортирован ли диапазон (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
(C++11) |
находит наибольший отсортированный поддиапазон (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
| находит N-й элемент, если бы диапазон был отсортирован (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
Операции бинарного поиска (на разбитых диапазонах)
Определено в заголовке
<algorithm> | |
| находит первый элемент, не меньший заданного значения, используя бинарный поиск (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| находит первый элемент, больший заданного значения, используя бинарный поиск (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| находит диапазон элементов, соответствующих заданному значению, используя бинарный поиск (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| определяет, существует ли элемент в диапазоне, используя бинарный поиск (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
Операции над множествами (на отсортированных диапазонах)
Определено в заголовке
<algorithm> | |
| определяет, является ли одна последовательность подпоследовательностью другой (шаблон функции & объект функции алгоритма) | |
(C++20) |
|
| вычисляет объединение двух множеств (шаблон функции & объект функции алгоритма) | |
(C++20) |
|
| вычисляет пересечение двух множеств (шаблон функции & объект функции алгоритма) | |
(C++20) |
|
| вычисляет разность двух множеств (шаблон функции & объект функции алгоритма) | |
(C++20) |
|
| вычисляет симметрическую разность двух множеств (шаблон функции & объект функции алгоритма) | |
Операции слияния (на отсортированных диапазонах)
Определено в заголовке
<algorithm> | |
| объединяет два отсортированных диапазона (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| объединяет два упорядоченных диапазона на месте (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
Операции с кучей
|
Произвольный доступ диапазон |
(до C++20) |
|
Произвольный доступ диапазон Диапазон с произвольным доступом |
(начиная с C++20) |
Куча может быть создана с помощью std::make_heap и ranges::make_heap(начиная с C++20).
Для получения дополнительной информации о куче см. максимальная куча.
Определено в заголовке
<algorithm> | |
| добавляет элемент в максимальную кучу (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| удаляет наибольший элемент из максимальной кучи (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| создает максимальную кучу из диапазона элементов (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
| преобразует максимальную кучу в диапазон элементов, отсортированных по возрастанию (шаблон функции & объект-функция алгоритма) | |
(C++20) |
|
(C++11) |
проверяет, является ли заданный диапазон максимальной кучей (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
(C++11) |
находит наибольший поддиапазон, являющийся максимальной кучей (шаблон функции & объект-функция алгоритма) |
(C++20) |
|
Операции минимума/максимума
Определено в заголовочном файле
<algorithm> | |
| возвращает большее из заданных значений (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| возвращает наибольший элемент в диапазоне (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| возвращает меньшее из заданных значений (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
| возвращает наименьший элемент в диапазоне (шаблон функции & функциональный объект алгоритма) | |
(C++20) |
|
(C++11) |
возвращает меньшее и большее из двух элементов (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
(C++11) |
возвращает наименьший и наибольший элементы в диапазоне (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
(C++17) |
зажимает значение между парой граничных значений (шаблон функции & функциональный объект алгоритма) |
(C++20) |
|
Операции лексикографического сравнения
Определено в заголовке
<algorithm> | |
| сравнивает два диапазона лексикографически (шаблон функции & функциональный объект алгоритма) | |
| сравнивает два диапазона с помощью трёхстороннего сравнения (шаблон функции) | |
Операции перестановки
Определено в заголовке
<algorithm> | |
| создаёт следующую в лексикографическом порядке перестановку диапазона элементов (шаблон функции& функциональный объект алгоритма) | |
(C++20) |
|
| создаёт предыдущую в лексикографическом порядке перестановку диапазона элементов (шаблон функции& функциональный объект алгоритма) | |
(C++20) |
|
(C++11) |
определяет, является ли последовательность перестановкой другой последовательности (шаблон функции& функциональный объект алгоритма) |
(C++20) |
|
Числовые операции
Определено в заголовке
<numeric> | |
(C++11) |
заполняет диапазон последовательными приращениями начального значения (шаблон функции & алгоритм функциональный объект) |
(C++23) |
|
| суммирует или свёртывает диапазон элементов (шаблон функции) | |
| вычисляет внутреннее произведение двух диапазонов элементов (шаблон функции) | |
| вычисляет разности между соседними элементами в диапазоне (шаблон функции) | |
| вычисляет частичную сумму диапазона элементов (шаблон функции) | |
(C++17) |
аналогична std::accumulate, за исключением неупорядоченного выполнения (шаблон функции) |
(C++17) |
аналогична std::partial_sum, исключает i-й входной элемент из i-й суммы (шаблон функции) |
(C++17) |
аналогична std::partial_sum, включает i-й входной элемент в i-й сумму (шаблон функции) |
(C++17) |
применяет вызываемый объект, затем выполняет неупорядоченную редукцию (шаблон функции) |
(C++17) |
применяет вызываемый объект, затем вычисляет эксклюзивное сканирование (шаблон функции) |
(C++17) |
применяет вызываемый объект, затем вычисляет инклюзивное сканирование (шаблон функции) |
Специализированные <memory> алгоритмы
Специализированные <random>алгоритмы (начиная с C++26)
Определено в заголовке
<random> | |
(C++26) |
заполняет диапазон случайными числами из генератора равномерных случайных битов (функциональный объект алгоритма) |
Примечания
| Макрос тестирования возможностей | Значение | Стандарт | Возможность |
|---|---|---|---|
__cpp_lib_algorithm_iterator_requirements
|
202207L
|
(C++23) | Итераторы диапазонов как входные данные для алгоритмов не-диапазонов |
__cpp_lib_clamp
|
201603L
|
(C++17) | std::clamp |
__cpp_lib_constexpr_algorithms
|
201806L
|
(C++20) | Constexpr для алгоритмов |
202306L
|
(C++26) | Constexpr стабильная сортировка | |
__cpp_lib_algorithm_default_value_type
|
202403L
|
(C++26) | Списковая инициализация для алгоритмов |
__cpp_lib_freestanding_algorithm
|
202311L
|
(C++26) | Автономные средства в <algorithm> |
__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>
|
|
|
сортирует диапазон элементов с неуказанным типом
(функция) |
|
|
выполняет поиск элемента с неуказанным типом в массиве
(функция) |
|
Отчеты о дефектах
Следующие отчеты об изменениях поведения, влияющие на дефекты, были применены ретроактивно к ранее опубликованным стандартам C++.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 193 | C++98 | heap required * first to be the largest element |
there can be elements
equal to * first |
| LWG 2150 | C++98 | the definition of a sorted sequence was incorrect | corrected |
| LWG 2166 | C++98 |
the heap requirement did not match the
definition of max heap closely enough |
requirement improved |
Смотрите также
|
C documentation
для
Algorithms
|