Constrained algorithms (since C++20)
From cppreference.net
C++20 предоставляет
ограниченные
версии большинства алгоритмов в пространстве имён
std::ranges
. В этих алгоритмах диапазон может быть задан либо как пара
итератор
-
cентинел
, либо как единый аргумент
range
, при этом поддерживаются проекции и вызываемые объекты типа указатель-на-член. Дополнительно,
типы возвращаемых значений
большинства алгоритмов были изменены для возврата всей потенциально полезной информации, вычисленной во время выполнения алгоритма.
Функциональные объекты алгоритмов
Объект-функция алгоритма (AFO), неформально известный как niebloid , представляет собой объект точки кастомизации (CPO), который задаётся в виде одной или нескольких перегруженных шаблонов функций. Имя этих шаблонов функций обозначает соответствующий объект-функцию алгоритма.
Для функционального объекта алгоритма
o
, пусть
S
будет соответствующим набором шаблонов функций. Тогда для любой последовательности аргументов
args...
,
o
(
args...
)
является
эквивалентным по выражению
выражению
s
(
args...
)
, где результатом поиска имени для
s
является набор перегрузок
S
.
Ограниченные алгоритмы в пространстве имён
std::ranges
определены как объекты-функции алгоритмов. В результате:
- Явные списки аргументов шаблона не могут быть указаны при вызове любого из них.
- Ни один из них не видим для поиска, зависящего от аргументов .
- Когда любой из них найден обычным поиском без квалификации как имя слева от оператора вызова функции, поиск, зависящий от аргументов , блокируется.
Алгоритмы с ограничениями
|
Определено в заголовочном файле
<algorithm>
|
|
|
Определено в пространстве имён
std::ranges
|
|
Немодифицирующие операции над последовательностями |
|
|
(C++20)
(C++20)
(C++20)
|
проверяет, является ли предикат
true
для всех, любого или ни одного из элементов в диапазоне
(функциональный объект алгоритма) |
|
(C++20)
|
применяет унарный
function object
к элементам из
range
(algorithm function object) |
|
(C++20)
|
применяет функциональный объект к первым N элементам последовательности
(функциональный объект алгоритма) |
|
(C++20)
(C++20)
|
возвращает количество элементов, удовлетворяющих заданным критериям
(функциональный объект алгоритма) |
|
(C++20)
|
находит первую позицию, в которой два диапазона различаются
(функциональный объект алгоритма) |
|
(C++20)
|
определяет, являются ли два набора элементов одинаковыми
(функциональный объект алгоритма) |
|
(C++20)
|
возвращает
true
если один диапазон лексикографически меньше другого
(функциональный объект алгоритма) |
|
(C++20)
(C++20)
(C++20)
|
находит первый элемент, удовлетворяющий определённым критериям
(функциональный объект алгоритма) |
|
(C++23)
(C++23)
(C++23)
|
находит последний элемент, удовлетворяющий определённым критериям
(функциональный объект алгоритма) |
|
(C++20)
|
находит последнюю последовательность элементов в определённом диапазоне
(функциональный объект алгоритма) |
|
(C++20)
|
выполняет поиск любого элемента из набора элементов
(функциональный объект алгоритма) |
|
(C++20)
|
находит первые два соседних элемента, которые равны (или удовлетворяют заданному предикату)
(функциональный объект алгоритма) |
|
(C++20)
|
выполняет поиск первого вхождения диапазона элементов
(функциональный объект алгоритма) |
|
(C++20)
|
ищет первое вхождение заданного количества последовательных копий элемента в диапазоне
(функциональный объект алгоритма) |
|
(C++23)
(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++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)
|
изменяет порядок элементов в диапазоне
(функциональный объект алгоритма) |
|
(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)
|
сортирует первые N элементов диапазона
(функциональный объект алгоритма) |
|
(C++20)
|
копирует и частично сортирует диапазон элементов
(функциональный объект алгоритма) |
|
(C++20)
|
сортирует диапазон элементов, сохраняя порядок между равными элементами
(объект-функция алгоритма) |
|
(C++20)
|
частично сортирует заданный диапазон, обеспечивая его разделение по заданному элементу
(функциональный объект алгоритма) |
Операции бинарного поиска (на отсортированных диапазонах) |
|
|
(C++20)
|
возвращает итератор на первый элемент
не меньший
заданного значения
(функциональный объект алгоритма) |
|
(C++20)
|
возвращает итератор на первый элемент
больший
определённого значения
(функциональный объект алгоритма) |
|
(C++20)
|
определяет, существует ли элемент в частично упорядоченном диапазоне
(функциональный объект алгоритма) |
|
(C++20)
|
возвращает диапазон элементов, соответствующих заданному ключу
(функциональный объект алгоритма) |
Операции над множествами (для отсортированных диапазонов) |
|
|
(C++20)
|
объединяет два отсортированных диапазона
(функциональный объект алгоритма) |
|
(C++20)
|
объединяет два упорядоченных диапазона на месте
(функциональный объект алгоритма) |
|
(C++20)
|
возвращает
true
если одна последовательность является подпоследовательностью другой
(функциональный объект алгоритма) |
|
(C++20)
|
вычисляет разность двух множеств
(функциональный объект алгоритма) |
|
(C++20)
|
вычисляет пересечение двух множеств
(функциональный объект алгоритма) |
|
(C++20)
|
вычисляет симметрическую разность двух множеств
(функциональный объект алгоритма) |
|
(C++20)
|
вычисляет объединение двух множеств
(функциональный объект алгоритма) |
Операции с кучей |
|
|
(C++20)
|
проверяет, является ли заданный диапазон максимальной кучей
(функциональный объект алгоритма) |
|
(C++20)
|
находит наибольший поддиапазон, который является max heap
(функциональный объект алгоритма) |
|
(C++20)
|
создает максимальную кучу из диапазона элементов
(функциональный объект алгоритма) |
|
(C++20)
|
добавляет элемент в максимальную кучу
(функциональный объект алгоритма) |
|
(C++20)
|
удаляет наибольший элемент из max heap
(объект-функция алгоритма) |
|
(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)
|
заполняет диапазон последовательными приращениями начального значения
(функциональный объект алгоритма) |
Ограниченные операции свертки
|
Определено в заголовке
<algorithm>
|
|
|
Определено в пространстве имён
std::ranges
|
|
|
(C++23)
|
левосторонняя свёртка диапазона элементов
(объект-функция алгоритма) |
|
(C++23)
|
левосторонняя свёртка диапазона элементов с использованием первого элемента в качестве начального значения
(объект-функция алгоритма) |
|
(C++23)
|
правосторонняя свёртка диапазона элементов
(объект-функция алгоритма) |
|
(C++23)
|
правосторонняя свёртка диапазона элементов с использованием последнего элемента в качестве начального значения
(объект-функция алгоритма) |
|
(C++23)
|
левосторонняя свёртка диапазона элементов и возврат
пары
(итератор, значение)
(объект-функция алгоритма) |
|
левосторонняя свёртка диапазона элементов с использованием первого элемента в качестве начального значения и возврат
пары
(итератор,
optional
)
(объект-функция алгоритма) |
|
Алгоритмы работы с неинициализированной памятью с ограничениями
|
Определено в заголовке
<memory>
|
|
|
Определено в пространстве имён
std::ranges
|
|
|
(C++20)
|
копирует диапазон объектов в неинициализированную область памяти
(объект-функция алгоритма) |
|
(C++20)
|
копирует указанное количество объектов в неинициализированную область памяти
(объект-функция алгоритма) |
|
(C++20)
|
копирует объект в неинициализированную область памяти, определённую диапазоном
(объект-функция алгоритма) |
|
(C++20)
|
копирует объект в неинициализированную область памяти, определённую началом и количеством
(объект-функция алгоритма) |
|
(C++20)
|
перемещает диапазон объектов в неинициализированную область памяти
(объект-функция алгоритма) |
|
(C++20)
|
перемещает указанное количество объектов в неинициализированную область памяти
(объект-функция алгоритма) |
|
конструирует объекты с помощью
default-initialization
в неинициализированной области памяти, определённой диапазоном
(объект-функция алгоритма) |
|
|
конструирует объекты с помощью
default-initialization
в неинициализированной области памяти, определённой началом и количеством
(объект-функция алгоритма) |
|
|
конструирует объекты с помощью
value-initialization
в неинициализированной области памяти, определённой диапазоном
(объект-функция алгоритма) |
|
|
конструирует объекты с помощью
value-initialization
в неинициализированной области памяти, определённой началом и количеством
(объект-функция алгоритма) |
|
|
(C++20)
|
уничтожает диапазон объектов
(объект-функция алгоритма) |
|
(C++20)
|
уничтожает указанное количество объектов в диапазоне
(объект-функция алгоритма) |
|
(C++20)
|
уничтожает объект по заданному адресу
(объект-функция алгоритма) |
|
(C++20)
|
создаёт объект по заданному адресу
(объект-функция алгоритма) |
Алгоритмы генерации случайных чисел с ограничениями
|
Определено в заголовке
<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_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 | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| P3136R1 | C++20 |
niebloids были разрешены к спецификации как специальные сущности
отличные от функциональных объектов |
требуется специфицировать как функциональные объекты |