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

 

C++

Поддержка компилятором

Автономные и размещённые реализации

Язык

Стандартная библиотека

Заголовки стандартной библиотеки

Требования к именованию

Макросы тестирования функциональности (C++20)

Поддержка языка

Библиотека концептов(C++20)

Библиотека метапрограммирования(C++11)

Библиотека диагностики

Библиотека общих утилит

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

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

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

Библиотека диапазонов(C++20)

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

Библиотека численных данных

Библиотека ввода/вывода

Библиотека локализаций

Регулярные выражения(C++11)

Атомарные операции(C++11)

Библиотека поддержки конкуренции(C++11)

Библиотека файловой системы(C++17)

Технические спецификации

Указатель символов

Внешние библиотеки

 

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

Концепты итераторов
indirectly_readable (C++20) indirectly_writable (C++20) weakly_incrementable (C++20) incrementable (C++20) input_or_output_iterator (C++20) sentinel_for (C++20) sized_sentinel_for (C++20)	input_iterator (C++20) output_iterator (C++20) forward_iterator (C++20) bidirectional_iterator (C++20) random_access_iterator (C++20) contiguous_iterator (C++20)
Примитивы итераторов
iterator_traits input_iterator_tagoutput_iterator_tagforward_iterator_tagbidirectional_iterator_tagrandom_access_iterator_tagcontiguous_iterator_tag (C++20) iterator (устарело в C++17)	incrementable_traits (C++20) indirectly_readable_traits (C++20) iter_value_titer_difference_titer_reference_titer_rvalue_reference_titer_common_reference_t (C++20)(C++20)(C++20)(C++20)(C++20)
Концепты алгоритмов и утилиты
Косвенно вызываемые концепты
indirectly_unary_invocableindirectly_regular_unary_invocable (C++20)(C++20)   indirect_unary_predicate (C++20)	indirect_binary_predicate (C++20) indirect_equivalence_relation (C++20) indirect_strict_weak_order (C++20)
Общие требования к алгоритмам
indirectly_movable (C++20) indirectly_movable_storable (C++20) indirectly_copyable (C++20) indirectly_copyable_storable (C++20)	indirectly_swappable (C++20) indirectly_comparable (C++20) permutable (C++20) mergeable (C++20) sortable (C++20)
Утилиты
indirect_result_t (C++20)	projected (C++20)
Адаптеры итераторов
reverse_iterator move_iterator (C++11) move_sentinel (C++20) common_iterator (C++20) counted_iterator (C++20) back_insert_iterator front_insert_iterator insert_iterator	make_reverse_iterator (C++14) make_move_iterator (C++11) default_sentinel_tdefault_sentinel (C++20)(C++20) unreachable_sentinel_tunreachable_sentinel (C++20)(C++20) back_inserter front_inserter inserter
Потоковые итераторы
istream_iterator ostream_iterator	istreambuf_iterator ostreambuf_iterator
Точки настройки итераторов
ranges::iter_move (C++20)
ranges::iter_swap (C++20)
Операции итераторов
advance distance prev (C++11) next (C++11)	ranges::advance (C++20) ranges::distance (C++20) ranges::prev (C++20) ranges::next (C++20)
Доступ к диапазону
begincbegin (C++11)(C++14) endcend (C++11)(C++14) sizessize (C++17)(C++20)	rbegincrbegin (C++14)(C++14) rendcrend (C++14)(C++14) empty (C++17) data (C++17)

 

Итераторы являются обобщением указателей, которые позволяют программе на C++ работать с различными структурами данных (например, с контейнерами и диапазонами(начиная с C++20)) единым образом. Библиотека итераторов предоставляет определения для итераторов, а также свойства итераторов, адаптеры и служебные функции.

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

Категории итераторов

Существует пять(до C++17)шесть(начиная с C++17) видов итераторов: LegacyInputIterator, LegacyOutputIterator, LegacyForwardIterator, LegacyBidirectionalIterator, LegacyRandomAccessIterator и LegacyContiguousIterator(начиная с C++17). (Смотрите также LegacyIterator , где описан самый базовый тип итератора.)

Вместо того, чтобы определяться конкретными типами, каждая категория итераторов определяется операциями, которые могут быть выполнены с нею. Это определение означает, что любой тип, поддерживающий необходимые операции, может использоваться в качестве итератора – например, указатель поддерживает все операции, требуемые для LegacyRandomAccessIterator, поэтому указатель можно использовать где угодно, где ожидается LegacyRandomAccessIterator.

Все категории итераторов (кроме LegacyOutputIterator) могут быть организованы в иерархию, где более мощные категории итераторов (например, LegacyRandomAccessIterator) поддерживают операции менее мощных категорий (например, LegacyInputIterator). Если итератор попадает в одну из этих категорий и также соответствует требованиям LegacyOutputIterator, то он называется изменяемым итератором и поддерживает ввод и вывод. Неизменяемые итераторы называются константными итераторами.

Итераторы называются constexpr итераторами если все операции, предусмотренные для соответствия требованиям категории итераторов, являются .

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

Категоря итератора	Требования к эксплуатации и хранению
	запись	чтение	инкремент		декремент	произвольный    доступ	непрерывное  хранилище
			без    нескольких    проходов	с    несколькими    проходами
