Контейнеры типа hash_multimap
Контейнеры типа 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
