Elegir entre std:: mapa y std:: mapa desordenado

Además de las respuestas anteriores, también debe tener en cuenta que solo porque unordered_map es velocidad constante (O(1)) no significa que sea más rápido que map (de orden log(N)). La constante puede ser mayor que log(N) especialmente porque N está limitada por 2³² (o 2⁶⁴).

Así que 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 eficiente.

Por ejemplo, en un programa que ejecuté para un blog post Vi que para VS10 std::unordered_map era más lento que std::map (aunque boost::unordered_map era más rápido que ambos).

Note 3rd a 5th bars.

_{Esto se debe a Chandler Carruth de Google en su conferencia CppCon 2014}

std::map es (considerado por muchos como) no útil para el trabajo orientado al rendimiento: Si desea O (1) - acceso amortizado, use una matriz asociativa adecuada (o por falta de una, std::unorderded_map); si desea un acceso secuencial ordenado, use algo basado en un vector.

También, std::map es un árbol equilibrado; y tienes que atravesarlo, o reequilibrarlo, increíblemente a menudo. Estos son asesinos de caché y cache-apocalypse operations respectivamente... así que di NO a std::map.

Podría interesarle esta pregunta sobre implementaciones eficientes de mapas hash.

(PS - std::unordered_map es hostil a la caché porque usa listas enlazadas como cubos.)

Creo que es obvio que usaría el std::map que necesita para iterar entre los elementos del 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 hash (que generalmente es muy poco intuitiva).

Digamos que tienes teclas muy grandes, quizás cadenas grandes. Para crear un valor hash para una cadena grande, debe recorrer toda la cadena de principio a fin. Tomará al menos tiempo lineal hasta 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 devolverse cuando se encuentra el primer desajuste. Esto es típicamente muy temprano para cuerdas 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 se necesita más tiempo para producir un hash (en el caso de std::unordered_map) que para encontrar la ubicación de un elemento mediante 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 en los que este sería el caso, pero creo que serían bastante raros en la práctica.