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

 };

Б.3. Итераторы

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

Б.3.1. Модель итераторов

Итератор — это аналог указателя, в котором реализованы операции косвенного доступа (например, оператор * для разыменования) и перехода к новому элементу (например, оператор ++ для перехода к следующему элементу). Последовательность элементов определяется парой итераторов, задающих полуоткрытый диапазон [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<class Iter> void f(Iter p, int n)
 {
  while (n>0) *p++ = ––n;
  vector<int> 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. Наиболее полезными контейнерами являются следующие.

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

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

Для выделения и освобождения памяти (см. раздел 19.3.6) контейнеры используют распределители памяти. Мы не описываем их здесь; при необходимости читатели найдут информацию о них в профессиональных справочниках. По умолчанию распределитель памяти использует операторы new и delete, для того чтобы занять или освободить память, необходимую для элементов контейнера.

Там, где это целесообразно, операция доступа реализована в двух вариантах: один — для константных объектов, другой — для неконстантных (см. раздел 18.4).

В этом разделе перечислены общие и “почти общие” члены стандартных контейнеров (более подробную информацию см. в главе 20). Члены, характерные для какого-то конкретного контейнера, такие как функция splice из класса list, не указаны; их описание можно найти в профессиональных справочниках.

Некоторые типы данных обеспечивают большинство операций, требующихся от стандартного контейнера, но все-таки не все. Иногда такие типы называют “почти контейнерами”. Перечислим наиболее интересные из них.