¿Tabla hash en C++?
https://stackoverflow.com/questions/133569
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Normalmente uso el mapa stdlib de C++ siempre que necesito almacenar algunos datos asociados con un tipo específico de valor (un valor clave, p. ej.una cuerda u otro objeto).La implementación del mapa stdlib se basa en árboles que proporcionan un mejor rendimiento (O(log n)) que la matriz estándar o el vector stdlib.
Mi pregunta es: ¿conoce alguna implementación de tabla hash "estándar" de C++ que proporcione un rendimiento aún mejor (O(1))?Algo similar a lo que está disponible en la clase Hashtable desde la API de Java.
Solución
Si está utilizando C++ 11, tiene acceso a la <unordered_map> y <unordered_set> encabezados.Estos brindan clases std::unordered_map y std::unordered_set.
Si estás usando C++03 con TR1, tienes acceso a las clases. std::tr1::unordered_map y std::tr1::unordered_set, usando los mismos encabezados (a menos que estés usando GCC, en cuyo caso los encabezados son <tr1/unordered_map> y <tr1/unordered_set> en cambio).
En todos los casos, existen correspondientes unordered_multimap y unordered_multiset tipos también.
Otros consejos
Si aún no tiene unordered_map o unordered_set, son parte de boost .
Aquí está la documentación para ambos .
Hay un objeto hash_map como muchos han mencionado aquí, pero no es parte de la stl. Es una extensión SGI, así que si estabas buscando algo en el STL, creo que no tienes suerte.
std :: tr1 :: unordered_map, en <unordered_map>
si no tiene tr1, obtenga impulso y use
boost :: unordered_map en <boost/unordered_map.hpp>
Visual Studio tiene la clase stdext::hash_map en el encabezado <hash_map>, y gcc tiene la clase __gnu_cxx::hash_map en el mismo encabezado.
Consulte std :: hash_map de SGI.
Esto está incluido en la distribución STLPort también.
hash_map también es compatible con libstdc ++ .
Dinkumware también admite esto, que significa que muchas implementaciones tendrán un hash_map (creo que incluso Visual C ++ ofrece Dinkumware).
Si tiene las extensiones TR1 disponibles para su compilador, úselas. Si no, boost.org tiene una versión bastante similar, excepto por el espacio de nombres std ::. En ese caso, ingrese una declaración de uso para que pueda cambiar a std :: later.
