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

Итераторы — это обобщение указателей, позволяющее программе на 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).

В этих случаях сингулярное значение перезаписывается так же, как любое другое значение. Разыменовываемые значения всегда являются несингулярными.

Недействительный итератор — это итератор, который может быть сингулярным.

Диапазоны

Большинство шаблонов алгоритмов стандартной библиотеки, работающих со структурами данных, имеют интерфейсы, использующие диапазоны.

Итератор j называется достижимым из итератора i тогда и только тогда, когда существует конечная последовательность применений выражения ++i, приводящая к i == j. Если j достижим из i, они относятся к элементам одной и той же последовательности.

Диапазон — это пара итераторов, обозначающих начало и конец вычисления. Диапазон [i, i) является пустым; в общем случае диапазон [i, j) относится к элементам структуры данных, начиная с элемента, на который указывает i, и заканчивая, не включая его, элементом, на который указывает j.

Диапазон [i, j) является корректным тогда и только тогда, когда j достижим из i.

(до C++20)

Диапазон может быть представлен одним из следующих способов:

[i, s) — итератором i и сторожевым значением s, обозначающими начало и конец вычисления (i и s могут иметь разные типы); или
i + [0, n) — итератором i и количеством n, обозначающими начало и число элементов, к которым следует применить вычисление.

Диапазон «итератор — сторожевое значение»

Итератор и сторожевое значение, обозначающие диапазон, можно сравнивать. [i, s) является пустым, если i == s; в противном случае [i, s) относится к элементам структуры данных, начиная с элемента, на который указывает i, и заканчивая, не включая его, элементом (если он существует), на который указывает первый итератор j, такой что j == s.

Сторожевое значение s называется достижимым из итератора i тогда и только тогда, когда существует конечная последовательность применений выражения ++i, приводящая к i == s.

Если s достижимо из i, [i, s) обозначает корректный диапазон.

Диапазон с заданным количеством элементов

Диапазон с заданным количеством элементов i + [0, n) является пустым, если n == 0; в противном случае i + [0, n) относится к n элементам структуры данных, начиная с элемента, на который указывает i, и заканчивая, не включая его, элементом (если он существует), на который указывает результат n применений ++i.

Диапазон с заданным количеством элементов i + [0, n) является корректным тогда и только тогда, когда

n == 0; или
выполняются все следующие условия:
- n является положительным числом,
- i является разыменовываемым, и
- ++i + [0, --n) является корректным.

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

Результат применения функций стандартной библиотеки к некорректным диапазонам не определён.

Концепты итераторов (начиная с C++20)

Новая система итераторов основана на концептах, отличающихся от итераторов C++17. Хотя основная классификация осталась похожей, требования к отдельным категориям итераторов несколько изменились.

Определено в пространстве имён `std`
indirectly_readable (C++20)	задаёт требования к типу, косвенно читаемому с помощью оператора `*` (концепт)
indirectly_writable (C++20)	задаёт требования, согласно которым значение можно записать в объект, на который ссылается итератор (концепт)
weakly_incrementable (C++20)	задаёт требования, согласно которым тип `semiregular` можно инкрементировать с помощью операторов префиксного и постфиксного инкремента (концепт)
incrementable (C++20)	задаёт требования, согласно которым операция инкремента для типа `weakly_incrementable` сохраняет равенство, а сам тип является `equality_comparable` (концепт)
is-integer-likeis-signed-integer-like (C++20)(C++20)	задаёт требования, согласно которым тип ведёт себя как (знаковый) целочисленный тип (концепт, используемый только для описания*)
input_or_output_iterator (C++20)	задаёт требования, согласно которым объекты типа можно инкрементировать и разыменовывать (концепт)
sentinel_for (C++20)	задаёт требования, согласно которым тип является сторожевым значением для типа `input_or_output_iterator` (концепт)
sized_sentinel_for (C++20)	задаёт требования, согласно которым оператор `-` можно применить к итератору и сторожевому значению для вычисления их разности за постоянное время (концепт)
input_iterator (C++20)	задаёт требования, согласно которым тип является итератором ввода, то есть значения, на которые он ссылается, можно читать, а сам итератор можно инкрементировать как префиксным, так и постфиксным оператором (концепт)
output_iterator (C++20)	задаёт требования, согласно которым тип является итератором вывода для заданного типа значения, то есть значения этого типа можно записывать через него, а сам итератор можно инкрементировать как префиксным, так и постфиксным оператором (концепт)
forward_iterator (C++20)	задаёт требования, согласно которым `input_iterator` является итератором прямого хода, поддерживающим сравнение на равенство и многократный проход (концепт)
bidirectional_iterator (C++20)	задаёт требования, согласно которым `forward_iterator` является двунаправленным итератором, поддерживающим перемещение назад (концепт)
random_access_iterator (C++20)	задаёт требования, согласно которым `bidirectional_iterator` является итератором произвольного доступа, поддерживающим перемещение за постоянное время и индексирование (концепт)
contiguous_iterator (C++20)	задаёт требования, согласно которым `random_access_iterator` является непрерывным итератором, указывающим на элементы, расположенные в памяти непрерывно (концепт)

