C++ для начинающих

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

Емкость	Время в секундах
1 по умолчанию	670
4,096	555
8,192	444
10,000	222
*Сложный класс размером 8000 байт с конструктором копирования и деструктором

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

Упражнение 6.2

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

Упражнение 6.3

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

Упражнение 6.4

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

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

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

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

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

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

#include vector

#inclnde list

#include deque

#include map

#include set

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

vector string svec;

list int ilist;

Переменная svec определяется как вектор, способный содержать элементы типа string, а ilist – как список с элементами типа int. Оба контейнера при таком определении пусты. Чтобы убедиться в этом, можно вызвать функцию-член empty():

if ( svec.empty() != true )

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

Простейший метод вставки элементов – использование функции-члена 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 };

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

for ( int ix=0; ix4; ++ix )

ilist.push_back( ia[ ix ] );

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

for ( int ix=0; ix4; ++ix )

ilist.push_front( ia[ ix ] );

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

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

#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")));

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

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

list int ilist( list_size, -1 );

vector string svec( 24, "pooh" );

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

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

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

// каждый новый элемент получает значение "piglet"

svec.resize( 2 * svec.size(), "piglet" );

Кстати, какова наиболее вероятная емкость svec при определении, если его начальный размер равен 24? Правильно, 24! В общем случае минимальная емкость вектора равна его текущему размеру. При удвоении размера емкость, как правило, тоже удваивается

Мы можем инициализировать новый контейнер с помощью существующего. Например: