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
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 questd::map
. No ocurre así constd::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 unstd::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.
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.