— это прекрасный способ хранить пары ключ/значение. После того как вы поймете поведение его частей, таких как
operator[]
и хранение данных (в виде объектов
pair<Key, Value>
),
map
предоставит простоту в использовании и высокую производительность.
Смотри также
Рецепт 6.7.
6.7. Использование хеш-контейнеров
Проблема
Требуется сохранить ключи и значения, обеспечив постоянное время доступа к элементам, и не требуется хранения элементов в упорядоченном виде.
Решение
Используйте один из связанных с хешами контейнеров —
hash_map
или
hash_set
. Однако помните, что они не входят в число стандартных контейнеров, определяемых стандартом С++, а представляют собой расширения, включаемые большинством реализаций стандартной библиотеки. Пример 6.8 показывает, как использовать
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> // Функция, используемая для