Namespaces
Variants

Iterator library

From cppreference.net
C++
Iterator library
Iterator concepts
Iterator primitives
Algorithm concepts and utilities
Indirect callable concepts
Common algorithm requirements
(C++20)
(C++20)
(C++20)
Utilities
(C++20)
Iterator adaptors
Range access
(C++11) (C++14)
(C++14) (C++14)
(C++11) (C++14)
(C++14) (C++14)
(C++17) (C++20)
(C++17)
(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 итераторами, если все операции, предоставляемые для соответствия требованиям категории итераторов, являются constexpr-функциями .

(since C++20)
Категория итератора Операции и требования к хранению
запись чтение инкремент декремент произвольный
доступ 		непрерывное
хранение
без
многократных
проходов 		с
многократными
проходами
LegacyIterator Требуется
LegacyOutputIterator Требуется Требуется
LegacyInputIterator
(изменяемый, если поддерживает операцию записи) 		Требуется Требуется
LegacyForwardIterator
(также удовлетворяет LegacyInputIterator ) 		Требуется Требуется Требуется
LegacyBidirectionalIterator
(также удовлетворяет LegacyForwardIterator ) 		Требуется Требуется Требуется Требуется
LegacyRandomAccessIterator
(также удовлетворяет LegacyBidirectionalIterator ) 		Требуется Требуется Требуется Требуется Требуется
LegacyContiguousIterator [1]
(также удовлетворяет LegacyRandomAccessIterator ) 		Требуется Требуется Требуется Требуется Требуется Требуется
  1. ↑ LegacyContiguousIterator категория была формально определена только в C++17, однако итераторы std::vector , std::basic_string , std::array , и std::valarray , а также указатели на массивы в стиле C часто рассматривались как отдельная категория в коде до C++17.

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

Определения

Типы и возможность записи

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

Выходной итератор i имеет непустое множество типов, которые writable (until C++20) indirectly_writable (since C++20) для итератора; для каждого такого типа T выражение * i = o является корректным, где o является значением типа T .

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

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

Так же, как обычный указатель на массив гарантирует наличие значения указателя, указывающего за последний элемент массива, так и для любого типа итератора существует значение итератора, указывающее за последний элемент соответствующей последовательности. Такое значение называется past-the-end значением.

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

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

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

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

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

Диапазоны

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

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

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

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

(until 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)

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

Определено в пространстве имен std
(C++20)
определяет, что тип можно прочитать косвенно, применяя оператор *
(концепт)
(C++20)
определяет, что значение можно записать в объект, на который ссылается итератор
(концепт)
(C++20)
определяет, что semiregular тип можно инкрементировать с помощью пре- и постинкрементных операторов
(концепт)
(C++20)
определяет, что операция инкремента для weakly_incrementable типа является сохраняющей равенство и что тип является equality_comparable
(концепт)
(C++20) (C++20)
определяет, что тип ведет себя как (знаковый) целочисленный тип
( концепт только для экспозиции* )
(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 является непрерывным итератором, ссылающимся на элементы, расположенные непрерывно в памяти
(концепт)

Ассоциированные типы итераторов (since C++20)

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

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

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

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

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

Определено в заголовочном файле <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)
определяет требования алгоритмов, которые объединяют отсортированные последовательности в выходную последовательность путем копирования элементов
(concept)
(C++20)
определяет общие требования алгоритмов, которые переставляют последовательности в упорядоченные последовательности
(концепт)
Утилиты
(C++20)
вычисляет результат вызова вызываемого объекта на результате разыменования некоторого набора indirectly_readable типов
(псевдоним шаблона)
(C++20)
вспомогательный шаблон для указания ограничений на алгоритмы, принимающие проекции
(псевдоним шаблона)
(C++26)
вычисляет тип значения indirectly_readable типа посредством проекции
(псевдоним шаблона)

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

адаптер итератора для обхода в обратном порядке
(шаблон класса)
(C++14)
создаёт std::reverse_iterator с типом, выведенным из аргумента
(шаблон функции)
адаптер итератора для вставки в конец контейнера
(шаблон класса)
создаёт std::back_insert_iterator типа, выведенного из аргумента
(шаблон функции)
адаптер итератора для вставки в начало контейнера
(шаблон класса)
создаёт std::front_insert_iterator типа, выведенного из аргумента
(шаблон функции)
адаптер итератора для вставки в контейнер
(шаблон класса)
создаёт std::insert_iterator типа, выведенного из аргумента
(шаблон функции)
(C++23)
адаптер итератора, преобразующий итератор в константный итератор
(шаблон класса)
(C++23)
вычисляет тип константного итератора для заданного типа
(alias template)
(C++23)
вычисляет тип sentinel для использования с константными итераторами
(alias template)
(C++23)
создаёт std::const_iterator с типом, выведенным из аргумента
(шаблон функции)
(C++23)
создает std::const_sentinel типа, выведенного из аргумента
(шаблон функции)
(C++11)
адаптер итератора, который разыменовывается в rvalue
(шаблон класса)
(C++20)
адаптер sentinel для 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)
перемещает итератор на заданное расстояние или до заданной границы
(функциональный объект алгоритма)
(C++20)
возвращает расстояние между итератором и стражем, или между началом и концом диапазона
(функциональный объект алгоритма)
(C++20)
инкрементирует итератор на заданное расстояние или до границы
(функциональный объект алгоритма)
(C++20)
декрементирует итератор на заданное расстояние или до границы
(функциональный объект алгоритма)

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

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

Определено в заголовочном файле <array>
Определено в заголовочном файле <deque>
Определено в заголовочном файле <flat_map>
Определено в заголовочном файле <flat_set>
Определено в заголовочном файле <forward_list>
Определено в заголовочном файле <inplace_vector>
Определено в заголовочном файле <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 output итераторы имели типы значений output итераторы имеют записываемые типы вместо этого
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> не
предоставляли шаблоны функций доступа к диапазонам 		предоставляют эти шаблоны