C++. Сборник рецептов

Когсуэлл Джефф

list<int>::iterator p1;

set<MyClass>::iterator p2;

Возвращаясь обратно к нашему примеру, итератор о инициализируется первым элементом последовательности, который возвращается методом

begin

. Чтобы перейти к следующему элементу, используется

operator++

. Можно использовать как префиксный инкремент так и постфиксный инкремент (

p++

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

p++

) должен создавать временную переменную, так как он возвращает значение

p

до его инкрементирования. Однако он не может инкрементировать значение

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

Как только будет достигнут элемент

end

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

end

. В отношении стандартных контейнеров принято некое мистическое значение, которое представляет элемент, идущий сразу за последним элементом последовательности, и именно оно возвращается методом

end

. Этот подход работает в цикле

for

, как в этом примере:

for (list<string>::iterator p = lstStr.begin;

 p != lstStr.end; ++p) {

 cout << *p << endl;

}

Как только

p

станет равен

end

,

p

больше не может увеличиваться. Если контейнер пуст, то

begin == end

равно

true

, и тело цикла никогда не выполнится. (Однако для проверки пустоты контейнера следует использовать метод

empty

, а не сравнивать

begin

и

end

или использовать выражение вида

size == 0

.)

Это простое объяснение функциональности итераторов, но это не все. Во-первых, как только что было сказано, итератор работает как

rvalue

или

lvalue

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

for (list<string>::iterator p = lstStr.begin;

 p != lstStr.end; ++p) {

 *p = "mustard";

}

Так как

*p

ссылается на объект типа

string

, для присвоения элементу контейнера новой строки используется выражение

string::operator=(const char*)

. Но что, если

lstStr

 — это объект типа

const

? В этом случае

iterator

не работает, так как его разыменовывание дает не-const объект. Здесь требуется использовать

const_iterator

, который возвращает только

rvalue

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

const

– ссылку.

template<typename T>

void printElements(const T& cont) {

 for(T::const_iterator p = cont.begin;

p ! = cont.end; ++p) {

cout << *p << endl;

 }

}

В этой ситуации следует использовать именно

const

, a

const_iterator

позволит компилятору не дать вам изменить

*p

.

Время от времени вам также может потребоваться перебирать элементы контейнера в обратном порядке. Это можно сделать с помощью обычного

iterator

, но также имеется

reverse_iterator

, который предназначен специально для этой задачи.

reverse_iterator

ведет себя точно так же, как и обычный

iterator

, за исключением того, что его инкремент и декремент

работают противоположно обычному

iterator

и вместо использования методов

begin

и

end

контейнера с ним используются методы

rbegin

и

rend

, которые возвращают

reverse_iterator

.

reverse_iterator

позволяет просматривать последовательность в обратном порядке. Например, вместо инициализации

reverse_iterator

с помощью

begin

он инициализируется с помощью

rbegin

, который возвращает

reverse_iterator

, указывающий на последний элемент последовательности.

operator++

перемещает его назад — по направлению к началу последовательности,

rend

возвращает

reverse_iterator

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

for (list<string>::reverse_iterator p = lstStr.rbegin;

 p != lstStr.rend; ++p) {

 cout << *p << endl;

}

Но может возникнуть ситуация, когда использовать

reverse_iterator

невозможно. В этом случае используйте обычный

iterator

, как здесь.

for (list<string>::iterator p = --lstStr.end;

 p != --lstStr.begin; --p) {

 cout << *p << endl;

}

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

size_t i = lstStr.size;

list<string>::iterator p = begin;

p += i/2; // Переход к середине последовательности

Но помните: в зависимости от типа используемого контейнера эта операция может иметь как постоянную, так и линейную сложность. При использовании контейнеров, которые хранят элементы последовательно, таких как

vector

или

deque

,

iterator

может перейти на любое вычисленное значение за постоянное время. Но при использовании контейнера на основе узлов, такого как

list

, такая операция произвольного доступа недоступна. Вместо этого приходится перебирать все элементы, пока не будет найден нужный. Это очень дорого. Именно поэтому выбор контейнера, используемого в каждой конкретной ситуации, определяется требованиями к перебору элементов контейнера и их поиска в нем. (За более подробной информацией о работе стандартных контейнеров обратитесь к главе 6.)

При использовании контейнеров, допускающих произвольный доступ, для доступа к элементам использования

operator[]

с индексной переменной следует предпочитать

iterator

. Это особенно важно при написании обобщенного алгоритма в виде шаблона функции, так как не все контейнеры поддерживают

iterator

с произвольным доступом.

С итератором можно делает еще много чего, но не с любым

iterator

.

iterator

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

Категории итераторов

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

vector<T>::iterator

позволяет использовать для перехода на некоторое количество элементов вперед

operator+=

, в то время как

list<T>::iterator

не позволяет. Разница между этими двумя типами итераторов определяется их категорией.

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