21.2.Итераторы
Итераторы представляют собой классы, являющиеся абстракциями, обобщениями указателей. Это означает, что итераторы, как и указатели, можно инкрементировать, декрементировать и разыменовывать для доступа к тем элементам контейнеров, на которые они указывают.
Любой контейнер хранит коллекцию элементов одного типа, а способ хранения этих элементов, точнее, их взаимное расположение, зависит от типа контейнера. Например, элементы вектора хранятся в последовательных блоках памяти, а элементы списков хранятся в произвольном порядке. В любом случае каждый контейнер хранит элементы так, чтобы к ним можно было всегда получить доступ в направлении от первого элемента к последнему (рис.1.)
|
Рис. 1. Итераторы и элементы контейнера
Итератор begin() всегда указывает на первый элемент последовательности, а end() – на позицию последовательности, следующую за последним элементом. Несмотря на сходство с указателем, для итератора неприменимо значение NULL. Говорят, что итератор действителен, если он указывает на существующий элемент или на end(). Итератор недействителен (invalid), если он не инициализирован или если последовательность изменила размеры после последнего присваивания значения итератору.
Так как итераторы - обобщение указателей, их семантика - обобщение семантики указателей в C++. Это гарантирует, что каждая шаблонная функция, которая использует итераторы, работает с обычными указателями. Есть пять категорий итераторов в зависимости от операций, определённых для них:
ввода (input iterators);
вывода (output iterators);
последовательные (forward iterators);
двунаправленные (bidirectional iterators);
произвольного доступа (random access iterators).
Отношения между категориями итераторов показаны в табл.1.
Таблица 1.
Отношения среди категорий итераторов
Произвольного доступа |
-> |
Двунаправленные |
-> |
Последовательные |
-- |
|
Последовательные итераторы удовлетворяют всем требованиям итераторов ввода и вывода и могут использоваться всякий раз, когда определяется тот или другой вид. Двунаправленные итераторы удовлетворяют всем требованиям последовательных итераторов и могут использоваться всякий раз, когда определяется последовательный итератор. Итераторы произвольного доступа удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда определяется двунаправленный итератор. Имеется дополнительный атрибут, который могли быть иметь последовательные, двунаправленные и произвольного доступа итераторы, то есть они могут быть модифицируемые (mutable) или постоянные (constant) в зависимости от того, ведёт ли себя результат operator* как ссылка или как ссылка на константу. Постоянные итераторы не удовлетворяют требованиям итераторов вывода.
Точно так же, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными (past-the-end) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми (dereferenceable). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные (singular) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x;), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение – присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.
Итератор j называется доступным (reachable) из итератора i, если и только если имеется конечная последовательность применений операции operator++ к i, которая делает i==j. Если i и j относятся к одному и тому же контейнеру, тогда или j доступен из i, или i доступен из j, или оба доступны (i == j).
Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон – это пара итераторов, которые указывают начало и конец вычисления. Интервал [i,i) – пустой диапазон; вообще, диапазон [i,j) относится к элементам в структуре данных, начиная с элемента, указываемого i, и до элемента, но не включая его, указываемого j. Диапазон [i,j) допустим, если и только если j доступен из i. Результат применения алгоритмов библиотеки к недопустимым диапазонам не определён.
Более подробные сведения по категориям итераторов и особенностям их применения см. в разделе «Итераторы» [5].