Hash Table v/s Mapa de STL en C++

Question

Estoy intentando aprender mapas de C++. Solo me preguntaba sobre la implementación del mapa STL. Lo leí emplea un árbol de búsqueda binario.

1. ¿Hay una implementación de tabla hash en STL?

2. ¿Cómo exactamente el mapa de STL almacena pares de valores clave?

Answer 1

Las implementaciones de STL típicas se basan en árboles Rojo-Negros. C++ TR1 proporciona std :: tr1 :: unordered_map que utiliza una implementación de tabla hash. Boost también proporciona una implementación de tabla hash unordered_map.

C++ 11 ahora tiene std::unordered_map

Answer 2

1. Algunas bibliotecas implementan stdext::hash_map que tiene casi la misma interfaz que std::map pero utiliza una tabla hash en lugar de un árbol binario.

2. Los nodos del árbol binario están organizados en el árbol de acuerdo con la clave, y cada clave tiene un valor adjunto, ya sea en su totalidad en el mismo nodo o como un puntero.

Answer 3

Los pares clave-valor se almacenan en un std::pair. Es una estructura con plantilla; un elemento llamado first almacena la clave, y un elemento llamado second almacena el valor. Some info.