Связанные типы итераторов (начиная с C++20)

Определено в пространстве имён `std`
incrementable_traits (C++20)	вычисляет тип разности типа `weakly_incrementable` (шаблон класса)
indirectly_readable_traits (C++20)	вычисляет тип значения типа `indirectly_readable` (шаблон класса)
iter_value_titer_reference_titer_const_reference_titer_difference_titer_rvalue_reference_titer_common_reference_t (C++20)(C++20)(C++23)(C++20)(C++20)(C++20)	вычисляет связанные типы итератора (шаблон псевдонима)

Примитивы итераторов

iterator_traits	предоставляет единый интерфейс к свойствам итератора (шаблон класса)
input_iterator_tagoutput_iterator_tagforward_iterator_tagbidirectional_iterator_tagrandom_access_iterator_tagcontiguous_iterator_tag (C++20)	пустые типы классов, используемые для обозначения категорий итераторов (класс)
iterator (устарел в C++17)	базовый класс, упрощающий определение необходимых типов для простых итераторов (шаблон класса)

Точки настройки итераторов (начиная с C++20)

Определено в пространстве имён `std::ranges`
ranges::iter_move (C++20)	преобразует результат разыменования объекта в соответствующий тип rvalue-ссылки (объект точки настройки)
ranges::iter_swap (C++20)	меняет местами значения, на которые ссылаются два разыменовываемых объекта (объект точки настройки)

Концепты и вспомогательные средства алгоритмов (начиная с C++20)

Набор концептов и связанных с ними вспомогательных шаблонов, предназначенных для упрощения задания ограничений на распространённые операции алгоритмов.

