Программирование. Принципы и практика использования C++ Исправленное издание

Итератор — это аналог указателя, в котором реализованы операции косвенного доступа (например, оператор * для разыменования) и перехода к новому элементу (например, оператор ++ для перехода к следующему элементу). Последовательность элементов определяется парой итераторов, задающих полуоткрытый диапазон [begin:end].

Иначе говоря, итератор begin указывает на первый элемент последовательности, а итератор end — на элемент, следующий за последним элементом последовательности. Никогда не считывайте и не записывайте значение *end. Для пустой последовательности всегда выполняется условие begin==end. Другими словами, для любого итератора p последовательность [p:p] является пустой.

Для того чтобы считать последовательность, алгоритм обычно получает пару итераторов (b, e) и перемещается по элементам с помощью оператора ++, пока не достигнет конца.

while (b!=e) { // используйте !=, а не <

               // какие-то операции

  ++b;         // переходим к последнему элементу

}

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

p = find(v.begin,v.end,x); // ищем x в последовательности v

if (p!=v.end) {

      // x найден в ячейке p

}

else {

      // x не найден в диапазоне [v.begin:v.end)

}

См. раздел 20.3.

Алгоритмы, записывающие элементы последовательности, часто получают только итератор, установленный на ее первый элемент. В данном случае программист должен сам предотвратить выход за пределы этой последовательности. Рассмотрим пример.

template void f(Iter p, int n)

{

  while (n>0) *p++ = ––n;

  vector v(10);

  f(v.begin,v.size); // OK

  f(v.begin,1000);     // большая проблема

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

Перечислим операции над итераторами.

Обратите внимание на то, что не каждый вид итераторов (раздел Б.3.2) поддерживает все операции над итераторами.

Б.3.2. Категории итераторов

В стандартной библиотеке предусмотрены пять видов итераторов.

С логической точки зрения итераторы образуют иерархию (см. раздел 20.10).

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

Каждый контейнер имеет собственные итераторы конкретной категории:

• vector — итераторы произвольного доступа;

• list — двунаправленные итераторы;

• deque — итераторы произвольного доступа;

• bitset — итераторов нет;

• set — двунаправленные итераторы;

• multiset — двунаправленные итераторы;

• map — двунаправленные итераторы;

• multimap — двунаправленные итераторы;

• unordered_set — однонаправленные итераторы;

• unordered_multiset — однонаправленные итераторы;

• unordered_map — однонаправленные итераторы;

• unordered_multimap — однонаправленные итераторы.

Б.4. Контейнеры

Контейнер содержит последовательность элементов. Элементы этой последовательности имеют тип value_type. Наиболее полезными контейнерами являются следующие.

Эти контейнеры определены в классах , и др. (см. раздел Б.1.1). Последовательные контейнеры занимают непрерывную область памяти или представляют собой связанные списки, содержащие элементы соответствующего типа value_type (выше мы обозначали его буквой T). Ассоциативные контейнеры представляют собой связанные структуры (деревья) с узлами соответствующего типа value_type (выше мы обозначали его как pair(K,V)). Последовательность элементов в контейнерах set, map или multimap упорядочена по ключу (K). Последовательность в контейнерах, название которых начинается со слова unordered, не имеет гарантированного порядка. Контейнер multimap отличается от контейнера map тем, что в первом случае значение ключа может повторяться много раз. Адаптеры контейнеров — это контейнеры со специальными операциями, созданные из других контейнеров.

Если сомневаетесь, используйте класс vector. Если у вас нет весомой причины использовать другой контейнер, используйте класс vector.