C++ Программирование в среде С++ Builder 5

Карты и мультикарты


Карты являются ассоциативными контейнерами и очень похожи на множества за исключением того, что в картах с ключами можно связать объекты произвольного типа. Ключ, таким образом, может служить своего рода индексом, по которому можно получить доступ к ассоциированному объекту. Соответственно, на картах определена операция индексации.

Ключевые значения в картах должны быть уникальны, в мультикартах они могут повторяться. Данные хранятся сортированными по ключевым значениям.

В общем, работа с картами практически ничем не отличается от работы с множествами. Только объявление карты выглядит несколько по-другому, поскольку в нем нужно указать дополнительно тип ассоциированных объектов.

Создание карт

В объявлении карты (мультикарты) требуется указать три аргумента шаблона: тип ключа, тип ассоциированного значения и класс функционального объекта, которым будет определяться способ упорядочения ключей. Обычно для простоты типу карты присваивается новое имя:

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


Содержание раздела