Dictionary/HashTable Object in C++?

Estoy buscando una implementación de HashTable o Diccionario en C++ que tenga una funcionalidad similar a la de C#? ¿El STL contiene un objeto como este y cómo lo usaría?Dictionary/HashTable Object in C++?

Fuente

2010-04-27 cam

realidad, para ser exactamente el mismo que el de .NET diccionario/tabla hash, lo que quiere es hash_map o unordered_map (std::map se implementa como un árbol binario), hash_map es una extensión al SC++ L. La mayoría de los compiladores que conozco vienen con hash_map, y obviamente tienen unordered_map hasta que C++ 0x esté disponible en todos los compiladores, por lo que debería poder usarlo sin problemas.

Fuente

2010-04-27 13:01:54

C++ no tiene ningún contenedor como hash_map ,, y no lo hará en C++ 0x. El nombre del nombre de la tabla hash en C++ es unordered_map - se http://publib.boulder.ibm.com/infocenter/comphelp/v9v111/topic/com.ibm.xlcpp9.aix.doc/standlib/stl_unordered_map.htm –

Sí, actualicé un poco mi respuesta ... –

Ahh, el proceso de estándares de C++. Discutir sobre el nombre de una clase de hashtable mientras Roma arde. – stusmith

Creo que estás buscando map. Ver here para más.

Fuente

2010-04-27 12:59:03

STL tiene std::map

Fuente

2010-04-27 12:59:18 spoulson

mapa es un árbol equilibrado, no un contenedor hash. – Joe

@joe - la pregunta era para una clase de diccionario hashmap * o * en C++ STL, por lo que 'std :: map' encaja perfectamente. – gnud

@gnud: OP también dijo "que tiene una funcionalidad similar a la de C#", que solo corresponde a unordered_map, si se trata de características de rendimiento. – Joe

El STL std::map se puede utilizar para crear un diccionario. std::map generalmente se implementa como un árbol de búsqueda, no como una tabla hash. Eso significa que tanto la búsqueda como la inserción tienen características de rendimiento diferentes a las de C# HashMap - para mapas muy grandes, la búsqueda promedio será más lenta, especialmente si los objetos en el mapa están fragmentados en la memoria.

En el TR1 del nuevo estándar de C++, tiene std::tr1::unordered_map y std::tr1::unordered_multimap, que generalmente se implementarán utilizando una tabla hash. Si su compilador no proporciona esas bibliotecas, puede usar la implementación desde http://www.boost.org/.

Otra alternativa es Google sparse_hash.

Fuente

2010-04-27 13:05:49 gnud

Una búsqueda en un std :: map es ** no ** per se más lenta que en un hash_map. Solo el rendimiento asintótico de un hash_map es O (1) frente a O (log n), pero para valores suficientemente grandes de 1, log n puede ser más rápido. Incluso en la práctica, esto suele ser suficiente, y encontrar una buena función hash es mucho más difícil que implementar un operador correcto. – gimpf

Acabo de volver a leer, usted dijo _ a menudo_, no siempre, mi culpa. Sin embargo, _often_ implica que la mayoría de las veces las personas usan diccionarios con, bueno, más de 1000 entradas, usando funciones hash correctas. Dependiendo del área de trabajo y el nivel de habilidad dentro de una empresa, esto puede ser poco probable. – gimpf

Tal vez 'a menudo será más lento' es un poco duro. Mi punto es principalmente que tienen diferentes características de rendimiento. – gnud

Dictionary/HashTable Object in C++?

Respuesta

Cuestiones relacionadas