C++. Сборник рецептов

Контейнеры, основанные на хешах, — это популярные во всех языках структуры данных, и прискорбно, что стандарт C++ не требует их реализации. Однако если требуется использовать хеш-контейнер, то не все потеряно: высока вероятность, что используемая вами реализация стандартной библиотеки содержит hash_map и hash_set, но тот факт, что они не стандартизованы, означает, что их интерфейсы могут отличаться от одной реализации стандартной библиотеки к другой. Я опишу хеш-контейнеры, которые поставляются в составе реализации стандартной библиотеки STLPort.

STLPort — это свободно распространяемая переносимая реализация стандартной библиотеки, существующая уже довольно длительное время и предоставляющая хеш-контейнеры. При использовании другой библиотеки интерфейс может быть другим, но общая идея будет той же самой.

Главной особенностью хеш-контейнеров (называемых во многих книгах по ассоциативными хеш-контейнерами) является то, что они в общем случае предоставляют постоянное время поиска, вставки и удаления элементов, а в худшем случае эти операции имеют линейное время. Ценой постоянного времени выполнения этих операций является то, что в хеш-контейнере они хранятся в неупорядоченном виде, как в map.

Посмотрите на пример 6.8. Использование хеш-контейнера (в данном случае hash_set) довольно просто — объявите его как большинство других контейнеров и начните вставлять в него элементы.

hash_set hsString; // hash_set строк

string s = "bravo";

hsString.insert(s); // Вставка копии s

Использование hash_map аналогично, за исключением того, что требуется, как минимум, указать типы данных используемых ключей и значений. Это аналогично map.

hash_map

hmStrings; // Отображение строк на строки

string key = "key";

string val = "val";

hmStrings[key] = val;

Это только основы использования хеш-контейнеров. Также имеется набор параметров шаблона, которые позволяют указать используемую хеш-функцию, функцию, проверяющую ключи на эквивалентность, и объект, используемый для распределения памяти. Я опишу их немного позже.

В большинстве библиотек есть четыре хеш-контейнера, и они похожи на другие ассоциативные контейнеры стандартной библиотеки (т.е. map и set). Это hash_map, hash_multimap, hash_set и hash_multiset. хеш-контейнеры реализуются с помощью хеш- таблицы. Хеш-таблица — это структура данных, которая обеспечивает постоянное время доступа к элементам, используя для этого хеш-функцию перехода к месту, близкому к хранению искомого объекта, а не проход по древовидной структуре. Разница между hash_map и hash_set состоит в том, как данные хранятся в хеш-таблице.

Объявления контейнеров, использующих хеш-таблицу, в STLPort выглядят так.

hash_map

 Value,                   // Тип значения,

                          // связанного с ключом

 HashFun = hash,     // Используемая хеш-функция

 EqualKey = equal_to // Функция, используемая для

                          // проверки равенства ключей

 Alloc = alloc>;          // Используемый распределитель памяти

hash_set

 HashFun = hash,      // Используемая хеш-функция

 EqualKey = equal_to, // Функция, используемая для

                           // проверки равенства ключей

 Alloc = alloc>;           // Используемый распределитель памяти

hash_map — это хеш-таблица, которая хранит значения как объекты pair. Это означает, что когда я буду далее описывать хеш-таблицы, «элементы» в таблице будут означать пары ключ/значение. hash_map не хранит ключи значение по отдельности (как и map). hash_set просто хранит ключ как значение.

Параметр шаблона HashFun — это функция, которая превращает объекты типа Key в значения, которые могут быть сохранены как size_t. Более подробно это описывается ниже. Параметр шаблона EqualKey — это функция, которая принимает два аргумента и, если они эквивалентны, возвращает true. В контейнерах hash_map и hash_set два ключа не могут быть равны, hash_multimap и hash_multiset могут содержать по нескольку одинаковых ключей. Как и в случае с другими контейнерами, Alloc — это используемый распределитель памяти.