Определено в заголовочном файле `<iterator>`
Определено в пространстве имён `std`
Косвенные вызываемые концепции
indirectly_unary_invocableindirectly_regular_unary_invocable (C++20)(C++20)	задаёт требование, согласно которому вызываемый тип можно вызвать с результатом разыменования типа `indirectly_readable` (концепция)
indirect_unary_predicate (C++20)	задаёт требование, согласно которому вызываемый тип при вызове с результатом разыменования типа `indirectly_readable` удовлетворяет требованиям `predicate` (концепция)
indirect_binary_predicate (C++20)	задаёт требование, согласно которому вызываемый тип при вызове с результатами разыменования двух типов `indirectly_readable` удовлетворяет требованиям `predicate` (концепция)
indirect_equivalence_relation (C++20)	задаёт требование, согласно которому вызываемый тип при вызове с результатами разыменования двух типов `indirectly_readable` удовлетворяет требованиям `equivalence_relation` (концепция)
indirect_strict_weak_order (C++20)	задаёт требование, согласно которому вызываемый тип при вызове с результатами разыменования двух типов `indirectly_readable` удовлетворяет требованиям `strict_weak_order` (концепция)
Общие требования к алгоритмам
indirectly_movable (C++20)	задаёт требование, согласно которому значения можно перемещать из типа `indirectly_readable` в тип `indirectly_writable` (концепция)
indirectly_movable_storable (C++20)	задаёт требование, согласно которому значения можно перемещать из типа `indirectly_readable` в тип `indirectly_writable`, причём перемещение может выполняться через промежуточный объект (концепция)
indirectly_copyable (C++20)	задаёт требование, согласно которому значения можно копировать из типа `indirectly_readable` в тип `indirectly_writable` (концепция)
indirectly_copyable_storable (C++20)	задаёт требование, согласно которому значения можно копировать из типа `indirectly_readable` в тип `indirectly_writable`, причём копирование может выполняться через промежуточный объект (концепция)
indirectly_swappable (C++20)	задаёт требование, согласно которому значения, на которые ссылаются два типа `indirectly_readable`, можно обменять местами (концепция)
indirectly_comparable (C++20)	задаёт требование, согласно которому значения, на которые ссылаются два типа `indirectly_readable`, можно сравнивать (концепция)
permutable (C++20)	задаёт общие требования к алгоритмам, переставляющим элементы на месте (концепция)
mergeable (C++20)	задаёт требования к алгоритмам, объединяющим отсортированные последовательности в выходную последовательность путём копирования элементов (концепция)
sortable (C++20)	задаёт общие требования к алгоритмам, преобразующим последовательности в упорядоченные последовательности путём перестановки элементов (концепция)
Утилиты
indirect_result_t (C++20)	вычисляет результат вызова вызываемого объекта с результатами разыменования некоторого набора типов `indirectly_readable` (шаблон псевдонима)
projected (C++20)	вспомогательный шаблон для задания ограничений алгоритмов, принимающих проекции (шаблон класса)
projected_value_t (C++26)	вычисляет тип значения типа `indirectly_readable` посредством проекции (шаблон псевдонима)

Адаптеры итераторов

reverse_iterator	адаптер итератора для обхода в обратном порядке (шаблон класса)
make_reverse_iterator (C++14)	создаёт `std::reverse_iterator` типа, выводимого из аргумента (шаблон функции)
back_insert_iterator	адаптер итератора для вставки в конец контейнера (шаблон класса)
back_inserter	создаёт `std::back_insert_iterator` типа, выводимого из аргумента (шаблон функции)
front_insert_iterator	адаптер итератора для вставки в начало контейнера (шаблон класса)
front_inserter	создаёт `std::front_insert_iterator` типа, выводимого из аргумента (шаблон функции)
insert_iterator	адаптер итератора для вставки в контейнер (шаблон класса)
inserter	создаёт `std::insert_iterator` типа, выводимого из аргумента (шаблон функции)
basic_const_iterator (C++23)	адаптер итератора, преобразующий итератор в константный итератор (шаблон класса)
const_iterator (C++23)	вычисляет тип константного итератора для заданного типа (шаблон псевдонима)
const_sentinel (C++23)	вычисляет тип sentinel, используемый с константными итераторами (шаблон псевдонима)
make_const_iterator (C++23)	создаёт `std::const_iterator` типа, выводимого из аргумента (шаблон функции)
make_const_sentinel (C++23)	создаёт `std::const_sentinel` типа, выводимого из аргумента (шаблон функции)
move_iterator (C++11)	адаптер итератора, разыменование которого даёт rvalue (шаблон класса)
move_sentinel (C++20)	адаптер sentinel для `std::move_iterator` (шаблон класса)
make_move_iterator (C++11)	создаёт `std::move_iterator` типа, выводимого из аргумента (шаблон функции)
common_iterator (C++20)	адаптирует тип итератора и его sentinel к общему типу итератора (шаблон класса)
default_sentinel_t (C++20)	sentinel по умолчанию для итераторов, знающих границу своего диапазона (класс)
counted_iterator (C++20)	адаптер итератора, отслеживающий расстояние до конца диапазона (шаблон класса)
unreachable_sentinel_t (C++20)	sentinel, который всегда сравнивается неравным с любым типом `weakly_incrementable` (класс)

