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

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

  ++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.

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

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

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

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

Б.4.1. Обзор

Операции, предусмотренные в стандартных контейнерах, можно проиллюстрировать следующим образом: