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

Страуструп Бьерн

Для того чтобы считать последовательность, алгоритм обычно получает пару итераторов (

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

, не указаны; их описание можно найти в профессиональных справочниках.

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

Б.4.1. Обзор

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

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

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