Язык программирования C++. Пятое издание - Стенли Липпман

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

Обычно каждый контейнер определяется в файле заголовка, название которого совпадает с именем типа. Таким образом, тип deque определен в заголовке deque, тип list — в заголовке list и т.д. Контейнеры — это шаблоны классов (см. раздел 3.3). Подобно векторам, при создании контейнера специфического типа необходимо предоставить дополнительную информацию. Для большинства контейнеров, но не всех, предоставляемой информацией является тип элемента:

list<Sales_data> // список, содержащий объекты класса Sales_data

deque<double>    // двухсторонняя очередь переменных типа double

Ограничения на типы, которые может содержать контейнер

Типом элемента последовательного контейнера может быть практически любой тип. В частности, типом элемента контейнера может быть другой контейнер. Такие контейнеры определяют точно так же, как любые другие: в угловых скобках указывается тип элемента (которым в данном случае является другой контейнер):

vector<vector<string>> lines; // вектор векторов

где lines — это вектор, элементами которого являются векторы строк.

Устаревшие компиляторы могут потребовать пробела между угловыми скобками, например vector<vector<string> >.

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

В качестве примера рассмотрим конструктор последовательного контейнера, получающий аргумент размера (см. раздел 3.3.1) и использующий стандартный конструктор типа элемента. У некоторых классов нет стандартного конструктора. Вполне можно определить контейнер, содержащий объекты такого типа, но создать такой контейнер, используя только количество элементов, нельзя:

// тип noDefault не имеет стандартного конструктора

vector<noDefault> v1(10, init); // ok: предоставлен инициализатор

                                // элемента

vector<noDefault> v2(10);       // ошибка: необходимо предоставить

                                // инициализатор элемента

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

Упражнения раздела 9.2

Упражнение 9.2. Определите список (list), элементами которого будут двухсторонние очереди целых чисел.

9.2.1. Итераторы

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

За одним исключением контейнерные итераторы поддерживают все функции, перечисленные в табл. 3.6. Исключение в том, что итераторы контейнера forward_list не поддерживают оператор декремента (--). Операторы арифметических действий с итераторами, перечисленными в табл. 3.7, применимы только к итераторам контейнеров string, vector, deque и array. К итераторам контейнеров любых других типов эти операторы неприменимы.

Диапазоны итераторов

Концепция диапазона итераторов фундаментальна для стандартной библиотеки.

Диапазон итераторов (iterator range) обозначается парой итераторов, каждый из которых указывает на элемент или на следующий элемент после последнего в том же контейнере. Эти два итератора, обозначающие диапазон элементов контейнера, зачастую называют begin и end или, что несколько обманчиво, first и last.

Хоть имя last и общепринято, оно немного вводит в заблуждение, поскольку второй итератор никогда не указывает на последний элемент диапазона. Вместо этого он указывает на позицию следующего элемента после последнего. Диапазон включает элемент, обозначенный итератором first, и все элементы от него до обозначенного итератором last, но не включая его.

Такой диапазон элементов называется интервал, включающий левый элемент (left-inclusive interval). Вот стандартная математическая форма записи такого диапазона:

[ begin, end )

Это указывает, что диапазон начинается с элемента, обозначенного итератором begin, и заканчивается элементом перед тем, который обозначен итератором end. Итераторы begin и end должны относиться к тому же контейнеру. Итератор end может быть равен итератору begin, но не должен указывать на элемент перед обозначенным итератором begin.

Требования к итераторам, формирующим диапазон

Два итератора, begin и end, позволяют задать диапазон при следующих условиях.

• Итераторы относятся к существующим элементам или к следующему элементу за концом того же контейнера.

• Элемент end достижим благодаря последовательному приращению итератора begin. Другими словами, итератор end не должен предшествовать итератору begin.

Компилятор не может сам соблюдать эти требования. Позаботиться об этом придется разработчику.

Смысл использования диапазонов, включающих левый элемент

Библиотека использует диапазоны, включающие левый элемент, потому, что они обладают двумя очень полезными качествами (напомним, что допустимый диапазон обозначают итераторы begin и end).

• Если итератор begin равен итератору end, то диапазон пуст.

• Если итератор begin не равен итератору end, в диапазоне содержится по крайней мере один элемент и итератор begin указывает на первый из них.

• Можно осуществлять инкремент итератора begin до тех пор, пока он не станет равен итератору end (т.е. begin == end).

Благодаря этим качествам можно создавать вполне безопасные циклы обработки диапазона элементов, например, такие:

while (begin != end) {

 *begin = val; // ok: диапазон не пуст, begin обозначает элемент

 ++begin;      // переместить итератор и получить следующий элемент

}

Если итераторы begin и end задают допустимый диапазон элементов, выполнение условия begin == end означает, что диапазон пуст. В данном случае это условие выхода из цикла. Если диапазон не пуст, значит, итератор begin указывает на элемент в этом не пустом диапазоне. Вполне очевидно, что в теле цикла while можно безопасно обращаться к значению итератора begin, поскольку оно гарантировано существует. И наконец, поскольку инкремент итератора begin осуществляется в теле цикла, последний гарантированно будет конечным.

Упражнения раздела 9.2.1

Упражнение 9.3. Каким условиям должны удовлетворять итераторы, обозначающие диапазон?

Упражнение 9.4. Напишите функцию, которая получает два итератора вектора vector<int> и значение типа int. Организуйте поиск этого значения в диапазоне и возвратите логическое значение (тип bool), указывающее, что значение найдено.

Упражнение 9.5. Перепишите предыдущую программу так, чтобы она возвращала итератор на найденный элемент. Функция должна учитывать случай, когда элемент не найден.

Упражнение 9.6. Что не так со следующей программой? Как ее можно исправить?

list<int> lst1;

list<int>::iterator iter1 = lst1.begin(),

iter2 = lst1.end();

while (iter1 < iter2) /* ... */

9.2.2. Типы-члены классов контейнеров

Класс каждого контейнера определяет несколько типов, представленных в табл. 9.2. Три из них уже использовались: size_type (см. раздел 3.2.2), iterator и const_iterator (см. раздел 3.4.1).

Кроме итераторов уже использовавшихся типов, большинство контейнеров предоставляет реверсивные итераторы (reverse_iterator). Другими словами, реверсивный итератор — это итератор, перебирающий контейнер назад и инвертирующий значение его операторов. Например, оператор ++ возвращает реверсивный итератор к предыдущему элементу. Более подробная информация о реверсивных итераторах приведена в разделе 10.4.3.