Контейнеры multimap и multiset

Контейнеры map и set не допускают повторяющихся значений ключей, а multimap (мультиотображение) и multiset (мультимножество) позволяют сохранять ключи с дублирующимися значениями. Например, в телефонном справочнике может понадобиться отдельный список номеров для каждого абонента. В перечне книг одного автора может быть несколько названий, а в нашей программе с одним словом текста сопоставляется несколько позиций. Для использования multimap и multiset нужно включить соответствующий заголовочный файл – map или set:

#include < map>

multimap< key_type, value_type > multimapName;

 

// ключ - string, значение - list< string >

multimap< string, list< string > > synonyms;

 

#include < set>

multiset< type > multisetName;

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

#include < map>

#include < string>

 

void code_fragment()

{

multimap< string, string > authors;

string search_item( " Alain de Botton" );

//...

int number = authors.count( search_item );

mu1timap< string, string >:: iterator iter;

 

iter = authors.find( search_item );

for ( int cnt = 0; cnt < number; ++cnt, ++-iter )

   do_something( *iter );

//...

}

Более элегантный способ перебрать все значения с одинаковыми ключами использует специальную функцию-член equal_range(), которая возвращает пару итераторов. Один из них указывает на первое найденное значение, а второй – на следующее за последним найденным. Если последний из найденных элементов является последним в контейнере, второй итератор содержит величину, равную end():

#include < map> #include < string> #include < utility>   void code_fragment() { multimap< string, string > authors; //... string search_item( " Haruki Murakami" );   while ( cin & & cin > > search_item )    switch ( authors.count( search_item ))    {      // не найдено      case 0:        break;       // найден 1, обычный find()     case 1: {       multimap< string, string >: iterator iter;       iter = authors.find( search_item );       // обработка элемента...       break;     }     // найдено несколько...     default:     {        typedef multimap< string, string>:: iterator iterator;        pair< iterator, iterator > pos;          // pos.first - адрес 1-го найденного        // pos.second - адрес 1-го отличного        // от найденного        pos = authors.equa1_range( search_item );        for (; pos.first! = pos.second; pos.first++ )                // обработка элемента...     }   } }

Вставка и удаление элементов в multimap и multiset ничем не отличаются от аналогичных операций с контейнерами map и set. Функция equal_range() доставляет итераторную пару, задающую диапазон удаляемых элементов:

#include < multimap> #include < string>   typedef multimap< string, string >:: iterator iterator; pair< iterator, iterator > pos; string search_item( " Kazuo Ishiguro" );   // authors - multimap< string, string> // эквивалентно // authors.erase( search_item ); pos = authors.equa1_range( search_item ); authors.erase( pos.first, pos.second );

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

typedef multimap< string, string>:: value_type valType;

multimap< string, string> authors;

 

// первый элемент с ключом Barth

authors.insert( valType (

string( " Barth, John" ),

string( " Sot-Weed Factor" )));

 

// второй элемент с ключом Barth

authors.insert( va1Type(

string( " Barth, John" ),

string( " Lost in the Funhouse" )));

Контейнер multimap не поддерживает операцию взятия индекса. Поэтому следующее выражение ошибочно:

authors[ " Barth, John" ]; // ошибка: multimap

Упражнение 6.28

Перепишите программу текстового поиска из раздела 6.14 с использованием multimap для хранения позиций слов. Каковы производительность и дизайн в обоих случаях? Какое решение вам больше нравится? Почему?

Стек

В разделе 4.5 операции инкремента и декремента были проиллюстрированы на примере реализации абстракции стека. В общем случае стек является очень полезным механизмом для сохранения текущего состояния, если в разные моменты выполнения программы одновременно существует несколько состояний, вложенных друг в друга. Поскольку стек – это важная абстракция данных, в стандартной библиотеке С++ предусмотрен класс stack, для использования которого нужно включить заголовочный файл:

#include < stack>

В стандартной библиотеке стек реализован несколько иначе, чем у нас. Разница состоит в том, что доступ к элементу с вершины стека и удаление его осуществляются двумя функциями – top() и pop(). Полный набор операций со стеком приведен в таблице 6.5.

Таблица 6.5. Операции со стеком

Операция	Действие
empty()	Возвращает true, если стек пуст, и false в противном случае
size()	Возвращает количество элементов в стеке
pop()	Удаляет элемент с вершины стека, но не возвращает его значения
top()	Возвращает значение элемента с вершины стека, но не удаляет его
push(item)	Помещает новый элемент в стек

 

В нашей программе приводятся примеры использования этих операций:

#include < stack> #include < iostream> int main() { const int ia_size = 10; int ia[ia_size ]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // заполним стек int ix = 0; stack< int > intStack; for (; ix < ia_size; ++ix ) intStack.push( ia[ ix ] );   int error_cnt = 0; if ( intStack.size()! = ia_size ) { cerr < < " Ошибка! неверный размер IntStack: "     < < intStack.size()     < < " \t ожидается: " < < ia_size < < endl, ++error_cnt; }   int value; while ( intStack.empty() == false ) { // считаем элемент с вершины value = intStack.top(); if ( value! = --ix ) {    cerr < < " Ошибка! ожидается " < < ix         < < " получено " < < value < < endl;    ++error_cnt; }   // удалим элемент intStack.pop(); }   cout < < " В результате запуска программы получено " < < error_cnt < < " ошибок" < < endl; }

Объявление

stack< int > intStack;

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

stack< int, list< int> > intStack;

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

#include < stack>

class NurbSurface { /* mumble */ };

stack< NurbSurface* > surf_Stack;

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

Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа

 

Civil & & ( War || Rights )

 

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

Поделиться: