С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 43
Текст из файла (страница 43)
Но прежде чемприступать к реализации, посмотрим, как определяется объект контейнерного типа.Упражнение 6.2Объясните разницу между размером и емкостью контейнера. Почему понятие емкостинеобходимо для контейнера, содержащего элементы в непрерывной области памяти, и ненужно для списка?Упражнение 6.3Почему большие сложные объекты удобнее хранить в контейнере в виде указателей наних, а для коллекции целых чисел применение указателей снижает эффективность?Упражнение 6.4Объясните, какой из типов контейнера – вектор или список – больше подходит дляприведенных примеров (во всех случаях происходит вставка неизвестного заранее числаэлементов):.(a) Целые числа(b) Указатели на большие сложные объекты(c) Большие сложные объекты6.4.
Как определить последовательный контейнер?Для того чтобы определить объект контейнерного типа, необходимо сначала включитьсоответствующий заголовочный файл:С++ для начинающих#include#inclnde#include#include253<vector><list><deque><map>#include <set>Определение контейнера начинается именем его типа, за которым в угловых скобкахvector< string > svec;следует тип данных его элементов12. Например:list< int >ilist;Переменная svec определяется как вектор, способный содержать элементы типа string,а ilist – как список с элементами типа int.
Оба контейнера при таком определенииif ( svec.empty() != true )пусты. Чтобы убедиться в этом, можно вызвать функцию-член empty():; // что-то не такПростейший метод вставки элементов – использование функции-члена 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.Применение распределителя памяти преследует две цели: упростить реализациюконтейнеров путем отделения всех деталей, касающихся работы с памятью, и позволитьпрограммисту при желании реализовать собственную стратегию выделения памяти.Определения объектов для компилятора, не поддерживающего значения по умолчаниюпараметров шаблонов, выглядят следующим образом: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")));Каждый элемент контейнера инициализируется значением по умолчанию,соответствующим типу данных.
Для int это 0. Для строкового типа вызываетсяконструктор по умолчанию класса string.list< int > ilist( list_size, -1 );Мы можем указать начальное значение всех элементов:vector< string > svec( 24, "pooh" );Разрешается не только задавать начальный размер контейнера, но и впоследствииизменять его с помощью функции-члена resize(). Например:svec.resize( 2 * svec.size() );Размер svec в этом примере удваивается. Каждый новый элемент получает значение поумолчанию.
Если мы хотим инициализировать его каким-то другим значением, то оноуказывается вторым параметром функции-члена resize():13 Если функция-член push_front() используется часто, следует применять тип deque,а не vector: в deque эта операция реализована наиболее эффективно.254С++ для начинающих255// каждый новый элемент получает значение "piglet"svec.resize( 2 * svec.size(), "piglet" );Кстати, какова наиболее вероятная емкость svec при определении, если его начальныйразмер равен 24? Правильно, 24! В общем случае минимальная емкость вектора равна еготекущему размеру. При удвоении размера емкость, как правило, тоже удваиваетсяvector< string > svec2( svec );Мы можем инициализировать новый контейнер с помощью существующего. Например:list< int >ilist2( ilist ) ;Каждый контейнер поддерживает полный набор операций сравнения: равенство,неравенство, меньше, больше, меньше или равно, больше или равно.
Сопоставляютсяпопарно все элементы контейнера. Если они равны и размеры контейнеров одинаковы, тоэти контейнеры равны; в противном случае – не равны. Результат операций “больше”или “меньше” определяется сравнением первых двух неравных элементов. Вот чтопечатает программа, сравнивающая пять векторов:ivecl:ivec2:ivec3:ivec4:ivec5:10112313345 7 9 121 2 3 5 8 1395 7// первый неравный элемент: 1, О// ivecl больше чем ivec2ivecl < ivec2 //falseivec2 < ivecl //true// первый неравный элемент: 5, 9ivecl < ivec3 //true// все элементы равны, но ivec4 содержит меньше элементов// следовательно, ivec4 меньше, чем iveclivecl < ivec4 //false// первый неравный элемент: 1, 2ivecl < ivec5 //trueivecl == ivecl //trueivecl == ivec4 //falseivecl != ivec4 //trueivecl > ivec2 //trueivec3 > ivecl //trueivec5 > 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Какие из данных классов не могут храниться в векторе:256С++ для начинающих(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!=();// ...}6.5.
ИтераторыИтератор предоставляет обобщенный способ перебора элементов любого контейнера –как последовательного, так и ассоциативного. Пусть iter является итератором длякакого-либо контейнера. Тогда++iter;перемещает итератор так, что он указывает на следующий элемент контейнера, а*iter;разыменовывает итератор, возвращая элемент, на который он указывает.Все контейнеры имеют функции-члены begin() и end().•begin() возвращает итератор, указывающий на первый элемент контейнера.•end() возвращает итератор, указывающий на элемент, следующий запоследним в контейнере.for ( iter = container. begin();iter != container.end(); ++iter )Чтобы перебрать все элементы контейнера, нужно написать:257С++ для начинающихdo_something_with_element( *iter );Объявление итератора выглядит слишком сложным.
Вот определение пары итераторов// vector<string> vec;vector<string>::iterator iter = vec.begin();вектора типа string: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.#include <vector>void even_odd( const vector<int> *pvec,vector<int> *pvec_even,vector<int> *pvec_odd ){// const_iterator необходим для навигации по pvecvector<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 );const_iterator позволяет только читать элементы контейнера:}Что делать, если мы хотим просмотреть некоторое подмножество элементов, напримервзять каждый второй или третий элемент, или хотим начать с середины? Итераторыподдерживают адресную арифметику, а значит, мы можем прибавить некоторое число китератору:vector<int>::iterator iter = vec->begin()+vec.size()/2;iter получает значение адреса элемента из середины вектора, а выражение258С++ для начинающихiter += 2;сдвигает iter на два элемента.Арифметические действия с итераторами возможны только для контейнеров vector иdeque.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
