Язык программирования C++. Вводный курс. С для начинающих
 Скачать 5.41 Mb.
|
|
254 Использование push_back() ilist.push_back( ia[ ix ] ); создаст последовательность 0, 1, 2, 3, а push_front() ilist.push_front( ia[ ix ] ); создаст последовательность 3, 2, 1, 0. 13 Мы можем при создании явно указать размер массива – как константным, так и неконстантным выражением: vector< string > svec(get_word_count(string("Chimera"))); Каждый элемент контейнера инициализируется значением по умолчанию, соответствующим типу данных. Для int это 0. Для строкового типа вызывается конструктор по умолчанию класса string. Мы можем указать начальное значение всех элементов: vector< string > svec( 24, "pooh" ); Разрешается не только задавать начальный размер контейнера, но и впоследствии изменять его с помощью функции-члена resize(). Например: svec.resize( 2 * svec.size() ); Размер svec в этом примере удваивается. Каждый новый элемент получает значение по умолчанию. Если мы хотим инициализировать его каким-то другим значением, то оно указывается вторым параметром функции-члена resize(): 13 Если функция-член push_front() используется часто, следует применять тип deque, а не vector : в deque эта операция реализована наиболее эффективно. for ( int ix=0; ix<4; ++ix ) for ( int ix=0; ix<4; ++ix ) #include #include #include С++ для начинающих 255 svec.resize( 2 * svec.size(), "piglet" ); Кстати, какова наиболее вероятная емкость svec при определении, если его начальный размер равен 24? Правильно, 24! В общем случае минимальная емкость вектора равна его текущему размеру. При удвоении размера емкость, как правило, тоже удваивается Мы можем инициализировать новый контейнер с помощью существующего. Например: 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 Существуют три ограничения на тип элементов контейнера (практически это касается только пользовательских классов). Для должны быть определены: • операция “равно”; • операция “меньше” (все операции сравнения контейнеров, о которых говорилось выше, используют только эти две операции сравнения); • значение по умолчанию (для класса это означает наличие конструктора по умолчанию). // каждый новый элемент получает значение "piglet" vector< string > svec2( svec ); С++ для начинающих 256 Все предопределенные типы данных, включая указатели и классы из стандартной библиотеки С++ удовлетворяют этим требованиям. Упражнение 6.5 Объясните, что делает данная программа: } Упражнение 6.6 Может ли емкость контейнера быть меньше его размера? Желательно ли, чтобы емкость была равна размеру: изначально или после вставки элемента? Почему? Упражнение 6.7 Если программа из упражнения 6.5 прочитает 256 слов, то какова наиболее вероятная емкость контейнера после изменения размера? А если она считает 512 слов? 1000? 1048? Упражнение 6.8 Какие из данных классов не могут храниться в векторе: #include #include #include #int main() { vector // ... С++ для начинающих 257 } 6.5. Итераторы Итератор предоставляет обобщенный способ перебора элементов любого контейнера – как последовательного, так и ассоциативного. Пусть iter является итератором для какого-либо контейнера. Тогда ++iter; перемещает итератор так, что он указывает на следующий элемент контейнера, а *iter; разыменовывает итератор, возвращая элемент, на который он указывает. Все контейнеры имеют функции-члены begin() и end(). • begin() возвращает итератор, указывающий на первый элемент контейнера. • end() возвращает итератор, указывающий на элемент, следующий за последним в контейнере. Чтобы перебрать все элементы контейнера, нужно написать: (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!=(); // ... for ( iter = container. begin(); iter != container.end(); ++iter ) С++ для начинающих 258 do_something_with_element( *iter ); Объявление итератора выглядит слишком сложным. Вот определение пары итераторов вектора типа string: vector В классе vector для определения iterator используется typedef. Синтаксис vector Для того чтобы напечатать все элементы вектора, нужно написать: cout << *iter << '\n'; Здесь значением *iter выражения является, конечно, элемент вектора. В дополнение к типу iterator в каждом контейнере определен тип const_iterator, который необходим для навигации по контейнеру, объявленному как const. const_iterator позволяет только читать элементы контейнера: } Что делать, если мы хотим просмотреть некоторое подмножество элементов, например взять каждый второй или третий элемент, или хотим начать с середины? Итераторы поддерживают адресную арифметику, а значит, мы можем прибавить некоторое число к итератору: vector // vector #include { // const_iterator необходим для навигации по pvec vector С++ для начинающих 259 iter += 2; сдвигает iter на два элемента. Арифметические действия с итераторами возможны только для контейнеров vector и deque . list не поддерживает адресную арифметику, поскольку его элементы не располагаются в непрерывной области памяти. Следующее выражение к списку неприменимо: ilist.begin() + 2; так как для перемещения на два элемента необходимо два раза перейти по адресу, содержащемуся в закрытом члене next. У классов vector и deque перемещение на два элемента означает прибавление 2 к указателю на текущий элемент. (Адресная арифметика рассматривается в разделе 3.3.) Объект контейнерного типа может быть инициализирован парой итераторов, обозначающих начало и конец последовательности копируемых в новый объект элементов. (Второй итератор должен указывать на элемент, следующий за последним копируемым.) Допустим, есть вектор: } Вот как можно определить новые векторы, инициализируя их элементами первого вектора: } #include #include #include { vector // обработать svec ... int main() { vector // ... // инициализация svec2 всеми элементами svec vector // инициализация svec3 первой половиной svec vector // ... С++ для начинающих 260 Использование специального типа istream_iterator (о нем рассказывается в разделе 12.4.3) упрощает чтение элементов из входного потока в svec: } Кроме итераторов, для задания диапазона значений, инициализирующих контейнер, можно использовать два указателя на массив встроенного типа. Пусть есть следующий массив строк: }; Мы можем инициализировать вектор с помощью указателей на первый элемент массива и на элемент, следующий за последним: vector< string > vwords( words, words+4 ); Второй указатель служит “стражем”: элемент, на который он указывает, не копируется. Аналогичным образом можно инициализировать список целых элементов: list< int > ilist( ia, ia+6 ); В разделе 12.4 мы снова обратимся к итераторам и опишем их более детально. Сейчас информации достаточно для того, чтобы использовать итераторы в нашей системе текстового поиска. Но прежде чем вернуться к ней, рассмотрим некоторые дополнительные операции, поддерживаемые контейнерами. Упражнение 6.9 Какие ошибки допущены при использовании итераторов: #include #include #include { // привязка istream_iterator к стандартному вводу istream_iterator // istream_iterator, отмечающий конец потока istream_iterator // инициализация svec элементами, считываемыми из cin; vector // ... #include "stately", "plump", "buck", "mulligan" int ia[6] = { 0, 1, 2, 3, 4, 5 }; С++ для начинающих 261 // ... Упражнение 6.10 Найдите ошибки в использовании итераторов: (f) vector 6.6. Операции с последовательными контейнерами Функция-член push_back() позволяет добавить единственный элемент в конец контейнера. Но как вставить элемент в произвольную позицию? А целую последовательность элементов? Для этих случаев существуют более общие операции. Например, для вставки элемента в начало контейнера можно использовать: svec.insert( svec.begin(), spouse ); Первый параметр функции-члена insert() (итератор, адресующий некоторый элемент контейнера) задает позицию, а второй – вставляемое перед этой позицией значение. В примере выше элемент добавляется в начало контейнера. А так можно реализовать вставку в произвольную позицию: const vector< int > ivec; vector< string > svec; list< int > ilist; (a) vector (b) list (c) vector (d) for ( vector "Fort Sumter", "Manassas", "Perryville", "Vicksburg", "Meridian", "Chancellorsvine" }; (a) vector (b) list (c) list (d) vector (e) list С++ для начинающих 262 slist.insert( iter, spouse ); Здесь find() возвращает позицию элемента в контейнере, если элемент найден, либо итератор end(), если ничего не найдено. (Мы вернемся к функции find() в конце следующего раздела.) Как можно догадаться, push_back() эквивалентен следующей записи: slist.insert( slist.end(), value ); Вторая форма функции-члена insert() позволяет вставить указанное количество одинаковых элементов, начиная с определенной позиции. Например, если мы хотим добавить десять элементов Anna в начало вектора, то должны написать: svec.insert( svec.begin(), 10, anna ); insert() имеет и третью форму, помогающую вставить в контейнер несколько элементов. Допустим, имеется следующий массив: string sarray[4] = { "quasi", "simba", "frollo", "scar" }; Мы можем добавить все его элементы или только некоторый диапазон в наш вектор строк: sarray+2, sarray+4 ); Такой диапазон отмечается и с помощью пары итераторов svec.begin(), svec.end() ); string son( "Danny" ); list // эквивалентный вызов: slist.push_back( value ); vector // вставляем элементы svec // в середину svec_two svec_two.insert( svec_two.begin() + svec_two.size()/2, С++ для начинающих 263 или любого контейнера, содержащего строки: 14 slist.insert( iter, svec.begin(), svec.end() ); 6.6.1. Удаление В общем случае удаление осуществляется двумя формами функции-члена erase(). Первая форма удаляет единственный элемент, вторая – диапазон, отмеченный парой итераторов. Для последнего элемента можно воспользоваться функцией-членом pop_back() При вызове erase() параметром является итератор, указывающий на нужный элемент. В следующем фрагменте кода мы воспользуемся обобщенным алгоритмом find() для нахождения элемента и, если он найден, передадим его адрес функции-члену erase(). slist.erase( iter ); Для удаления всех элементов контейнера или некоторого диапазона можно написать следующее: slist.erase( first, last ); 14 Последняя форма insert() требует, чтобы компилятор работал с шаблонами функций-членов. Если ваш компилятор еще не поддерживает это свойство стандарта С++, то оба контейнера должны быть одного типа, например два списка или два вектора, содержащих элементы одного типа. list< string > slist; // ... // вставляем элементы svec // перед элементом, содержащим stringVal list< string >::iterator iter = find( slist.begin(), slist.end(), stringVal ); string searchValue( "Quasimodo" ); list< string >::iterator iter = find( slist.begin(), slist.end(), searchValue ); if ( iter != slist.end() ) // удаляем все элементы контейнера slist.erase( slist.begin(), slist.end() ); // удаляем элементы, помеченные итераторами list< string >::iterator first, last; first = find( slist. begin(), slist.end(), vail ); last = find( slist.begin(), slist.end(), va12 ); // ... проверка first и last С++ для начинающих 264 Парной по отношению к push_back() является функция-член pop_back(), удаляющая из контейнера последний элемент, не возвращая его значения: } 6.6.2. Присваивание и обмен Что происходит, если мы присваиваем один контейнер другому? Оператор присваивания копирует элементы из контейнера, стоящего справа, в контейнер, стоящий слева от знака равенства. А если эти контейнеры имеют разный размер? Например: svecl = svec2; Контейнер-адресат (svec1) теперь содержит столько же элементов, сколько контейнер- источник (svec2). 10 элементов, изначально содержавшихся в svec1, удаляются (для каждого из них вызывается деструктор класса string). Функция обмена swap() может рассматриваться как дополнение к операции присваивания. Когда мы пишем: svecl.swap( svec2 ); svec1 после вызова функции содержит 24 элемента, которые он получил бы в результате присваивания: svecl = svec2; но зато теперь svec2 получает 10 элементов, ранее находившихся в svec1. Контейнеры “обмениваются” своим содержимым. 6.6.3. Обобщенные алгоритмы Операции, описанные в предыдущих разделах, составляют набор, поддерживаемый непосредственно контейнерами vector и deque. Согласитесь, что это весьма небогатый интерфейс и ему явно не хватает базовых операций find(), sort(), merge() и т.д. Планировалось вынести общие для всех контейнеров операции в набор обобщенных алгоритмов, которые могут применяться ко всем контейнерным типам, а также к массивам встроенных типов. (Обобщенные алгоритмы описываются в главе 12 и в Приложении.) Эти алгоритмы связываются с определенным типом контейнера с vector< string >::iterator iter = buffer.begin(); for ( ; iter != buffer.end(), iter++ ) { slist.push_back( *iter ); if ( ! do_something( slist )) slist.pop_back(); // svecl содержит 10 элементов // svec2 содержит 24 элемента // после присваивания оба содержат по 24 элемента С++ для начинающих 265 помощью передачи им в качестве параметров пары соответствующих итераторов. Вот как выглядят вызовы алгоритма find() для списка, вектора и массива разных типов: viter = find( svec.begin(), svec.end(), some_string_value ); Контейнер list поддерживает дополнительные операции, такие, как sort() и merge(), поскольку в нем не реализован произвольный доступ к элементам. (Эти операции описаны в разделе 12.6.) Теперь вернемся к нашей поисковой системе. Упражнение 6.11 Напишите программу, в которой определены следующие объекты: vector Используя различные операции вставки и подходящие значения ia, ia2 и ia3, модифицируйте вектор ivec так, чтобы он содержал последовательность: { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 } Упражнение 6.12 Напишите программу, определяющую данные объекты: list Используя функцию-член erase() с одним параметром, удалите из ilist все нечетные элементы. #include #include // соответствующий заголовочный файл #include #int *pia; // find() возвращает итератор на найденный элемент // для массива возвращается указатель ... pia = find( &ia[0], &ia[6], some_int_value ); liter = find( dlist.begin(), dlist.end(), some_double_value ); int ia[] = { 1, 5, 34 }; int ia2[] = { 1, 2, 3 }; int ia3[] = { 6, 13, 21, 29, 38, 55, 67, 89 }; int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 }; |