Контейнеры типа 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();
pI= h.end(); p++)
cout << "\n" << p › first
<<". " << p › second;
//====== Выбираем диапазон (сотрудники 100-го отдела)
pair<ManMapIt, 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";
}
Не лишнее напомнить, что приведенный код надо дополнить объявлениями объектов класса 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