8.2. Итераторы

Итератор–это специальный вспомогательный объект, который поставляется разработчиком контейнерного класса. Единственное назначение такого объекта – обеспечить доступ к элементам контейнера без показа внутренней структуры контейнера (один элемент за одно обращение).

Обычно итератор содержит указатель, с которым производятся различные манипуляции.

В STL итератор – это фундамент, на котором основано использование контейнерных классов и алгоритмов.

Итераторы применяются для различных целей:

• Итератор может обозначать конкретное значение.

• Пара итераторов может задавать диапазон значений. При этом второе значение (второй итератор) рассматривается не как часть определяемого диапазона, но как запредельный элемент, описывающий значение, следующее за последним значением из заданного диапазона.

Основное действие, которое модифицирует итератор, – это операции инкремент ++ , декремент -- и увеличение +.

Для доступа к данным, определяемым итератором используется оператор разыменования *.

Итератор является шаблоном, параметром которого является контейнерный класс. Существует пять типов итераторов:

Итераторы ввода (input_iterator) поддерживают операции равенства, разыменования и автоинкремента. Итераторы, отвечающие этим условиям, могут использоваться для однопроходных алгоритмов, которые читают значения данных в одном направлении. Специальным случаем итератора ввода является istream_iterator.

==, !=, *i, ++i, i++, *i++.

Итераторы вывода (output_iterator) поддерживают разыменование, допустимое только с левой стороны присваивания, и инкремент:

++i, i++, *i=t, *i++=t

Однонаправленные итераторы (forward_iterator) поддерживают все операции итераторов ввода-вывода и, кроме того, позволяют без ограничений применять присваивание. Для них из i==j следует ++i==++j, что не всегда истинно для итераторов ввода. Т.е. forward-итераторы сохраняют позицию внутри структуры данных (контейнера) при многократных проходах. Таким образом, их можно использовать в алгоритмах с многократным проходом.

==, !=, =, *i, ++i, i++, *i++.

Двунаправленные итераторы (biderectional_iterator) обладают всеми свойствами forward-итераторов, а также возможностью прохода контейнера в обоих направлениях, т.е. имеют дополнительная операции –декремент

--i, i--, *i--.

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

i+=n, a+n, i-=n, a-n, i-j, i[n], i<j, i<=j, i>j, i>=j.

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

С итераторами можно работать так же, как с указателями. К ним можно применить операции *, инкремента, декремента. Типом итератора объявляется тип iterator, который определен соответствующим образом в различных контейнерах. В STL также поддерживаются обратные итераторы (reverse iterators). Обратными итераторами могут быть либо двунаправленные итераторы, либо итераторы произвольного доступа, но проходящие последовательность в обратном направлении. То есть если обратный итератор указывает на последний элемент последовательности, то инкремент этого итератора приведет к тому, что он будет указывать на предпоследний элемент.