Алгоритмы с ограничениями (начиная с C++20)
C++20 предоставляет версии с ограничениями для большинства алгоритмов в пространстве имён std::ranges. В этих алгоритмах диапазон можно задать либо парой итератор–сентинел, либо одним аргументом типа range; также поддерживаются проекции и вызываемые объекты — указатели на члены. Кроме того, типы возвращаемых значений большинства алгоритмов были изменены, чтобы возвращать всю потенциально полезную информацию, вычисленную во время выполнения алгоритма.
Объекты-функции алгоритмов
Объект-функция алгоритма (AFO), неофициально известный как niebloid , — это объект точки настройки (CPO), заданный одним или несколькими перегруженными шаблонами функций. Имя этих шаблонов функций обозначает соответствующий объект-функцию алгоритма.
Для объекта-функции алгоритма o пусть S — соответствующее множество шаблонов функций. Тогда для любой последовательности аргументов args... выражение o(args...) эквивалентно выражению s(args...), где результат поиска имени для s — множество перегрузок S.
Алгоритмы с ограничениями в пространстве имён std::ranges определены как объекты-функции алгоритмов. В результате:
- При вызове любого из них нельзя указывать явные списки аргументов шаблона.
- Ни один из них не виден при поиске с учётом аргументов.
- Если любой из них найден при обычном неквалифицированном поиске как имя слева от оператора вызова функции, поиск с учётом аргументов подавляется.
Параметры-диапазоны
Некоторые перегрузки принимают аргументы типа range. Они ведут себя так, как если бы реализовывались путём вызова соответствующей перегрузки в пространстве имён ranges, принимающей отдельные аргументы-итератор и сентинел, где для каждого аргумента-диапазона r:
- Соответствующий аргумент-итератор инициализируется значением
ranges::begin(r).
| (до C++26) |
| (начиная с C++26) |
Немодифицирующие операции над последовательностями
Определено в заголовке <algorithm> |
|
|---|---|
Определено в пространстве имён std::ranges |
|
Пакетные операции |
|
|
(C++20) | применяет унарный объект-функцию к элементам диапазона (объект-функция алгоритма) |
|
(C++20) | применяет объект-функцию к первым N элементам последовательности (объект-функция алгоритма) |
Операции поиска |
|
|
(C++20)(C++20)(C++20) | проверяет, является ли предикат true для всех, некоторых или ни для одного из элементов диапазона(объект-функция алгоритма) |
|
(C++23)(C++23) | проверяет, содержит ли диапазон заданный элемент или поддиапазон (объект-функция алгоритма) |
|
(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)(C++23) | задаёт требование, согласно которому вызываемый тип можно использовать в алгоритмах свёртки (концепт только для описания*) |
|
(C++23) | выполняет свёртку диапазона элементов слева направо (объект-функция алгоритма) |
|
(C++23) | выполняет свёртку диапазона элементов слева направо, используя первый элемент в качестве начального значения (объект-функция алгоритма) |
|
(C++23) | выполняет свёртку диапазона элементов справа налево (объект-функция алгоритма) |
|
(C++23) | выполняет свёртку диапазона элементов справа налево, используя последний элемент в качестве начального значения (объект-функция алгоритма) |
|
(C++23) | выполняет свёртку диапазона элементов слева направо и возвращает пару (итератор, значение) (объект-функция алгоритма) |
|
(C++23) | выполняет свёртку диапазона элементов слева направо, используя первый элемент в качестве начального значения, и возвращает пару (итератор, optional) (объект-функция алгоритма) |
Модифицирующие операции над последовательностями
Определено в заголовке <algorithm> |
|
|---|---|
Определено в пространстве имён std::ranges |
|
Операции копирования |
|
|
(C++20)(C++20) | копирует диапазон элементов в новое место (объект-функция алгоритма) |
|
(C++20) | копирует заданное количество элементов в новое место (объект-функция алгоритма) |
|
(C++20) | копирует диапазон элементов в обратном порядке (объект-функция алгоритма) |
|
(C++20) | перемещает диапазон элементов в новое место (объект-функция алгоритма) |
|
(C++20) | перемещает диапазон элементов в новое место в обратном порядке (объект-функция алгоритма) |
Операции обмена |
|
|
(C++20) | обменивает местами два диапазона элементов (объект-функция алгоритма) |
Операции преобразования |
|
|
(C++20) | применяет функцию к диапазону элементов (объект-функция алгоритма) |
|
(C++20)(C++20) | заменяет все значения, удовлетворяющие заданным критериям, другим значением (объект-функция алгоритма) |
|
(C++20)(C++20) | копирует диапазон, заменяя элементы, удовлетворяющие заданным критериям, другим значением (объект-функция алгоритма) |
Операции генерации |
|
|
(C++20) | присваивает элементам диапазона заданное значение (объект-функция алгоритма) |
|
(C++20) | присваивает значение заданному количеству элементов (объект-функция алгоритма) |
|
(C++20) | сохраняет результат функции в диапазоне (объект-функция алгоритма) |
|
(C++20) | сохраняет результат N вызовов функции (объект-функция алгоритма) |
Операции удаления |
|
|
(C++20)(C++20) | удаляет элементы, удовлетворяющие заданным критериям (объект-функция алгоритма) |
|
(C++20)(C++20) | копирует диапазон элементов, исключая те, которые удовлетворяют заданным критериям (объект-функция алгоритма) |
|
(C++20) | удаляет повторяющиеся подряд элементы диапазона (объект-функция алгоритма) |
|
(C++20) | создаёт копию части диапазона элементов без повторяющихся подряд элементов (объект-функция алгоритма) |
Операции изменения порядка |
|
|
(C++20) | изменяет порядок элементов диапазона на обратный (объект-функция алгоритма) |
|
(C++20) | создаёт копию диапазона с обратным порядком элементов (объект-функция алгоритма) |
|
(C++20) | циклически сдвигает элементы диапазона (объект-функция алгоритма) |
|
(C++20) | копирует диапазон элементов с циклическим сдвигом (объект-функция алгоритма) |
|
(C++23)(C++23) | сдвигает элементы диапазона (объект-функция алгоритма) |
|
(C++20) | случайным образом переставляет элементы диапазона (объект-функция алгоритма) |
Операции выборки |
|
|
(C++20) | выбирает N случайных элементов из последовательности (объект-функция алгоритма) |
Сортировка и связанные с ней операции
Определено в заголовочном файле <algorithm> |
|
|---|---|
Определено в пространстве имён std::ranges |
|
Операции разбиения |
|
|
(C++20) | определяет, разбит ли диапазон согласно заданному предикату (функциональный объект алгоритма) |
|
(C++20) | разделяет диапазон элементов на две группы (функциональный объект алгоритма) |
|
(C++20) | копирует диапазон, разделяя элементы на две группы (функциональный объект алгоритма) |
|
(C++20) | разделяет элементы на две группы, сохраняя их относительный порядок внутри каждой группы (функциональный объект алгоритма) |
|
(C++20) | находит точку разбиения в разбитом диапазоне (функциональный объект алгоритма) |
Операции сортировки |
|
|
(C++20) | проверяет, отсортирован ли диапазон (функциональный объект алгоритма) |
|
(C++20) | находит наибольший отсортированный поддиапазон (функциональный объект алгоритма) |
|
(C++20) | сортирует диапазон элементов (функциональный объект алгоритма) |
|
(C++20) | сортирует первые N элементов диапазона (функциональный объект алгоритма) |
|
(C++20) | копирует и частично сортирует диапазон элементов (функциональный объект алгоритма) |
|
(C++20) | сортирует диапазон элементов, сохраняя относительный порядок эквивалентных элементов (функциональный объект алгоритма) |
|
(C++20) | находит N-й элемент в том порядке, в котором он находился бы в отсортированном диапазоне (функциональный объект алгоритма) |
Операции двоичного поиска (в отсортированных диапазонах) |
|
|
(C++20) | находит с помощью двоичного поиска первый элемент, не меньший заданного значения (функциональный объект алгоритма) |
|
(C++20) | находит с помощью двоичного поиска первый элемент, больший заданного значения (функциональный объект алгоритма) |
|
(C++20) | определяет с помощью двоичного поиска, существует ли элемент в диапазоне (функциональный объект алгоритма) |
|
(C++20) | находит с помощью двоичного поиска диапазон элементов, соответствующих заданному значению (функциональный объект алгоритма) |
Операции над множествами (в отсортированных диапазонах) |
|
|
(C++20) | определяет, является ли одна последовательность подпоследовательностью другой (функциональный объект алгоритма) |
|
(C++20) | вычисляет разность двух множеств (функциональный объект алгоритма) |
|
(C++20) | вычисляет пересечение двух множеств (функциональный объект алгоритма) |
|
(C++20) | вычисляет симметрическую разность двух множеств (функциональный объект алгоритма) |
|
(C++20) | вычисляет объединение двух множеств (функциональный объект алгоритма) |
Операции слияния (в отсортированных диапазонах) |
|
|
(C++20) | сливает два отсортированных диапазона (функциональный объект алгоритма) |
|
(C++20) | сливает два упорядоченных диапазона на месте (функциональный объект алгоритма) |
Операции с кучей |
|
|
(C++20) | проверяет, является ли заданный диапазон max-кучей (функциональный объект алгоритма) |
|
(C++20) | находит наибольший поддиапазон, являющийся max-кучей (функциональный объект алгоритма) |
|
(C++20) | создаёт max-кучу из диапазона элементов (функциональный объект алгоритма) |
|
(C++20) | добавляет элемент в max-кучу (функциональный объект алгоритма) |
|
(C++20) | удаляет наибольший элемент из max-кучи (функциональный объект алгоритма) |
|
(C++20) | преобразует max-кучу в отсортированный диапазон элементов (функциональный объект алгоритма) |
Операции поиска минимума и максимума |
|
|
(C++20) | возвращает большее из заданных значений (функциональный объект алгоритма) |
|
(C++20) | возвращает наибольший элемент диапазона (функциональный объект алгоритма) |
|
(C++20) | возвращает меньшее из заданных значений (функциональный объект алгоритма) |
|
(C++20) | возвращает наименьший элемент диапазона (функциональный объект алгоритма) |
|
(C++20) | возвращает меньшее и большее из двух элементов (функциональный объект алгоритма) |
|
(C++20) | возвращает наименьший и наибольший элементы диапазона (функциональный объект алгоритма) |
|
(C++20) | ограничивает значение заданными нижней и верхней границами (функциональный объект алгоритма) |
Операции лексикографического сравнения |
|
|
(C++20) | лексикографически сравнивает два диапазона (функциональный объект алгоритма) |
Операции перестановок |
|
|
(C++20) | определяет, является ли одна последовательность перестановкой другой (функциональный объект алгоритма) |
|
(C++20) | генерирует следующую лексикографически большую перестановку элементов диапазона (функциональный объект алгоритма) |
|
(C++20) | генерирует следующую лексикографически меньшую перестановку элементов диапазона (функциональный объект алгоритма) |
Числовые операции
Определено в заголовочном файле <numeric> |
|
|---|---|
Определено в пространстве имён std::ranges |
|
|
(C++23) | заполняет диапазон последовательными приращениями начального значения (функциональный объект алгоритма) |
Специализированные алгоритмы <memory>
Определено в заголовочном файле <memory> |
|
|---|---|
Определено в пространстве имён std::ranges |
|
Создание объектов (пакетное) |
|
|
(C++20) | создаёт объект по заданному адресу (функциональный объект алгоритма) |
|
(C++20) | копирует диапазон объектов в неинициализированную область памяти (функциональный объект алгоритма) |
|
(C++20) | копирует заданное количество объектов в неинициализированную область памяти (функциональный объект алгоритма) |
|
(C++20) | копирует объект в неинициализированную область памяти, заданную диапазоном (функциональный объект алгоритма) |
|
(C++20) | копирует объект в неинициализированную область памяти, заданную начальной позицией и количеством элементов (функциональный объект алгоритма) |
|
(C++20) | перемещает диапазон объектов в неинициализированную область памяти (функциональный объект алгоритма) |
|
(C++20) | перемещает заданное количество объектов в неинициализированную область памяти (функциональный объект алгоритма) |
|
(C++20) | создаёт объекты посредством инициализации по умолчанию в неинициализированной области памяти, заданной диапазоном (функциональный объект алгоритма) |
|
(C++20) | создаёт объекты посредством инициализации по умолчанию в неинициализированной области памяти, заданной начальной позицией и количеством элементов (функциональный объект алгоритма) |
|
(C++20) | создаёт объекты посредством инициализации значением в неинициализированной области памяти, заданной диапазоном (функциональный объект алгоритма) |
|
(C++20) | создаёт объекты посредством инициализации значением в неинициализированной области памяти, заданной начальной позицией и количеством элементов (функциональный объект алгоритма) |
Уничтожение объектов (пакетное) |
|
|
(C++20) | уничтожает диапазон объектов (функциональный объект алгоритма) |
|
(C++20) | уничтожает заданное количество объектов в диапазоне (функциональный объект алгоритма) |
|
(C++20) | уничтожает объект по заданному адресу (функциональный объект алгоритма) |
Специализированные алгоритмы <random>
Определено в заголовочном файле <random> |
|
|---|---|
Определено в пространстве имён std::ranges |
|
|
(C++26) | заполняет диапазон случайными числами, полученными от равномерного генератора случайных битов (функциональный объект алгоритма) |
Типы возвращаемых значений
Определено в заголовочном файле <algorithm> |
|
|---|---|
Определено в пространстве имён std::ranges |
|
|
(C++20) | предоставляет способ хранить итератор и функциональный объект как единое целое (шаблон класса) |
|
(C++20) | предоставляет способ хранить два итератора как единое целое (шаблон класса) |
|
(C++20) | предоставляет способ хранить два итератора как единое целое (шаблон класса) |
|
(C++20) | предоставляет способ хранить три итератора как единое целое (шаблон класса) |
|
(C++20) | предоставляет способ хранить три итератора как единое целое (шаблон класса) |
|
(C++20) | предоставляет способ хранить два объекта или ссылки одного типа как единое целое (шаблон класса) |
|
(C++20) | предоставляет способ хранить итератор и логический флаг как единое целое (шаблон класса) |
|
(C++23) | предоставляет способ хранить итератор и значение как единое целое (шаблон класса) |
|
(C++23) | предоставляет способ хранить итератор и значение как единое целое (шаблон класса) |
Примечания
| Макрос проверки функциональности | Значение | Стандарт | Функция |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type | 202403L | (C++26) | Инициализация списком для алгоритмов |
__cpp_lib_parallel_algorithm | 202506L | (C++26) | Параллельные алгоритмы для диапазонов |
__cpp_lib_ranges | 201911L | (C++20) | Библиотека диапазонов и алгоритмы с ограничениями |
__cpp_lib_ranges_contains | 202207L | (C++23) |
std::ranges::contains |
__cpp_lib_ranges_find_last | 202207L | (C++23) |
std::ranges::find_last |
__cpp_lib_ranges_fold | 202207L | (C++23) |
std::ranges алгоритмы свёртки |
__cpp_lib_ranges_iota | 202202L | (C++23) |
std::ranges::iota |
__cpp_lib_ranges_starts_ends_with | 202106L | (C++23) |
std::ranges::starts_with, std::ranges::ends_with |
__cpp_lib_shift | 201806L | (C++20) |
std::shift_left, std::shift_right |
202202L | (C++23) |
std::ranges::shift_left, std::ranges::shift_right |
|
__cpp_lib_ranges_generate_random | 202403L | (C++26) |
std::ranges::generate_random |
Отчёты об ошибках
Следующие отчёты об ошибках, изменяющие поведение, были применены задним числом к ранее опубликованным стандартам C++.
| DR | Применён к | Опубликованное поведение | Корректное поведение |
|---|---|---|---|
| P3136R1 | C++20 |
ниблоиды могли быть специфицированы как специальные сущности, отличные от функциональных объектов | должны быть специфицированы как функциональные объекты |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges
