1

Cuál es la diferencia entre estos los contenedores STL std::map y std::unorderedmap, además a la hora de buscar un elemento cual es más eficiente.

2 respuestas 2

2

Ambos con contenedores asociativos; asocian un valor, T, con una determinada palabra clave, Key. En otros lenguajes son llamados diccionarios o mapas.

std::map< Key, T, Compare, Allocator >

Los elementos son almacenados siguiendo un determinado orden: el determinado por el parámetro Compare de la plantilla. Se recorren en ese mismo orden.

Las operaciones de búsqueda, eliminación e inserción tienen complejidad logarítmica O(log n).

Es decir, el tiempo que tardan en realizar esas operaciones depende de la cantidad de elementos en elmap. Cuantos mas elementos, mas lento.

std::unordered_map< Key, T, Hash, KeyEqual, Allocator >

Los elementos son almacenados sin un orden en particular, usando para ello una función hash o de firma (wikipedia). Es casi imposible recorrerlos en ningún tipo de orden, siendo este aleatorio y dependiente de la función hash utilizada.

Las operaciones de búsqueda, inserción y eliminación tienen, de media, complejidad constante O(1).

Es decir, el tiempo que tardan en realizar las operaciones es independiente del número de elementos; tardan aproximadamente lo mismo exista 1, 10, o 10000 elementos.

Aquí, el estandar si indica que se implementan mediante buckets (perdón por el término, no encontré palabra adecuada en Español. Wikipedia en inglés ).

Son esos buckets los responsables de esa aproximación en los tiempos.

Observaciones

  • Ten presente que estas indicaciones son requerimientos minimos. Es decir, puedes encontrar implementaciones de std::unordered_map que sean mas rápidas de lo que indica el estandar, pudiendo llegar a ser igual de rápidas que std::map. No ocurre así con std::map. No es que el estardar lo impida, es que no es posible hacerlo más rapido de O(1).

  • Ten presente también que se indica complejidad de la operación, NO tiempos. Puede ser, aunque improbable, que un std::map con pocos elementos sea más rápido que un std::unordered_map.

  • Jugando con los argumentos adicionales, se puede personalizar el comportamiento. Por ejemplo, en el caso de std::unordered_map, es posible recorrerlos en un orden concreto, aunque es complicado. Para ello, se puede utilizar una función hash personalizada.

0

Para no repetir lo comentado por trauma...

std::map implementa un árbol de nodos el cual se encuentra ordenado. La profundidad de las diferentes ramas tiende a ser la misma lo que obliga a recolocar nodos en muchas inserciones. Debido a esto este mapa proporciona unos tiempos de acceso muy buenos pero penaliza enormemente la inserción de nuevos valores. Esta recomendado para mapas muy estables con un gran número de consultas.

std::unordered_map utiliza el concepto de hash para agrupar las diferentes claves. Este mecanismo permite insertar elementos de una forma bastante rápida a cambio de penalizar sensiblemente las búsquedas. Mapas con vida corta o que reciben inserciones con asiduidad suelen tener mejor tiempo de respuesta con este tipo de mapa.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.