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

См. раздел 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, не указаны; их описание можно найти в профессиональных справочниках.

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

Б.4.1. Обзор

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

Б.4.2. Типы членов

Контейнер определяет множество типов его членов.

Б.4.3. Конструкторы, деструкторы и присваивания

Контейнеры имеют много разнообразных конструкторов и операторов присваивания. Перечислим конструкторы, деструкторы и операторы присваивания для контейнера C (например, типа vector<double> или map<string,int>).

Для некоторых контейнеров и типов элементов конструктор или операция копирования может генерировать исключения.

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

Контейнер можно интерпретировать как последовательность, порядок следования элементов в которой определен либо итератором контейнера, либо является обратным к нему. Для ассоциативного контейнера порядок определяется критерием сравнения (по умолчанию оператором <).

Б.4.5. Доступ к элементам

К некоторым элементам можно обратиться непосредственно.

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

Б.4.6. Операции над стеком и двусторонней очередью

Стандартные контейнеры vector и deque обеспечивают эффективные операции над концами (back) последовательности элементов. Кроме того, контейнеры list и deque обеспечивают аналогичные операции над началом (front) своей последовательности.

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

Отметим, что операции удаления элементов не возвращают значений. Если бы они это делали, то копирующие конструкторы, генерирующие исключения, могли бы серьезно усложнить реализацию. Для доступа к элементам стека и очереди рекомендуем использовать функции front() и back() (см. раздел Б.4.5). Мы не ставили себе задачу перечислить все ограничения; попробуйте догадаться об остальных (как правило, компиляторы сообщают пользователям об их неверных догадках) или обратитесь к более подробной документации.

Б.4.7. Операции над списком

Ниже приведены операции над списком.

Результат q функции insert() ссылается на последний вставленный элемент. Результат q функции erase() ссылается на элемент, следующий