Карты и мультикарты
Карты являются ассоциативными контейнерами и очень похожи на множества за исключением того, что в картах с ключами можно связать объекты произвольного типа. Ключ, таким образом, может служить своего рода индексом, по которому можно получить доступ к ассоциированному объекту. Соответственно, на картах определена операция индексации.
Ключевые значения в картах должны быть уникальны, в мультикартах они могут повторяться. Данные хранятся сортированными по ключевым значениям.
В общем, работа с картами практически ничем не отличается от работы с множествами. Только объявление карты выглядит несколько по-другому, поскольку в нем нужно указать дополнительно тип ассоциированных объектов.
Создание карт
В объявлении карты (мультикарты) требуется указать три аргумента шаблона: тип ключа, тип ассоциированного значения и класс функционального объекта, которым будет определяться способ упорядочения ключей. Обычно для простоты типу карты присваивается новое имя:
typedef map<string, double, less<string> > map_type;
Ключи такого контейнера будут строками, а ассоциированные объекты — значениями типа double. Сортирована карта будет в соответствии с алфавитным порядком ключей.
Кроме того, иногда бывает удобно объявить имя для типа элемента карты (т. е. по сути структуры, состоящей из ключа и ассоциированного типа объекта; подобные типы определяются с помощью шаблона pair<Tl, Т2>):
typedef map type::value_type val_type;
Обычно создается пустая карта, а затем в нее вводятся элементы функцией insert () . Возможно также конструирование новой карты из части уже существующей. При этом конструктору передаются, как обычно, два итератора.
Действия над картами
Важнейшие действия, выполняемые с картами и мультикартами — это поиск и извлечение данных по заданному ключу. Вообще-то карты в этом смысле практически полностью аналогичны множествам и имеют те же функции-элементы. Ниже приводится программа, демонстрирующая вариант “записной книжки” на основе мультикарты, которая может хранить несколько телефонных номеров для одного и того же имени-ключа. Нечто подобное мы уже делали в главе 8, когда говорили о перегрузке операции индексации, но индекс должен быть уникальным, а мультикарта позволяет иметь повторяющиеся ключи.
///////////////////////////////////////////////////////
// Multimap.срр: Макет телефонной книжки на основе multimap.
//
#include <iostream>
#include <iomanip>
#include <map>
#pragma hdrstop using namespace std;
struct Phone {
long pn;
Phone(long n = 0): pn(n) {} };
typedef multimap<string. Phone, less<string> > map_type;
typedef map type::value type val type;
typedef map_type::iterator i_type;
//
// Выводит элемент multimap (т.е. пару (string. Phone)).
//
ostreams operator“(ostream& os, const val_type& v)
{
os << setiosflags(ios::left)<< setfill('.')
<< setw(20) << v.first
<<resetiosflags(ios::left) << setfill('0')
<< setw(3) << v.second.pn / 10000 << "-"
<< setw(4)<< v.second.pn % 10000 << setfill(' ');
return os;
}
//
// Выводит "структуру" Phone.
//
ostreamS operator“(ostreamS os. Phone p)
(
os << setw(20) << "" << setfill('0')
<< setw(3) << p.pn / 10000 << "-"
<< setw(4)<< p.pn % 10000<< setfill(' ');
return os;
}
//
// Распечатка всех номеров, относящихся к одному имени.
// Возвращает итератор, ссылающийся на первую запись с
// другим именем. Обратите внимание на функцию
// equal range(), возвращающую структуру pair.
//
i_type Retrieve(ostreams os, map_type& mp, string name)
{
pair<i__type, i type>
r = mp.equal_range(name);
// Временная карта, конструированная по паре итераторов:
map_type b(r.first, r.second);
if (b.empty())
cout << "*** No such name! ***" << endl;
else {
i type p = b. begin ();
os << *p++ << endl; // Распечатать ключ и номер.
while (p != b.end())
os << (p++)->second << endi; // Для остальных
// только номер.
} return r.second;
}
//
// Распечатка всей карты.
//
void Printout'(ostream& os, map_type& mp, i_type from)
{
while (from != mp.endO) // Если не пустая,
// распечатать
from = Retrieve (os, mp, from->first);
// все номера
// первого ключа
//и перейти к
// следующему.
os << "*** End of the book ***" << endl;
}
ostreamS operator<<(ostreamb os, map_type& v) {
Printout (os, v, v.begin ());
return os;
}
int main() {
map type book;
// Попробуем распечатать пустую карту...
cout << "Contents of a new book:" << end1;
cout << book << endl;
book.insert(val_type("Petrov", 1653318));
book.insert(val_type("Ivanov", 2640535));
book.insert(val_type("Sidorov", 2340711));
book.insert(val_type("Ivanov", 4720415));
book.insert(val_type("Petrov", 1770212));
book.insert(val_type("Pavlov", 5551703));
book.insert(val_type("Ivanov", 4722306)) ;
// Распечатка.
cout << "Contents of the phone book:" << endl;
cout << book << end1;
// Поиск отдельных имен.
cout << "Searching Petrov... " << endl;
Retrieve(cout, book, "Petrov");
cout << "Searching Kozlov... " << end1;
Retrieve(cout, book, "Kozlov");
return 0;
}
Поиск нужного имени в этой программе выполняется функцией equal_range (), которая возвращает пару итераторов (структуру pair), ссылающихся на начало и конец диапазона с одним и тем же заданным ключом (если он присутствует).
Результат запуска программы показан на рис. 11.2.
Рис. 11.2 Вывод программы Multimap
