Библиотека итераторов
Итераторы являются обобщением указателей, которые позволяют программе на C++ работать с различными структурами данных (например, с контейнерами и диапазонами (начиная с C++20)) единым образом. Библиотека итераторов предоставляет определения для итераторов, а также свойства итераторов, адаптеры и служебные функции.
Поскольку итераторы являются абстракцией указателей, их семантика является обобщением большей части семантики указателей в C++. Это гарантирует, что каждый шаблон функции, принимающий итераторы, будет работать и с обычными указателями.
Содержание |
[править] Категории итераторов
Существует пять (до C++17)шесть (начиная с C++17) видов итераторов: LegacyInputIterator, LegacyOutputIterator, LegacyForwardIterator, LegacyBidirectionalIterator, LegacyRandomAccessIterator и LegacyContiguousIterator (начиная с C++17). (Смотрите также LegacyIterator , где описан самый базовый тип итератора.)
Вместо того, чтобы определяться конкретными типами, каждая категория итераторов определяется операциями, которые могут быть выполнены с нею. Это определение означает, что любой тип, поддерживающий необходимые операции, может использоваться в качестве итератора – например, указатель поддерживает все операции, требуемые для LegacyRandomAccessIterator, поэтому указатель можно использовать где угодно, где ожидается LegacyRandomAccessIterator.
Все категории итераторов (кроме LegacyOutputIterator) могут быть организованы в иерархию, где более мощные категории итераторов (например, LegacyRandomAccessIterator) поддерживают операции менее мощных категорий (например, LegacyInputIterator). Если итератор попадает в одну из этих категорий и также соответствует требованиям LegacyOutputIterator, то он называется изменяемым итератором и поддерживает ввод и вывод. Неизменяемые итераторы называются константными итераторами.
|
Итераторы называются constexpr итераторами если все операции, предусмотренные для соответствия требованиям категории итераторов, являются no section name. |
(начиная с C++20) |
| Категоря итератора | Требования к эксплуатации и хранению | ||||||
|---|---|---|---|---|---|---|---|
| запись | чтение | инкремент | декремент | произвольный доступ |
непрерывное хранилище | ||
| без нескольких проходов |
с несколькими проходами | ||||||
| LegacyIterator | Требует | ||||||
| LegacyOutputIterator | Требует | Требует | |||||
| LegacyInputIterator (mutable, если поддерживает операцию записи) |
Требует | Требует | |||||
| LegacyForwardIterator (также соответствует LegacyInputIterator) |
Требует | Требует | Требует | ||||
| LegacyBidirectionalIterator (также соответствует LegacyForwardIterator) |
Требует | Требует | Требует | Требует | |||
| LegacyRandomAccessIterator (также соответствует LegacyBidirectionalIterator) |
Требует | Требует | Требует | Требует | Требует | ||
| LegacyContiguousIterator[1] (также соответствует LegacyRandomAccessIterator) |
Требует | Требует | Требует | Требует | Требует | Требует | |
- ↑ LegacyContiguousIterator была только формально определена в C++17, но итераторы std::vector, std::basic_string, std::array и std::valarray, а также указатели на массивы C часто рассматриваются как отдельная категория в коде до C++17.
Примечание: категория 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) в итератор; для каждого такого типа |
(начиная с C++11) |
Для каждого типа итератора X для которого определено равенство (до C++20), существует соответствующий знаковый целочисленный (до C++20)целочисленно-подобный (начиная с C++20) тип, называемый разностным типом итератора.
[править] Разыменовываемость и валидность
Точно так же, как обычный указатель на массив гарантирует наличие значения указателя, указывающего на элемент за последним элементом массива, так и для любого типа итератора существует значение итератора, указывающее на элемент за последним элементом соответствующего контейнера (до C++11)последовательности (начиная с C++11). Такое значение называется значением за концом.
Значения итератора i, для которых определено выражение *i называются разыменовываемыми. Стандартная библиотека никогда не предполагает, что значения за конечным значением могут быть разыменованы.
Итераторы также могут иметь единственные значения, не связанные ни с каким контейнером (до C++11)последовательностью (начиная с C++11). Результаты большинства выражений не определены для единственных значений; с единственными исключениями
- присваивание неединственного значения итератору, который содержит единственное значение,
- уничтожение итератора, который содержит единственное значение, и,
|
(начиная с C++11) |
В этих случаях единственное значение перезаписывается так же, как и любое другое значение. Разыменовываемые значения всегда не единственные.
Недопустимый итератор это итератор, который может быть единственным.
[править] Диапазоны
Большинство алгоритмических шаблонов стандартной библиотеки, работающих со структурами данных, имеют интерфейсы, использующие диапазоны.
|
Итератор j называется достижимым из итератора i тогда и только тогда, когда существует конечная последовательность применений выражения ++i, которая делает i == j. Если j достижим из i, они ссылаются на элементы одной и той же последовательности. Диапазон это пара итераторов, обозначающих начало и конец вычисления. Диапазон Диапазон |
(до C++20) |
|
Диапазон это либо
Сравнимый диапазонИтератор и ограничитель, обозначающий диапазон, сравнимы. Ограничитель s называется достижимым из итератора i тогда и только тогда, когда существует конечная последовательность применений выражения ++i, которая делает i == s. Если s достижимо из i, Подсчитываемый диапазонПодсчитываемый диапазон i Подсчитываемый диапазон i
|
(начиная с 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++17) |
базовый класс для упрощения определения требуемых типов для простых итераторов (шаблон класса) |
[править] Точки настройки итераторов
| Определены в пространстве имён
std::ranges | |
| (C++20) |
приводит результат разыменования объекта к связанному с ним типу правосторонней ссылки (объект точки настройки) |
| (C++20) |
меняет местами значения, на которые ссылаются два разыменовываемых объекта (объект точки настройки) |
[править] Концепты алгоритмов и утилиты
C++20 также предоставляет набор концептов и связанных шаблонов служебных утилит, предназначенных для упрощения ограничения операций общих алгоритмов.
| Определены в заголовочном файле
<iterator> | |
| Определены в пространстве имён
std | |
Косвенно вызываемые концепты | |
указывает, что вызываемый тип может быть вызван в результате разыменования типа indirectly_readable (концепт) | |
| (C++20) |
указывает, что вызываемый тип, когда он вызывается с результатом разыменования типа indirectly_readable, соответствует predicate (концепт) |
| (C++20) |
указывает, что вызываемый тип, когда он вызывается с результатом разыменования двух типов indirectly_readable, соответствует predicate (концепт) |
указывает, что вызываемый тип при вызове в результате разыменования двух типов 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) |
адаптер итератора, который разыменовывается в правостороннюю ссылку (шаблон класса) |
| (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) |
продвигает итератор на заданное расстояние или до заданной границы (ниблоид) |
| (C++20) |
возвращает расстояние между итератором и ограничителем или между началом и концом диапазона (ниблоид) |
| (C++20) |
инкрементирует итератор на заданное расстояние или до границы (ниблоид) |
| (C++20) |
декрементирует итератор на заданное расстояние или до границы (ниблоид) |
[править] Доступ к диапазону
Эти функции, не являющиеся элементами, предоставляют общий интерфейс для контейнеров, простых массивов и 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++:
| Номер | Применён | Поведение в стандарте | Корректное поведение |
|---|---|---|---|
| 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 | определение сингулярности и достижимости итератора зависело от контейнеров |
вместо этого зависит от последовательностей |
