No entiendo std::tr1::unordered_map

Question

Necesito un contenedor asociativo que me haga indexar un determinado objeto a través de una cadena, pero que también mantenga el orden de inserción, para poder buscar un objeto específico por su nombre o simplemente iterar sobre él y recuperar objetos en el mismo orden en que inserté. a ellos.

pienso esto híbrido de lista enlazada y mapa hash debería hacer el trabajo, pero antes intenté usar std::tr1::unordered_map Pensando que estaba funcionando de esa manera que describí, pero no fue así.Entonces, ¿alguien podría explicarme el significado y el comportamiento de unordered_map?

---

@wesc:Estoy seguro de que std::map está implementado por STL, mientras que estoy seguro de que std::hash_map NO está en STL (creo que la versión anterior de Visual Studio lo puso en un espacio de nombres llamado stdext).

@cristopher:entonces, si lo hago bien, la diferencia está en la implementación (y por lo tanto en el desempeño), no en la forma en que se comporta externamente.

Answer 1

Impulsar la documentación de contenedores desordenados.

La diferencia está en el método de generación de la búsqueda.

En los contenedores de mapas/conjuntos, operator< se utiliza para generar un árbol ordenado.

En los contenedores desordenados, un operator( key ) => index se utiliza.

Consulte hash para obtener una descripción de cómo funciona.

Answer 2

Has preguntado por la razón canónica por la que se creó Boost::MultiIndex:Orden de inserción de listas con búsqueda rápida por clave. Tutorial de Impulsar MultiIndex:lista de búsqueda rápida

Answer 3

Necesita indexar un contenedor asociativo de dos maneras:

• Orden de insercion
• Comparación de cadenas

Intentar Impulso.MultiIndex o Impulsar.Intrusivo.No lo he usado de esta manera pero creo que es posible.

Answer 4

Lo siento, leí mal tu último comentario.Sí, hash_map no está en STL, el mapa sí.Pero unordered_map y hash_map son iguales por lo que he estado leyendo.

mapa -> log (n) inserción, recuperación, iteración es eficiente (y ordenado por comparación de claves)

hash_map/unordered_map -> inserción y recuperación en tiempo constante, el tiempo de iteración no garantiza que sea eficiente

Ninguno de estos funcionará por sí solo, ya que el mapa ordena las cosas según el contenido de la clave y no según la secuencia de inserción (a menos que su clave contenga información sobre la secuencia de inserción).

Tendrá que hacer lo que describió (lista + hash_map) o crear un tipo de clave que tenga el número de secuencia de inserción más una función de comparación adecuada.

Answer 5

I pensar que un unordered_map y un hash_map son más o menos lo mismo.La diferencia es que STL no tiene oficialmente un hash_map (lo que estás usando probablemente sea algo específico del compilador), por lo que unordered_map es la solución para esa omisión.

unordered_map es solo eso...desordenado.No puede depender de que conserve ningún orden en la iteración.

Answer 6

Estás seguro de que std::hash_map existe en todo ¿Implementaciones STL?SGI STL lo implementa, sin embargo, GNU g++ no lo tiene (está ubicado en el espacio de nombres __gnu_cxx) a partir de 4.3.1 de todos modos.Hasta donde yo sé, hash_map siempre no ha sido estándar y ahora tr1 lo está solucionando.

Answer 7

@wesc:STL tiene std::map...Entonces, ¿cuál es la diferencia con unordered_map?No creo que STL implemente dos veces lo mismo y lo llame de manera diferente.