Хешированный ассоциативный контейнер типа
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 |