Потоковые итераторы

istream_iterator	входной итератор, считывающий данные из `std::basic_istream` (шаблон класса)
ostream_iterator	выходной итератор, записывающий данные в `std::basic_ostream` (шаблон класса)
istreambuf_iterator	входной итератор, считывающий данные из `std::basic_streambuf` (шаблон класса)
ostreambuf_iterator	выходной итератор, записывающий данные в `std::basic_streambuf` (шаблон класса)

Операции с итераторами

Определено в заголовочном файле `<iterator>`
advance	перемещает итератор на заданное расстояние (шаблон функции)
distance	возвращает расстояние между двумя итераторами (шаблон функции)
next (C++11)	увеличивает итератор (шаблон функции)
prev (C++11)	уменьшает итератор (шаблон функции)
ranges::advance (C++20)	перемещает итератор на заданное расстояние или до заданной границы (функциональный объект алгоритма)
ranges::distance (C++20)	возвращает расстояние между итератором и sentinel либо между началом и концом диапазона (функциональный объект алгоритма)
ranges::next (C++20)	увеличивает итератор на заданное расстояние или до заданной границы (функциональный объект алгоритма)
ranges::prev (C++20)	уменьшает итератор на заданное расстояние или до заданной границы (функциональный объект алгоритма)

Доступ к диапазону (начиная с C++11)

Эти шаблоны функций, не являющихся членами класса, предоставляют универсальный интерфейс для контейнеров, обычных массивов и std::initializer_list.

Определено в заголовочном файле `<array>`
Определено в заголовочном файле `<deque>`
Определено в заголовочном файле `<flat_map>`		(начиная с C++23)
Определено в заголовочном файле `<flat_set>`		(начиная с C++23)
Определено в заголовочном файле `<forward_list>`
Определено в заголовочном файле `<hive>`		(начиная с C++26)
Определено в заголовочном файле `<inplace_vector>`		(начиная с C++26)
Определено в заголовочном файле `<iterator>`
Определено в заголовочном файле `<list>`
Определено в заголовочном файле `<map>`
Определено в заголовочном файле `<optional>`		(начиная с C++26)
Определено в заголовочном файле `<regex>`
Определено в заголовочном файле `<set>`
Определено в заголовочном файле `<span>`		(начиная с C++20)
Определено в заголовочном файле `<stacktrace>`		(начиная с C++23)
Определено в заголовочном файле `<string>`
Определено в заголовочном файле `<string_view>`		(начиная с C++17)
Определено в заголовочном файле `<unordered_map>`
Определено в заголовочном файле `<unordered_set>`
Определено в заголовочном файле `<valarray>`
Определено в заголовочном файле `<vector>`

Определено в пространстве имён `std`
begincbegin (C++11)(C++14)	возвращает итератор на начало контейнера или массива (шаблон функции)
endcend (C++11)(C++14)	возвращает итератор на конец контейнера или массива (шаблон функции)
rbegincrbegin (C++14)	возвращает обратный итератор на начало контейнера или массива (шаблон функции)
rendcrend (C++14)	возвращает обратный итератор конца контейнера или массива (шаблон функции)
sizessize (C++17)(C++20)	возвращает размер контейнера или массива (шаблон функции)
empty (C++17)	проверяет, пуст ли контейнер (шаблон функции)
data (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	определение сингулярности и достижимости итераторов зависело от контейнеров	вместо этого зависит от последовательностей
LWG 3009	C++17	`<string_view>` не предоставлял шаблоны функций доступа к диапазонам	предоставляет эти шаблоны
LWG 3987	C++23	`<flat_map>` и `<flat_set>` не предоставляли шаблоны функций доступа к диапазонам	предоставляют эти шаблоны

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/iterator