LegacyIterator			Требует
LegacyOutputIterator	Требует		Требует
LegacyInputIterator (mutable, если поддерживает операцию записи)		Требует	Требует
LegacyForwardIterator (также соответствует LegacyInputIterator)		Требует	Требует	Требует
LegacyBidirectionalIterator (также соответствует LegacyForwardIterator)		Требует	Требует	Требует	Требует
LegacyRandomAccessIterator (также соответствует LegacyBidirectionalIterator)		Требует	Требует	Требует	Требует	Требует
LegacyContiguousIterator (также соответствует 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.

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

Для каждого типа итератора Xдля которого определено равенство(до C++20), существует соответствующий знаковый целочисленный(до C++20)целочисленно-подобный(начиная с C++20) тип, называемый разностным типом итератора.

Разыменовываемость и валидность

Точно так же, как обычный указатель на массив гарантирует наличие значения указателя, указывающего на элемент за последним элементом массива, так и для любого типа итератора существует значение итератора, указывающее на элемент за последним элементом соответствующего контейнера(до C++11)последовательности(начиная с C++11). Такое значение называется значением за концом.

Значения итератора i, для которых определено выражение *i называются разыменовываемыми. Стандартная библиотека никогда не предполагает, что значения за конечным значением могут быть разыменованы.

Итераторы также могут иметь единственные значения, не связанные ни с каким контейнером(до C++11)последовательностью(начиная с C++11). Результаты большинства выражений не определены для единственных значений; с единственными исключениями

• присваивание неединственного значения итератору, который содержит единственное значение,
• уничтожение итератора, который содержит единственное значение, и,

для итераторов, отвечающих требованиям DefaultConstructible, используя итератор,инициализированный значением, в качестве источника операции копирования или перемещения(начиная с C++11).

(начиная с 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 (концепт)
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 является непрерывным итератором, ссылающимся на смежные элементы памяти (концепт)

Типы, связанные с итераторами

Определены в пространстве имён 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)	базовый класс для упрощения определения требуемых типов для простых итераторов (шаблон класса)

Точки настройки итераторов

Определены в пространстве имён std::ranges
iter_move (C++20)	приводит результат разыменования объекта к связанному с ним типу правосторонней ссылки (объект точки настройки)
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)	вспомогательный шаблон для определения ограничений для алгоритмов, принимающих прогнозы (шаблон класса)

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

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)	вычисляет тип ограничителя, который будет использоваться с константными итераторами (псевдоним шаблона)
make_const_iterator (C++23)	создаёт std::const_iterator типа, полученного из аргумента (шаблон функции)
make_const_sentinel (C++23)	создаёт std::const_sentinel типа, выведенного из аргумента (шаблон функции)
move_iterator (C++11)	адаптер итератора, который разыменовывается в правостороннюю ссылку (шаблон класса)
move_sentinel (C++20)	адаптер ограничитель для использования с std::move_iterator (шаблон класса)
make_move_iterator (C++11)	создаёт std::move_iterator типа, выведенного из аргумента (шаблон функции)
common_iterator (C++20)	адаптирует тип итератора и его ограничителя к общему типу итератора (шаблон класса)
default_sentinel_t (C++20)	ограничитель по умолчанию для использования с итераторами, которые знают границу своего диапазона (класс)
counted_iterator (C++20)	адаптер итератора, отслеживающий расстояние до конца диапазона (шаблон класса)
unreachable_sentinel_t (C++20)	ограничитель, который всегда сравнивает на неравенство с любым типом 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)	возвращает расстояние между итератором и ограничителем или между началом и концом диапазона (ниблоид)
ranges::next (C++20)	инкрементирует итератор на заданное расстояние или до границы (ниблоид)
ranges::prev (C++20)	декрементирует итератор на заданное расстояние или до границы (ниблоид)

Доступ к диапазону

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

Определены в заголовочном файле <array>
Определены в заголовочном файле <deque>
Определены в заголовочном файле <forward_list>
Определены в заголовочном файле <iterator>
Определены в заголовочном файле <list>
Определены в заголовочном файле <map>
Определены в заголовочном файле <regex>
Определены в заголовочном файле <set>
Определены в заголовочном файле <span>
Определены в заголовочном файле <string>
Определены в заголовочном файле <string_view>
Определены в заголовочном файле <unordered_map>
Определены в заголовочном файле <unordered_set>
Определены в заголовочном файле <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++:

Номер	Применён	Поведение в стандарте	Корректное поведение
CWG 1181	C++98	типы массивов не могут быть типами значений	могут
LWG 208	C++98	итераторы за концом всегда были неособыми	они могут быть особыми
LWG 278	C++98	допустимость итератора не была определена	определяется как всегда неособый
LWG 324	C++98	выходные итераторы имели типы значений	вместо этого выходные итераторы имеют перезаписываемые типы
LWG 407	C++98	особые итераторы не могли быть уничтожены	позволено
LWG 408	C++98	особые итераторы не могли быть скопированы	разрешено, если они инициализированы значением
LWG 1185	C++98	LegacyForwardIterator, LegacyBidirectionalIterator и LegacyRandomAccessIterator всегда соответствуют LegacyOutputIterator	они могут не соответствовать LegacyOutputIterator
LWG 1210	C++98	определение сингулярности и достижимости итератора зависело от контейнеров	вместо этого зависит от последовательностей