6.15. Контейнеры multimap и multiset
6.15. Контейнеры multimap и multiset
Контейнеры map и set не допускают повторяющихся значений ключей, а multimap (мультиотображение) и multiset (мультимножество) позволяют сохранять ключи с дублирующимися значениями. Например, в телефонном справочнике может понадобиться отдельный список номеров для каждого абонента. В перечне книг одного автора может быть несколько названий, а в нашей программе с одним словом текста сопоставляется несколько позиций. Для использования multimap и multiset нужно включить соответствующий заголовочный файл – map или set:
#include map
multimap key_type, value_type multimapName;
Для прохода по мультиотображению или мультимножеству можно воспользоваться комбинацией итератора, который возвращает 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 multimapstring,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 - multimapstring, string
// эквивалентно
// authors.erase( search_item );
pos = authors.equa1_range( search_item );
authors.erase( pos.first, pos.second );
При каждом вызове функции-члена insert() добавляется новый элемент, даже если в контейнере уже был элемент с таким же ключом. Например:
typedef multimapstring,string::value_type valType;
multimapstring,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 для хранения позиций слов. Каковы производительность и дизайн в обоих случаях? Какое решение вам больше нравится? Почему?