svec получает емкость 32 при размере 0. Однако эксперименты показали, что любое изменение начальной емкости для вектора, у которого она по умолчанию отлична от 1, ведет к снижению производительности. Так, для векторов типа string и double увеличение емкости с помощью reserve() дало худшие показатели. С другой стороны, увеличение емкости для больших сложных типов дает значительный рост производительности, как показано в таблице 6.4.

Таблица 6.4. Время в секундах для вставки 10 000 элементов при различной емкости*

В нашей системе текстового поиска для хранения объектов тина string м1 будем использовать вектор, не меняя его емкости по умолчанию. Наши измерения показали, что производительность вектора в данном случае лучше, чем у списка. Но прежде чем приступать к реализации, посмотрим, как определяется объект контейнерного типа.

Упражнение 6.2

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

Упражнение 6.3

Почему большие сложные объекты удобнее хранить в контейнере в виде указателей на них, а для коллекции целых чисел применение указателей снижает эффективность?

Упражнение 6.4

Объясните, какой из типов контейнера - вектор или список - больше подходит для приведенных примеров (во всех случаях происходит вставка неизвестного заранее числа элементов):.

(a) Целые числа

(b) Указатели на большие сложные объекты

(c) Большие сложные объекта:

6.4. Как определить последовательный контейнер?

Для того чтобы определить объект контейнерного типа, необходимо сначала включить соответствующий заголовочный файл:

#include <vector>

#inclnde <list>

#include <deque>

#include <map>

#include <set>

Определение контейнера начинается именем его типа, за которым в угловых скобках

vector< string > svec;

следует тип данных его элементов12. Например:

list< int > ilist;

Переменная svec определяется как вектор, способный содержать элементы типа string, а ilist - как список с элементами типа int. Оба контейнера при таком определении

if ( svec.empty() != true )

пуст1. Чтобы убедиться в этом, можно вызвать функцию-член emipty():

; что-то не так

Простейший метод вставки элементов - использование функции-члена push back() ,

string text word; while ( cin >> text word )

которая добавляет элементы в конец контейнера. Например:

svec.push back( text word );

Здесь строки из стандартного ввода считываются в переменную text word, и затем копия каждой строки добавляется в контейнер svec с помощью push back() .

Список имеет функцию-член push front() , которая добавляет элемент в его начало. Пусть есть следующий массив:

int ia[ 4 ] = { 0, 1, 2, 3 };

12 Существующие на сегодняшний день реализации не поддерживают шаблоны с параметрами по умолчанию. Второй параметр - allocator - инкапсулирует способы выделения и освобождения памяти. В С++ он имеет значение по умолчанию, и его задавать не обязательно. Стандартная реализация использует операторы new и delete. Применение распределителя памяти преследует две цели: упростить реализацию контейнеров путем отделения всех деталей, касающихся работы с памятью, и позволить программисту при желании реализовать собственную стратегию выделения памяти. Определения объектов для компилятора, не поддерживающего значения по умолчанию параметров шаблонов, выглядят следующим образом:

i vector< string, allocator > svec; list< int, allocator > ilist;

for ( int ix=0; ix<4; ++ix )

Использование push back()

ilist.push back( ia[ ix ] );

for ( int ix=0; ix<4; ++ix )

создаст последовательность 0, 1, 2, 3, а push front()

ilist.push front( ia[ ix ] );

создаст последовательность 3, 2, 1, 0. 13

Мы можем при создании явно указать размер массива - как константным, так и

#include <list> #include <vector> #include <string>

extern int get word count( string file name ); const int list size = 64;

list< int > ilist( list size );

неконстантным выражением:

vector< string > svec(get word count(string( Chimera )));

Кажд1й элемент контейнера инициализируется значением но умолчанию, соответствующим типу данных. Для int это 0. Для строкового типа вызывается конструктор по умолчанию класса string.

list< int > ilist( list size, -1 );

Мы можем указать начальное значение всех элементов:

vector< string > svec( 24, pooh );

Разрешается не только задавать начальный размер контейнера, но и впоследствии изменять его с помощью функции-члена resize(). Например:

svec.resize( 2 * svec.size() );

Размер svec в этом примере удваивается. Кажд1й новый элемент получает значение но умолчанию. Если мы хотим инициализировать его каким-то другим значением, то оно указывается вторым параметром функции-члена resize() :

13 Если функция-член push front() используется часто, следует применять тип deque, а не vector: в deque эта операция реализована наиболее эффективно.