6.15. Контейнеры 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 для хранения позиций слов. Каковы производительность и дизайн в обоих случаях? Какое решение вам больше нравится? Почему?