Библиотека итераторов
Итераторы являются обобщением указателей, позволяя C++-программе работать с различными структурами данных (например, контейнерами и диапазонами(с C++20)) единообразно. Библиотека итераторов предоставляет определения для итераторов, а также свойства итераторов, адаптеры и вспомогательные функции.
Поскольку итераторы являются абстракцией указателей, их семантика является обобщением большей части семантики указателей в C++. Это гарантирует, что каждый шаблон функции, принимающий итераторы, работает также с обычными указателями.
Категории итераторов
Существует пять(до C++17)шесть(с C++17) типов итераторов: LegacyInputIterator, LegacyOutputIterator, LegacyForwardIterator, LegacyBidirectionalIterator, LegacyRandomAccessIterator, и LegacyContiguousIterator(с C++17). (См. также LegacyIterator для самого основного типа итератора.)
Вместо определения конкретными типами, каждая категория итераторов определяется операциями, которые могут быть выполнены над ними. Это определение означает, что любой тип, поддерживающий необходимые операции, может быть использован как итератор — например, указатель поддерживает все операции, необходимые для LegacyRandomAccessIterator, поэтому указатель может быть использован везде, где ожидается LegacyRandomAccessIterator.
Все категории итераторов (кроме LegacyOutputIterator) могут быть организованы в иерархию, где более мощные категории итераторов (например, LegacyRandomAccessIterator) поддерживают операции менее мощных категорий (например, LegacyInputIterator). Если итератор попадает в одну из этих категорий и также удовлетворяет требованиям LegacyOutputIterator, то он называется изменяемым итератором и поддерживает обе операции ввода и вывода. Неизменяемые итераторы называются постоянными итераторами.
| Итераторы называются constexpr итераторами, если все операции, необходимые для выполнения требований категории итератора, являются constexpr-функциями. | (с C++20) |
| Категория итератора | Операции и требования к хранению | ||||||
|---|---|---|---|---|---|---|---|
| запись | чтение | инкремент | декремент | случайный доступ | непрерывное хранение |
||
| без многократных проходов | с многократными проходами |
||||||
| LegacyIterator | Требуется | ||||||
| LegacyOutputIterator | Требуется | Требуется | |||||
|
LegacyInputIterator (изменяемый, если поддерживает операцию записи) | Требуется | Требуется | |||||
|
LegacyForwardIterator (также удовлетворяет LegacyInputIterator) | Требуется | Требуется | Требуется | ||||
|
LegacyBidirectionalIterator (также удовлетворяет LegacyForwardIterator) | Требуется | Требуется | Требуется | Требуется | |||
|
LegacyRandomAccessIterator (также удовлетворяет LegacyBidirectionalIterator) | Требуется | Требуется | Требуется | Требуется | Требуется | ||
| LegacyContiguousIterator[1] (также удовлетворяет LegacyRandomAccessIterator) | Требуется | Требуется | Требуется | Требуется | Требуется | Требуется | |
- LegacyContiguousIterator категория была формально определена только в C++17, но итераторы
std::vector,std::basic_string,std::array, иstd::valarray, а также указатели в массивы C часто рассматриваются как отдельная категория в коде до C++17.
Примечание: Тип, поддерживающий необходимые операции в строке таблицы выше, не обязательно относится к соответствующей категории, см. страницу категории для полного списка требований.
Определения
Типы и возможность записи
Вводной итератор i поддерживает выражение *i, что приводит к значению некоторого типа объекта T, называемого типом значения итератора.
У выходного итератора i есть непустой набор типов, которые являются записываемыми(до C++20)indirectly_writable(с C++20) для итератора; для каждого такого типа T, выражение *i = o является допустимым, где o является значением типа T.
Для каждого типа итератора X для которого определено равенство(до C++20), существует соответствующий знаковый целый тип(до C++20)целочисленный тип(с C++20), называемый типом разницы итератора.
Возможность разыменования и валидность
Так же, как указатель на массив гарантирует, что существует значение указателя, указывающее за последним элементом массива, так и для любого типа итератора существует значение итератора, указывающее за последним элементом соответствующей последовательности. Такое значение называется значением за концом.
Значения итератора i для которых определено выражение *i называются разыменовываемыми. Стандартная библиотека никогда не предполагает, что значения за концом разыменовываются.
Итераторы также могут иметь сингулярные значения, не связанные ни с какой последовательностью. Результаты большинства выражений неопределены для сингулярных значений; исключениями являются:
- присвоение ненулевого значения итератору, содержащему сингулярное значение,
- удаление итератора, содержащего сингулярное значение, и
- для итераторов, удовлетворяющих требованиям DefaultConstructible, использование итератора с инициализированным значением в качестве источника операции копирования или перемещения(с C++11).
В этих случаях сингулярное значение перезаписывается так же, как и любое другое значение. Разыменовываемые значения всегда несингулярны.
Недействительный итератор — это итератор, который может быть сингулярным.
Диапазоны
Большинство алгоритмических шаблонов стандартной библиотеки, работающих со структурами данных, имеют интерфейсы, использующие диапазоны.
END_OF_DOCUMENT_MARKER| Итератор Диапазон — это пара итераторов, которые обозначают начало и конец вычисления. Диапазон Диапазон | (до C++20) |
| Диапазон — это либо
Сравнимый диапазонИтератор и граничный итератор, обозначающие диапазон, сравнимы. Диапазон Граничный итератор Если Счётный диапазонСчётный диапазон Счётный диапазон
| (с C++20) |
Результат применения функций стандартной библиотеки к недействительным диапазонам не определён.
Концепции итераторов (с C++20)
Новая система итераторов, основанная на концепциях, отличающихся от итераторов C++17. Хотя базовая таксономия остаётся аналогичной, требования к отдельным категориям итераторов несколько отличаются.
Определено в пространстве имен std |
|
|---|---|
|
(C++20) | указывает, что тип может быть косвенно прочитан путём применения оператора * (концепция) |
|
(C++20) | указывает, что значение может быть записано в объект, на который ссылается итератор (концепция) |
|
(C++20) | указывает, что тип, являющийся semiregular, может быть инкрементирован с помощью префиксных и постфиксных операторов инкремента (концепция) |
|
(C++20) | указывает, что операция инкремента над типом weakly_incrementable является сохраняющей равенство и что тип является equality_comparable (концепция) |
|
(C++20) | указывает, что объекты данного типа могут быть инкрементированы и разыменованы (концепция) |
|
(C++20) | указывает, что тип является меткой-пределом для типа input_or_output_iterator (концепция) |
|
(C++20) | указывает, что оператор - может быть применён к итератору и метке-пределу для вычисления их разницы за константное время (концепция) |
|
(C++20) | указывает, что тип является итератором ввода, то есть его ссылочные значения могут быть прочитаны, и он может быть инкрементирован как префиксным, так и постфиксным оператором инкремента (концепция) |
|
(C++20) | указывает, что тип является итератором вывода для заданного типа значения, то есть значения этого типа могут быть в него записаны, и он может быть инкрементирован как префиксным, так и постфиксным оператором инкремента (концепция) |
|
(C++20) | указывает, что input_iterator является итератором прямого доступа, поддерживающим сравнение на равенство и многократное применение (концепция) |
|
(C++20) | указывает, что forward_iterator является двунаправленным итератором, поддерживающим обратное движение (концепция) |
|
(C++20) | указывает, что bidirectional_iterator является итератором произвольного доступа, поддерживающим продвижение за константное время и индексирование (концепция) |
|
(C++20) | указывает, что random_access_iterator является смежным итератором, ссылающимся на элементы, расположенные смежно в памяти (концепция) |
Типы, связанные с итераторами
Определено в пространстве имен std |
|
|---|---|
|
(C++20) | вычисляет тип разности для типа weakly_incrementable (шаблон класса) |
|
(C++20) | вычисляет тип значения для типа indirectly_readable (шаблон класса) |
|
(C++20)(C++20)(C++23)(C++20)(C++20)(C++20) | вычисляет связанные типы итератора (шаблон псевдонима) |
Примитивы итераторов
| предоставляет унифицированный интерфейс к свойствам итератора (шаблон класса) |
|
|
(C++20) | пустые типы классов, используемые для обозначения категорий итераторов (класс) |
|
(устарело в C++17) | базовый класс для облегчения определения необходимых типов для простых итераторов (шаблон класса) |
Точки кастомизации итераторов
Определено в пространстве имен std::ranges |
|
|---|---|
|
(C++20) | преобразует результат разыменования объекта в соответствующий тип rvalue ссылки (объект точки кастомизации) |
|
(C++20) | меняет местами значения, на которые ссылаются два разыменовываемых объекта (объект точки кастомизации) |
Концепции и утилиты алгоритмов (с C++20)
Набор концепций и связанных шаблонов утилит, разработанных для облегчения ограничения общих операций алгоритмов.
END_OF_DOCUMENT_MARKER Определено в заголовке <iterator> |
|
|---|---|
Определено в пространстве имён std |
|
Концепции косвенно вызываемых объектов |
|
|
(C++20)(C++20) | указывает, что тип вызываемого объекта может быть вызван с результатом обращение к элементу типа indirectly_readable (концепция) |
|
(C++20) | указывает, что тип вызываемого объекта, при вызове с результатом обращения к элементу типа indirectly_readable, удовлетворяет predicate (концепция) |
|
(C++20) | указывает, что тип вызываемого объекта, при вызове с результатом обращения к двум элементам типа indirectly_readable, удовлетворяет predicate (концепция) |
|
(C++20) | указывает, что тип вызываемого объекта, при вызове с результатом обращения к двум элементам типа indirectly_readable, удовлетворяет equivalence_relation (концепция) |
|
(C++20) | указывает, что тип вызываемого объекта, при вызове с результатом обращения к двум элементам типа indirectly_readable, удовлетворяет strict_weak_order (концепция) |
Общие требования к алгоритмам |
|
|
(C++20) | указывает, что значения можно перемещать из типа indirectly_readable в тип indirectly_writable (концепция) |
|
(C++20) | указывает, что значения можно перемещать из типа indirectly_readable в тип indirectly_writable, и что перемещение может выполняться через промежуточный объект (концепция) |
|
(C++20) | указывает, что значения можно копировать из типа indirectly_readable в тип indirectly_writable (концепция) |
|
(C++20) | указывает, что значения можно копировать из типа indirectly_readable в тип indirectly_writable, и что копирование может выполняться через промежуточный объект (концепция) |
|
(C++20) | указывает, что значения, на которые ссылаются два типа indirectly_readable, могут быть поменяны местами (концепция) |
|
(C++20) | указывает, что значения, на которые ссылаются два типа indirectly_readable, могут быть сравнены (концепция) |
|
(C++20) | определяет общие требования к алгоритмам, которые переупорядочивают элементы на месте (концепция) |
|
(C++20) | определяет требования к алгоритмам, которые объединяют отсортированные последовательности в выходную последовательность путем копирования элементов (концепция) |
|
(C++20) | определяет общие требования к алгоритмам, которые переупорядочивают последовательности в отсортированные последовательности (концепция) |
Утилиты |
|
|
(C++20) | вычисляет результат вызова вызываемого объекта по результату обращения к элементу одного из наборов типов indirectly_readable(псевдоним шаблона) |
|
(C++20) | вспомогательный шаблон для указания ограничений на алгоритмы, принимающие проекции (шаблон класса) |
Адаптеры итераторов
| адаптер итератора для обхода в обратном порядке (шаблон класса) |
|
|
(C++14) | создаёт std::reverse_iterator типа, определяемого из аргумента (шаблон функции) |
| адаптер итератора для вставки в конец контейнера (шаблон класса) |
|
создаёт std::back_insert_iterator типа, определяемого из аргумента (шаблон функции) |
|
| адаптер итератора для вставки в начало контейнера (шаблон класса) |
|
создаёт std::front_insert_iterator типа, определяемого из аргумента (шаблон функции) |
|
| адаптер итератора для вставки в контейнер (шаблон класса) |
|
создаёт std::insert_iterator типа, определяемого из аргумента (шаблон функции) |
|
|
(C++23) | адаптер итератора, преобразующий итератор в константный итератор (шаблон класса) |
|
(C++23) | вычисляет тип константного итератора для заданного типа (шаблон псевдонима) |
|
(C++23) | вычисляет тип сторожевого элемента для использования с константными итераторами (шаблон псевдонима) |
|
(C++23) | создаёт std::const_iterator типа, определяемого из аргумента (шаблон функции) |
|
(C++23) | создаёт std::const_sentinel типа, определяемого из аргумента (шаблон функции) |
|
(C++11) | адаптер итератора, который обращается к ссылке на rvalue (шаблон класса) |
|
(C++20) | адаптер сторожевого элемента для использования с std::move_iterator (шаблон класса) |
|
(C++11) | создаёт std::move_iterator типа, определяемого из аргумента (шаблон функции) |
|
(C++20) | адаптирует тип итератора и его сторожевой элемент в общий тип итератора (шаблон класса) |
|
(C++20) | по умолчанию сторожевой элемент для использования с итераторами, знающими границы своего диапазона (класс) |
|
(C++20) | адаптер итератора, отслеживающий расстояние до конца диапазона (шаблон класса) |
|
(C++20) | сторожевой элемент, который всегда сравнивается как неравный с любым типом weakly_incrementable (класс) |
Потоковые итераторы
входной итератор, считывающий из std::basic_istream (шаблон класса) |
|
выходной итератор, записывающий в std::basic_ostream (шаблон класса) |
|
входной итератор, считывающий из std::basic_streambuf (шаблон класса) |
|
выходной итератор, записывающий в std::basic_streambuf (шаблон класса) |
Операции с итераторами
Определено в заголовке <iterator> |
|
|---|---|
| смещает итератор на заданное расстояние (шаблон функции) |
|
| возвращает расстояние между двумя итераторами (шаблон функции) |
|
|
(C++11) | инкрементирует итератор (шаблон функции) |
|
(C++11) | декрементирует итератор (шаблон функции) |
|
(C++20) | смещает итератор на заданное расстояние или до заданной границы (niebloid) |
|
(C++20) | возвращает расстояние между итератором и сенсорным значением, или между началом и концом диапазона (niebloid) |
|
(C++20) | инкрементирует итератор на заданное расстояние или до границы (niebloid) |
|
(C++20) | декрементирует итератор на заданное расстояние или до границы (niebloid) |
Доступ к диапазону
Эти функции, не являющиеся членами, обеспечивают общий интерфейс для контейнеров, обычных массивов и std::initializer_list.
Определено в заголовке <array> |
|
|---|---|
Определено в заголовке <deque> |
|
Определено в заголовке <forward_list> |
|
Определено в заголовке <iterator> |
|
Определено в заголовке <list> |
|
Определено в заголовке <map> |
|
Определено в заголовке <regex> |
|
Определено в заголовке <set> |
|
Определено в заголовке <span> |
|
Определено в заголовке <string> |
|
Определено в заголовке <string_view> |
|
Определено в заголовке <unordered_map> |
|
Определено в заголовке <unordered_set> |
|
Определено в заголовке <vector> |
|
Определено в пространстве имен std |
|
|
(C++11)(C++14) | возвращает итератор в начало контейнера или массива (шаблон функции) |
|
(C++11)(C++14) | возвращает итератор в конец контейнера или массива (шаблон функции) |
|
(C++14) | возвращает обратный итератор в начало контейнера или массива (шаблон функции) |
|
(C++14) | возвращает обратный итератор в конец контейнера или массива (шаблон функции) |
|
(C++17)(C++20) | возвращает размер контейнера или массива (шаблон функции) |
|
(C++17) | проверяет, пуст ли контейнер (шаблон функции) |
|
(C++17) | получает указатель на базовый массив (шаблон функции) |
Отчеты об ошибках
Следующие отчеты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.
| DR | Применено к | Поведение, как опубликовано | Корректное поведение |
|---|---|---|---|
| CWG 1181 | C++98 | типы массивов не могли быть типами значений | они могут |
| LWG 208 | C++98 | итераторы за концом всегда были несингулярными | они могут быть сингулярными |
| LWG 278 | C++98 | действительность итератора не была определена | определена как всегда несингулярная |
| LWG 324 | C++98 | типы значений итераторов вывода | итераторы вывода вместо этого имеют типы для записи |
| LWG 407 | C++98 | сингулярные итераторы не могли быть уничтожены | разрешено |
|
LWG 408 (N3066) | C++98 | сингулярные итераторы не могли быть скопированы | разрешено, если они инициализированы значением |
|
LWG 1185 (N3066) | C++98 |
LegacyForwardIterator, LegacyBidirectionalIterator и LegacyRandomAccessIterator всегда удовлетворяют LegacyOutputIterator | они могут не удовлетворять LegacyOutputIterator |
|
LWG 1210 (N3066) | C++98 | определение сингулярности итератора и достижимости зависели от контейнеров | зависит от последовательностей |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/iterator
