hash_set. Однако помните, что они не входят в число стандартных контейнеров, определяемых стандартом С++, а представляют собой расширения, включаемые большинством реализаций стандартной библиотеки. Пример 6.8 показывает, как использовать hash_set.
#include <iostream>
#include <string>
#include <hash_set>
int main() {
hash_set<std::string> hsString;
string s = 'bravo';
hsString.insert(s);
s = 'alpha';
hsString.insert(s);
s = 'charlie';
hsString.insert(s);
for (hash set<string>::const_iterator p = hsString.begin();
p != hsString.end(); ++p)
cout << *p << endl; // заметьте, что здесь не гарантируется хранение
// в упорядоченном виде
}
Контейнеры, основанные на хешах, — это популярные во всех языках структуры данных, и прискорбно, что стандарт C++ не требует их реализации. Однако если требуется использовать хеш- контейнер, то не все потеряно: высока вероятность, что используемая вами реализация стандартной библиотеки содержит hash_map и hash_set, но тот факт, что они не стандартизованы, означает, что их интерфейсы могут отличаться от одной реализации стандартной библиотеки к другой. Я опишу хеш-контейнеры, которые поставляются в составе реализации стандартной библиотеки STLPort.
STLPort — это свободно распространяемая переносимая реализация стандартной библиотеки, существующая уже довольно длительное время и предоставляющая хеш- контейнеры. При использовании другой библиотеки интерфейс может быть другим, но общая идея будет той же самой.
Главной особенностью хеш-контейнеров (называемых во многих книгах по ассоциативными хеш- контейнерами) является то, что они в общем случае предоставляют постоянное время поиска, вставки и удаления элементов, а в худшем случае эти операции имеют линейное время. Ценой постоянного времени выполнения этих операций является то, что в хеш-контейнере они хранятся в неупорядоченном виде, как в map.
Посмотрите на пример 6.8. Использование хеш-контейнера (в данном случае hash_set) довольно просто — объявите его как большинство других контейнеров и начните вставлять в него элементы.
hash_set<string> hsString; // hash_set строк
string s = 'bravo';
hsString.insert(s); // Вставка копии s
Использование hash_map аналогично, за исключением того, что требуется, как минимум, указать типы данных используемых ключей и значений. Это аналогично map.
hash_map<string, string>
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<Key, // Тип ключа
Value, // Тип значения,
// связанного с ключом
HashFun = hash<Key>, // Используемая хеш-функция
EqualKey = equal_to<Key> // Функция, используемая для
// проверки равенства ключей
Alloc = alloc>; // Используемый распределитель памяти
hash_set<Key, // Тип ключа
HashFun = hash<Key>, // Используемая хеш-функция
EqualKey = equal_to<Key>, // Функция, используемая для
// проверки равенства ключей
Alloc = alloc>; // Используемый распределитель памяти
hash_map — это хеш-таблица, которая хранит значения как объекты pair<const Key, Data>. Это означает, что когда я буду далее описывать хеш-таблицы, «элементы» в таблице будут означать пары ключ/значение. hash_map не хранит ключи значение по отдельности (как и map). hash_set просто хранит ключ как значение.
Параметр шаблона HashFun — это функция, которая превращает объекты типа Key в значения, которые могут быть сохранены как size_t. Более подробно это описывается ниже. Параметр шаблона EqualKey — это функция, которая принимает два аргумента и, если они эквивалентны, возвращает true. В контейнерах hash_map и hash_set два ключа не могут быть равны, hash_multimap и hash_multiset могут содержать по нескольку одинаковых ключей. Как и в случае с другими контейнерами, Alloc — это используемый распределитель памяти.
Хеш-таблица содержит две части. В ней есть относительно большой вектор, где каждый индекс это «участок». Каждый из участков является на самом деле указателем на первый узел в относительно коротком одно- или двухсвязном списке (в STLPort — односвязном). Именно в этих списках и хранятся данные. Чтобы получить число участков в хеш-контейнере, используйте метод bucket_count. Рисунок 6.3 дает представление о том, как выглядит в памяти хеш-отображение.
Рис. 6.3. Хеш-таблица
Рассмотрим использование hash_set из примера 6.8. При вставке элемента контейнер вначале должен определить, к какому участку он относится. Это делается с помощью вызова хеш-функции
