Хеш-таблица v / s STL map в C ++

Question

Я пытаюсь изучить карты C ++. Просто было интересно по поводу реализации карты STL. Я прочитал это использует двоичное дерево поиска.

1. Есть ли в STL реализация хеш-таблицы?

2. Как именно на карте STL хранятся пары Key Value?

Answer 1

Типичные реализации STL основаны на красно-черных деревьях. C ++ TR1 предоставляет std :: tr1 :: unordered_map, который использует реализацию хеш-таблицы. Boost также предоставляет реализацию хеш-таблицы unordered_map.

C ++ 11 теперь имеет std::unordered_map

Answer 2

1. Некоторые библиотеки реализуют stdext::hash_map, который имеет почти тот же интерфейс, что и std::map, но использует хеш-таблицу вместо двоичного дерева.

2. Узлы двоичного дерева расположены в дереве в соответствии с ключом, и к каждому ключу прикреплено значение, либо в целом в том же узле, либо в виде указателя.

Answer 3

Пары ключ-значение хранятся в std::pair.Это шаблонная структура;элемент с именем first хранит ключ, а элемент с именем second хранит значение. Некоторая информация.