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

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

#include < vector>

#inclnde < list>

#include < deque>

#include < map>

#include < set>

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

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; ix< 4; ++ix )

ilist.push_back( ia[ ix ] );

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

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

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

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

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

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

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

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

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

(a) class cl1 { public: c11( int=0 ); bool operator==(); bool operator! =(); bool operator< =(); bool operator< (); //... };   (b) class c12 { public: c12( int=0 ); bool operator! =(); bool operator< =(); //... };   (с) class c13 { public: int ival; };   (d) class c14 { public: c14( int, int=0 ); bool operator==(); bool operator! =(); //... }

Итераторы

Итератор предоставляет обобщенный способ перебора элементов любого контейнера – как последовательного, так и ассоциативного. Пусть iter является итератором для какого-либо контейнера. Тогда

++iter;

перемещает итератор так, что он указывает на следующий элемент контейнера, а

*iter;

разыменовывает итератор, возвращая элемент, на который он указывает.

Все контейнеры имеют функции-члены begin() и end().

· begin() возвращает итератор, указывающий на первый элемент контейнера.

· end() возвращает итератор, указывающий на элемент, следующий за последним в контейнере.

Чтобы перебрать все элементы контейнера, нужно написать:

for ( iter = container. begin();

iter! = container.end(); ++iter )

do_something_with_element( *iter );

Объявление итератора выглядит слишком сложным. Вот определение пары итераторов вектора типа string:

// vector< string> vec;

vector< string>:: iterator iter = vec.begin();

vector< string>:: iterator iter_end = vec.end();

В классе vector для определения iterator используется typedef. Синтаксис

vector< string>:: iterator

ссылается на iterator, определенный с помощью typedef внутри класса vector, содержащего элементы типа string.

Для того чтобы напечатать все элементы вектора, нужно написать:

for(; iter! = iter_end; ++iter )

cout < < *iter < < '\n';

Здесь значением *iter выражения является, конечно, элемент вектора.

В дополнение к типу iterator в каждом контейнере определен тип const_iterator, который необходим для навигации по контейнеру, объявленному как const. const_iterator позволяет только читать элементы контейнера:

#include < vector>

void even_odd( const vector< int> *pvec,

          vector< int> *pvec_even,

          vector< int> *pvec_odd )

{

// const_iterator необходим для навигации по pvec

vector< int>:: const_iterator c_iter = pvec-> begin();

vector< int>:: const_1terator c_iter_end = pvec-> end();

 

for (; c_iter! = c_iter_end; ++c_iter )

   if ( *c_iter % 2 )

       pvec_even-> push_back( *c_iter );

   else pvec_odd-> push_back( *c_iter );

}

Что делать, если мы хотим просмотреть некоторое подмножество элементов, например взять каждый второй или третий элемент, или хотим начать с середины? Итераторы поддерживают адресную арифметику, а значит, мы можем прибавить некоторое число к итератору:

vector< int>:: iterator iter = vec-> begin()+vec.size()/2;

iter получает значение адреса элемента из середины вектора, а выражение

iter += 2;

сдвигает iter на два элемента.

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

ilist.begin() + 2;

так как для перемещения на два элемента необходимо два раза перейти по адресу, содержащемуся в закрытом члене next. У классов vector и deque перемещение на два элемента означает прибавление 2 к указателю на текущий элемент. (Адресная арифметика рассматривается в разделе 3.3.)

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

#include < vector>

#include < string>

#include < iostream>

 

int main()

{

vector< string> svec;

string intext;

while ( cin > > intext )

   svec.push_back( intext );

 

// обработать svec...

}

Вот как можно определить новые векторы, инициализируя их элементами первого вектора:

int main() { vector< string> svec; //...   // инициализация svec2 всеми элементами svec vector< string> svec2( svec.begin(), svec.end() );   // инициализация svec3 первой половиной svec vector< string>:: iterator it =           svec.begin() + svec.size()/2; vector< string> svec3 ( svec.begin(), it );   //... }

Использование специального типа istream_iterator (о нем рассказывается в разделе 12.4.3) упрощает чтение элементов из входного потока в svec:

#include < vector>

#include < string>

#include < iterator>

 

int mainQ

{

// привязка istream_iterator к стандартному вводу

istream_iterator< string> infile( cin );

 

// istream_iterator, отмечающий конец потока

istream_iterator< string> eos;

 

// инициализация svec элементами, считываемыми из cin;

vector< string> svec( infile, eos );

 

//...

}

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

#include < string>

string words[4] = {

" stately", " plump", " buck", " mulligan"

};

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

vector< string > vwords( words, words+4 );

Второй указатель служит “стражем”: элемент, на который он указывает, не копируется.

Аналогичным образом можно инициализировать список целых элементов:

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

list< int > ilist( ia, ia+6 );

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

Упражнение 6.9

Какие ошибки допущены при использовании итераторов:

const vector< int > ivec;

vector< string > svec;

list< int >     ilist;

 

(a) vector< int>:: iterator it = ivec.begin();

(b) list< int>:: iterator it = ilist.begin()+2;

(c) vector< string>:: iterator it = & svec[0];

(d) for ( vector< string>:: iterator

      it = svec.begin(); it! = 0; ++it )

//...

Упражнение 6.10

Найдите ошибки в использовании итераторов:

int ia[7] = { 0, 1, 1, 2, 3, 5, 8 };

string sa[6] = {

" Fort Sumter", " Manassas", " Perryville", " Vicksburg",

" Meridian", " Chancellorsvine" };

 

(a) vector< string> svec( sa, & sa[6] );

(b) list< int> ilist( ia+4, ia+6 );

(c) list< int> ilist2( ilist.begin(), ilist.begin()+2 );

(d) vector< int> ivec( & ia[0], ia+8 );

(e) list< string> slist( sa+6, sa );

(f) vector< string> svec2( sa, sa+6 );

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: