Контейнеры типа hash_multimap

Хешированный ассоциативный контейнер типа hash_multimap основан на встроенной реализации хэш-таблиц. Вы помните, что преимуществом такого типа контейнеров является быстродействие, которое в среднем значительно выше, чем у сортированных ассоциативных контейнеров. Упорядоченность элементов в таком контейнере не гарантируется, но вы можете по определенной системе добывать их С ПОМОЩЬЮ метода hash_multimap: :equal_range.

Предположим, что ваша база данных содержит сведения о сотрудниках — объектах класса Man, многих отделов какой-то организации. В примере мы возьмем только два отдела (100 и 115). Так как мы хотим быстро получать информацию о сотрудниках, то выбираем в качестве структуры для хранения данных в памяти хешированный ассоциативный контейнер. Очевидно, что если в качестве ключевого поля для него выбрать номер отдела, то поле не будет уникальным. Этот факт окончательно определяет выбор типа контейнера— hash_multimap.

Вы также, вероятно, помните, что все контейнеры типа тар — это Pair Associative контейнеры, так как они хранят пары типа pair<const Key, Data>. В нашем случае этой парой является pair<int, Man>, где первый элемент задает номер отдела, а второй сотрудника этого отдела. Для удобства пользования контейнером введем новые типы данных:

//======= ManPair - это тип используемых пар

typedef pair <int, Man> ManPair;

//======= ManMap - это тип контейнера

typedef hash_multimap <int, Man> ManMap;

//======= ManMapIt — это тип итератора

typedef ManMap::const_iterator ManMapIt;

Отметьте, что мы выбрали самый простой способ определения контейнера. Более точным описанием, которое намекает вам на возможность усложнения структуры, будет:

typedef hash_multimap <int, Man,

hash_compare <int, less<int> > > ManMap;

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

equal_range (int /*Номер отдела*/);

который возвращает пару итераторов. Первый итератор пары указывает на начало диапазона внутри контейнера из сотрудников указанного отдела, а второй — на конец этого диапазона. Теперь пора в бой. Надо писать код, реализующий работу контейнера.

void main( )

{

typedef pair <int, Man> ManPair;

typedef hash_multimap <int, Man> ManMap;

typedef ManMap::const_iterator ManMapIt;

//====== Создаем пустой контейнер типа hash_multimap ManMap h;

//====== Наполняем его сотрудниками

h.insert (ManPair (100, тагу));

h.insert (ManPair (115, joe));

h.insert (ManPair (100, win));

h.insert (ManPair (100, charlie));

h.insert (ManPair (115, liza));

h.insert TManPair (115, joy));

//====== При выводе пользуемся парой

cout « "Contents of Hash Multimap\n\n";

for (ManMapIt p = h.begin();

p != h.end(); p++)

cout « "\n" « p->first

«". " « p->second;

//====== Выбираем диапазон (сотрудники 100-го отдела)

pair<ManMap!t, ManMapIt> pp = h.equal_range(100);

//====== Вновь пользуемся парой

cout « "\n\nEmployees of 100 department\n\n";

for (p = pp.first; p != pp.second; ++p)

cout « "\n" « p->first

«"." « p->second; cout « "\n\n";

}

He лишнее напомнить, что приведенный код надо дополнить объявлениями объектов класса Man и вставкой директивы #include <hash_map>. Директивы должны копиться. Я надеюсь, что с этой задачей вы справитесь самостоятельно. Объявления людей мы приводили где-то в начале урока. Программа должна произвести такой вывод:

Contents of Hash Multimap

115. Liza Dale, Age: 17

115. Joy Amore, Age: 18

115. Joe Doe, Age: 30

100. Winton Kelly, Age: 50

100. Charlie Parker, Age: 60

100. Mary Poppins, Age: 36

Employees of 100 department

100. Winton Kelly, Age: 50

100. Charlie Parker, Age: 60

100. Mary Poppins, Age: 36