c++ - unordered_set - unordered_map example
Elegir entre std:: map y std:: unordered_map (5)
Además de las respuestas anteriores, también debe tener en cuenta que el hecho de que unordered_map sea velocidad constante ( O(1) ) no significa que sea más rápido que el map (del log(N) de órdenes log(N) ). La constante puede ser más grande que log(N) especialmente porque N está limitado por 2 32 (o 2 64 ).
Por lo tanto, además de las otras respuestas (el map mantiene el orden y las funciones hash pueden ser difíciles), es posible que el map sea más eficaz.
Por ejemplo, en un programa que ejecuté para una publicación de blog , vi que para VS10 std::unordered_map unordered_map era más lento que std::map (aunque boost::unordered_map era más rápido que los dos).
Note 3ro a 5to barras.
Ahora que std tiene un mapa hash real en unordered_map , ¿por qué (o cuándo) seguiría utilizando el viejo map en lugar de unordered_map en los sistemas en los que realmente existe? ¿Hay alguna situación obvia que no pueda ver de inmediato?
Como ya se mencionó , el map permite iterar sobre los elementos de una manera ordenada, pero no unordered_map . Esto es muy importante en muchas situaciones, por ejemplo, mostrar una colección (por ejemplo, libreta de direcciones). Esto también se manifiesta en otras formas indirectas como: (1) Comience a iterar desde el iterador devuelto por find() , o (2) existencia de funciones miembro como lower_bound() .
Además, creo que hay alguna diferencia en la peor complejidad de búsqueda de casos .
Para el
map, es O (lg N)Para
unordered_map, es O (N) [Esto puede suceder cuando la función hash no es buena, lo que lleva a demasiadas colisiones hash.]
Lo mismo es aplicable para la peor complejidad de eliminación de casos .
Creo que es obvio que usará el std::map que necesita para recorrer los elementos en el mapa en orden ordenado.
También puede usarlo cuando prefiera escribir un operador de comparación (que es intuitivo) en lugar de una función de control (que generalmente no es muy intuitiva).
Supongamos que tiene teclas muy grandes, tal vez grandes. Para crear un valor hash para una cadena grande, debe recorrer toda la cadena de principio a fin. Tomará al menos tiempo lineal a la longitud de la clave. Sin embargo, cuando solo busca un árbol binario usando el operador > de la clave, cada comparación de cadenas puede regresar cuando se encuentra la primera falta de coincidencia. Esto es típicamente muy temprano para cadenas grandes.
Este razonamiento se puede aplicar a la función find de std::unordered_map y std::map . Si la naturaleza de la clave es tal que lleva más tiempo producir un hash (en el caso de std::unordered_map ) de lo que lleva encontrar la ubicación de un elemento usando la búsqueda binaria (en el caso de std::map ), debería ser más rápido buscar una clave en el std::map . Es bastante fácil pensar en escenarios donde este sería el caso, pero creo que serían bastante raros en la práctica.
Esto se debe a Chandler Carruth de Google en su conferencia CppCon 2014
std::map es (considerado por muchos como tal) no útil para el trabajo orientado al rendimiento: si desea un acceso optimizado O (1), utilice una matriz asociativa adecuada (o por falta de una, std::unorderded_map ); si desea acceso secuencial ordenado, utilice algo basado en un vector.
Además, std::map es un árbol equilibrado; y tiene que atravesarlo, o volver a equilibrarlo, increíblemente a menudo. Estas son las operaciones cache-killer y cache-apocalypse respectivamente ... así que solo diga NO a std::map .
Puede que le interese esta pregunta sobre las implementaciones de mapas de hash eficientes.
(PS - std::unordered_map es cache-antipático porque usa listas enlazadas como cubos.)