На этом шаге мы приведем общие сведения о хэш-таблицах.
В стандартную библиотеку C++ не вошла такая важная структура данных, как хэш-таблица. Предложения о включении хаш-таблиц в стандарт были, однако хэш-таблицы не входили в исходную версию STL, и комитет решил, что предложение об их включении поступило слишком поздно. В какой-то момент приходится прекратить прием новых предложений и сосредоточиться на освоении того, что есть; иначе работа никогда бы не была закончена.
В сообществе C++ существует несколько распространенных реализаций C++. В библиотеках обычно определяются четыре разновидности хэш-таблиц: hash_set, hash_multiset, hash_map и hash_multimap. По аналогии со стандартными ассоциативными контейнерами multi-версии допускают присутствие дубликатов, а таблицы hash_map и hash_multimap содержат пары "ключ/значение". Бьярн Страуструп подробно рассматривает хэш-таблицы hash_map как пример вспомогательного контейнера STL в разделе 17.6 своей книги "The C++ Programming Language", 3rd Edition. Примеры конкретной реализации хэш-контейнеров можно найти, например, в версии STLport (http://www.stlport.org/). Учтите, что разные реализации могут расходиться в деталях, поскольку хэш-контейнеры еще не стандартизированы.
На следующем шаге мы рассмотрим реализацию ссылочной семантики.
