Я пытаюсь изучить карты С++. Было просто интересно о реализации карты STL. Я читал, что использует двоичное дерево поиска.
Есть ли реализация хэш-таблицы в STL?
Как именно карта STL хранит пары ключевых значений?
Типичные реализации STL основаны на деревьях Red-Black. С++ TR1 предоставляет std:: tr1:: unordered_map, который использует реализацию хеш-таблицы. Boost также предоставляет реализацию хэш-таблицы unordered_map.
С++ 11 теперь имеет std::unordered_map
В некоторых библиотеках реализована stdext::hash_map, которая имеет почти тот же интерфейс, что и std::map, но использует хеш-таблицу вместо двоичного дерева.
Узлы двоичного дерева расположены в дереве в соответствии с ключом, и каждый ключ имеет значение, прикрепленное либо в целом в том же node, либо как указатель.
Пара ключей-значений хранится в std::pair. Его шаблонная структура; элемент с именем first хранит ключ, а элемент с именем second сохраняет значение. Некоторая информация.