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

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

#include

<vect

or> #inclnde <list> #include <deque> #include <map>

соответствующий заголовочный файл:

#include <set>

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

vector< string > svec;

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

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

if ( svec.empty() != true )

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

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

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

string text_word; while ( cin >>

text_word )

которая добавляет элементы в конец контейнера. Например: svec.push_back( text_word );

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

vector< string, allocator >

list< int, allocator > ilist; svec;

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

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

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

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

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

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

Мы можем указать начальное значение всех элементов: vector< string > svec( 24, "pooh" );

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

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

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

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

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

указывается вторым параметром функции-члена resize(): svec.resize( 2 * svec.size(), "piglet" );

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

vector< string >

svec2( svec );

Мы можем инициализировать новый контейнер с помощью существующего. Например: list< int > ilist2( ilist ) ;

Каждый контейнер поддерживает полный набор операций сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно. Сопоставляются попарно все элементы контейнера. Если они равны и размеры контейнеров одинаковы, то эти контейнеры равны; в противном случае – не равны. Результат операций “больше” или “меньше” определяется сравнением первых двух неравных элементов. Вот что печатает программа, сравнивающая пять векторов:

ivecl: 1 3 5 7 9 12 ivec2: 0 1 1 2 3 5 8 13 ivec3: 1 3 9

ivec4: 1 3 5 7 ivec5: 2 4

//первый неравный элемент: 1, О

//ivecl больше чем ivec2

ivecl < ivec2 //false ivec2 < ivecl //true

//первый неравный элемент: 5, 9 ivecl < ivec3 //true

//все элементы равны, но ivec4 содержит меньше элементов

//следовательно, ivec4 меньше, чем ivecl

ivecl < ivec4 //false

// первый неравный элемент: 1, 2 ivecl < ivec5 //true

ivecl == ivecl //true ivecl == ivec4 //false ivecl != ivec4 //true

ivecl > ivec2 //true ivec3 > ivecl //true ivec5 > ivec2 //true

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

∙операция “равно”;

∙операция “меньше” (все операции сравнения контейнеров, о которых говорилось выше, используют только эти две операции сравнения);

∙значение по умолчанию (для класса это означает наличие конструктора по умолчанию).

Все предопределенные типы данных, включая указатели и классы из стандартной библиотеки С++ удовлетворяют этим требованиям.

Упражнение 6.5

#include <string> #include <vector> #include <iostream>

#int main()

{

vector<string> svec; svec.reserve( 1024 );

string text_word;

while ( cin >> text_word ) svec.push_back( text_word );

svec.resize( svec.size() +svec.size()/2 );

// ...

Объясните, что делает данная программа:

}

Упражнение 6.6

Может ли емкость контейнера быть меньше его размера? Желательно ли, чтобы емкость была равна размеру: изначально или после вставки элемента? Почему?

Упражнение 6.7

Если программа из упражнения 6.5 прочитает 256 слов, то какова наиболее вероятная емкость контейнера после изменения размера? А если она считает 512 слов? 1000? 1048?

Упражнение 6.8 Какие из данных классов не могут храниться в векторе: