Ahora que std tiene un verdadero mapa hash en unordered_map, por qué (o cuando) ¿Todavía desee utilizar el buen viejo map sobre unordered_map en sistemas donde existe realmente? ¿Hay alguna situación obvia que no pueda ver de inmediato?std :: mapa y std :: unordered_map
Como already mentioned, map permite iterar sobre los elementos de una manera ordenada, pero unordered_map no lo hace. 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 de miembro como lower_bound().
Además, me parece que una diferencia en el peor de los casos búsqueda complejidad.
Para map, es O (lg N)
Para unordered_map, es O (N) [Este puede suceda cuando la función hash no es bueno que conduce a demasiadas colisiones hash .]
Lo mismo es aplicable para el peor de los casos eliminación complejidad.
tiene razón sobre el peor de los casos, pero esta publicación de alguna manera es engañosa, ya que en promedio std :: unordered_map es O (1) para complejidad de búsqueda que es mucho mejor que std :: map –
Es muy importante entender que para algunas aplicaciones, el peor de los casos es crucial para saber y es el factor decisivo. Para algunos sistemas duros en tiempo real, tener un peor caso lineal como la tabla hash no es aceptable. std :: map siempre es O (lg N), que es una propiedad muy agradable de tener. –
Creo que es obvio que usaría 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).
Además de las respuestas anteriores también se debe señalar que el hecho de unordered_map es la velocidad constante (O(1)) no quiere decir que es más rápido que map (del orden log(N)). La constante puede ser mayor que log(N), especialmente porque N está limitado por 2 (o 2).
Por lo tanto, además de las otras respuestas (map mantiene el orden y las funciones hash pueden ser difíciles) puede ser que map sea más eficaz.
Por ejemplo, en un programa que corre por A blog post vi que para VS10 std::unordered_map fue más lento que std::map (aunque boost::unordered_map era más rápido que los dos).
Nota 3º a 5º bares.
¿Cuál es el valor de N en este gráfico? – paulm
@paulm, como dije en la [publicación del blog] (http://lanzkron.wordpress.com/2010/06/02/optimizing-collatz-for-klutzes/) 'N = 10,000,000'. – Motti
El enlace del blog ha seguido el camino del dodo, y los resultados presentados aquí son de poco valor sin ese contexto, ya que el tiempo necesario para comparar las cosas varía mucho con la función hash exacta, el tipo de datos, la longitud y los valores . Esto es particularmente importante con la Biblioteca estándar VC++, ya que las funciones hash son rápidas pero propensas a colisiones: los números pasaron inalterados, solo 10 caracteres espaciados a lo largo de una cadena de cualquier longitud se combinan en el valor hash, los recuentos no son primos. (GNU está en el extremo opuesto del espectro). –
Esto se debe a Chandler Carruth de Google en su CppCon 2014 lecture
std::map es (considerado por muchos como) no es útil para el trabajo orientado al rendimiento: Si desea acceso a la periferia (1) -amortized, utilice una matriz asociativa apropiada (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 estar interesado en this SO question en implementaciones de mapas de hash eficientes.
(PS -. std::unordered_map es caché hostil, ya que utiliza las listas enlazadas como cubos)
Digamos que tiene muy grandes teclas, tal vez las grandes cadenas. 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 discrepancia. 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 generar un hash (en el caso de std::unordered_map) que la búsqueda de la ubicación de un elemento mediante búsqueda binaria (en el caso de std::map), debería ser más rápido realizar una búsqueda 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.
Posible duplicado de [¿Hay alguna ventaja de usar el mapa sobre el \ desordenado no desordenado en el caso de las claves triviales?] (Http://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using- map-over-unordered-map-in-case-of-trivial-keys) –