Контейнеры 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 ); |
При каждом вызове функции-члена 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" ), |
Контейнер multimap не поддерживает операцию взятия индекса. Поэтому следующее выражение ошибочно:
authors[ "Barth, John" ]; // ошибка: multimap
Упражнение 6.28
Перепишите программу текстового поиска из раздела 6.14 с использованием multimap для хранения позиций слов. Каковы производительность и дизайн в обоих случаях? Какое решение вам больше нравится? Почему?
