Estructura de datos C++ con lookuptime O (1), como el hashmap de java en stl?

Question

¿Existe tal estructura en la biblioteca estándar de C++? No tengo acceso a nada más, por lo que unordered_map en tr1 no se puede usar (y aumentar, etc.).

Lo que tengo es una gran cantidad de elementos de clase personalizados 100000+ que necesito almacenar, y accedo a ellos muy rápido O (1) en everage. No puedo usar arrays/vectores ya que los elementos se almacenarán aleatoriamente y no sé la posición del elemento.

¿Mi única alternativa es implementar una implementación propia de hashmap con solo la biblioteca estándar de C++ disponible?

Answer 1

El problema es que la búsqueda O (1) no es estándar. No estoy seguro de qué aumento tiene, pero algunas implementaciones de STL (como sgi) tienen hash_map. Eso es lo que necesitas.

Aquí está el documentation.

Sólo probar:

#include <hash_map> 

tener en cuenta si esto funciona, no es portátil ... pero tal vez por ahora eso está bien, y más tarde se pueden encontrar soluciones.

Answer 2

¿Por qué no puedes usar Boost? La biblioteca de colecciones Unordered es "Sólo encabezado", lo que significa que no tiene que recurrir al proceso de compilación e instalador BJam de Boost. Simplemente puede tomar los archivos .hpp y agregarlos a su proyecto.

Answer 3

El STL predeterminado en el estándar actual no tiene O (1) contenedores de búsqueda.

Answer 4

Además de hash_map en algunos STL, busque unordered_map (que es lo que se llamará y/o se llama en la versión TR1 de C++).

Answer 5

Puede usar el contenedor unordered_map. Está en tr1 y estará en el próximo estándar completo. Visual Studio tiene una implementación de la misma en <unordered_map> la documentación y se puede encontrar aquí: http://msdn.microsoft.com/en-us/library/bb982522.aspx

Answer 6

hash_map es parte de la extensión de la SGI a la STL. En GCC, puede usarlo haciendo lo siguiente; No sé acerca de otras implementaciones:

#include <ext/hash_map> 

using __gnu_cxx::hash_map; 

hash_map<int,string> foo; // or whatever 

unordered_map es parte de la TR1. En GCC, puede usarlo haciendo lo siguiente; No sé acerca de otras implementaciones:

#include <tr1/unordered_map> 

using std::tr1::unordered_map; 

unordered_map<int,string> foo; // or whatever 

Answer 7

Si realmente está restringido a std:: y no se puede usar cualquier otra cosa, std::map es su mejor apuesta. Esto solo le da un tiempo de búsqueda logarítmico, no constante, pero en comparación con las matrices/vectores será increíblemente rápido. También creo que para 100000 elementos la búsqueda logarítmica será lo suficientemente rápida y no ganarás mucho usando una tabla hash.

Habiendo dicho eso, es probable que su implementación ya incluya alguna implementación de la tabla hash.Así que si std::map realmente no es lo suficientemente rápido, tratar

#include <tr1/unordered_map> 
std::tr1::unordered_map<int,int> test; 

o

#include <hash_map> 
stdext::hash_map<int,int> test; 

o incluso

#include <boost/tr1/unordered_map.hpp> 
std::tr1::unordered_map<int,int> test;