Итераторы - это обобщение указателей, которые позволяют программе на C ++ единообразно работать с различными структурами данных (контейнерами). Чтобы иметь возможность создавать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, библиотека формализует не только интерфейсы, но также семантику и предположения о сложности итераторов. Итератор ввода i поддерживает выражение *i, в результате чего получается значение некоторого типа объекта T, называемого value type итератором. Итератор вывода i имеет непустой набор типов, относящихся writable к итератору; для каждого такого типа допустимо Tвыражение, *i = oгде o - значение типа T. Итератор, i для которого выражение (*i).m четко определено, поддерживает выражение i->m с той же семантикой, что и (*i).m. Для каждого типа итератора, X для которого определено равенство, существует соответствующий целочисленный тип соdifference type знаком, называемый итератором.
Поскольку итераторы являются абстракцией указателей, их семантика является обобщением большей части семантики указателей в C ++. Это гарантирует, что каждый шаблон функции, который принимает итераторы, также работает с обычными указателями. Настоящий стандарт определяет пять категорий итераторов, в соответствии с операциями , определенными на них: input iterators, output iterators, forward iterators, bidirectional iterators и random access iterators, как показано в таблице 93.
| Произвольный доступ | → Двунаправленный | → Вперед | → Вход |
| → Выход |
Прямые итераторы удовлетворяют всем требованиям итераторов ввода и могут использоваться всякий раз, когда указан итератор ввода; Двунаправленные итераторы также удовлетворяют всем требованиям прямых итераторов и могут использоваться всякий раз, когда указан прямой итератор; Итераторы произвольного доступа также удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда указан двунаправленный итератор.
Вызываются итераторы, которые дополнительно удовлетворяют требованиям итераторов вывода mutable iterators. Неизменяемые итераторы называются constant iterators.
В дополнение к требованиям этого подпункта для типа итератора должна быть предусмотрена вложенность, typedef-names указанная в [iterator.traits]. [ Note: Либо тип итератора должен предоставлять их typedef-names напрямую (в этом случае получать их iterator_traits автоматически), либо iterator_traits специализация должна предоставлять их. ] — end note
Итераторы, которые дополнительно удовлетворяют требованию о том, что для целочисленных значений n и значений итераторов с возможностью разыменования a и (a + n), *(a + n) эквивалентно *(addressof(*a) + n), вызываются contiguous iterators. [ Note: Например, тип «указатель на int» является непрерывным итератором, но reverse_iterator<int *> это не так. Для допустимого диапазона итератора [a,b) с возможностью разыменования aсоответствующий диапазон, обозначенный указателями, равен [addressof(*a),addressof(*a) + (b - a)); b не может быть разыменован. ] — end note
Так же, как обычный указатель на массив гарантирует, что существует значение указателя, указывающее за последним элементом массива, так и для любого типа итератора существует значение итератора, указывающее за последним элементом соответствующей последовательности. Эти значения называются past-the-end значениями. Значения итератора ,i для которых выражение *i определенно называется dereferenceable. Библиотека никогда не предполагает, что последние значения могут быть разыменованы. Итераторы также могут иметь особые значения, не связанные с какой-либо последовательностью. [ Example: После объявления неинициализированного указателя x (как в случае int* x;) x всегда следует предполагать, что он имеет единственное значение указателя. ] Результаты большинства выражений не определены для сингулярных значений; единственными исключениями являются уничтожение итератора, содержащего сингулярное значение, присвоение неособого значения итератору, содержащему сингулярное значение, и, для итераторов, удовлетворяющих требованиям, использование итератора с инициализированным значением в качестве источника копирование или перемещение. [ Эта гарантия не предоставляется для инициализации по умолчанию, хотя различие имеет значение только для типов с тривиальными конструкторами по умолчанию, такими как указатели или агрегаты, содержащие указатели. ] В этих случаях единственное значение перезаписывается так же, как и любое другое значение. Разыменяемые значения всегда не единственные. — end example DefaultConstructible Note: — end note
Итератор j вызывается reachable из итератора i тогда и только тогда, когда существует конечная последовательность применений выражения, ++i которое делает i == j. Если j доступен из i, они относятся к элементам той же последовательности.
Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, использующие диапазоны. A range - пара итераторов, обозначающих начало и конец вычисления. Диапазон [i, i) - это пустой диапазон; в общем, диапазон [i, j) относится к элементам в структуре данных, начиная с элемента, на который указывает, i и до, но не включая элемент, на который указывает j. Диапазон [i, j) действителен тогда и только тогда, когда j он доступен из i. Результат применения функций библиотеки к недопустимым диапазонам не определен.
Для всех категорий итераторов требуются только те функции, которые могут быть реализованы для данной категории в постоянное время (с амортизацией). Поэтому в таблицах требований для итераторов нет столбца сложности.
Уничтожение итератора может сделать недействительными указатели и ссылки, ранее полученные от этого итератора.
В следующих разделах, a и b величины означают типа X или const X, difference_type и reference относятся к типам , iterator_traits<X>::difference_type и iterator_traits<X>::reference, соответственно, n обозначает значение difference_type, u, tmpи цветом,m обозначают идентификаторы, r обозначает значение X&, t обозначает значение типа значения T, o обозначает значение некоторого типа который доступен для записи итератору вывода. [ Note: Для типа итератора X должен быть экземпляр iterator_traits<X>. ] — end note
Это определение применяется к указателям, поскольку указатели являются итераторами. Эффект разыменования итератора, который был признан недействительным, не определен.