mapa vs unordered_map en C++

Requisito previo: std::map , std::unordered_map
Cuando se trata de eficiencia, hay una gran diferencia entre mapas y mapas desordenados. 
Debemos conocer el funcionamiento interno de ambos para decidir cuál usar.

Diferencia : 

                  | map             | unordered_map
---------------------------------------------------------
Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree |  

search time     | log(n)              | O(1) -> Average 
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search
                      
Deletion time   | log(n) + Rebalance  | Same as search

Utilice std::map cuando 

• Necesitas datos ordenados.
• Tendría que imprimir/acceder a los datos (en orden).
• Necesita predecesor/sucesor de elementos.
• Vea las ventajas de BST sobre Hash Table para más casos.

// CPP program to demonstrate use of std::map
#include <bits/stdc++.h>
 
int main()
{
    // Ordered map
    std::map<int, int> order;
 
    // Mapping values to keys
    order[5] = 10;
    order[3] = 5;
    order[20] = 100;
    order[1] = 1;
 
    // Iterating the map and
    // printing ordered values
    for (auto i = order.begin(); i
         != order.end(); i++) {
        std::cout << i->first
                  << " : "
                  << i->second << '\n';
    }
}

1 : 1
3 : 5
5 : 10
20 : 100

\

Utilice std::unordered_map cuando 

• Debe llevar la cuenta de algunos datos (Ejemplo: strings) y no es necesario ordenar.
• Necesita acceso a un solo elemento, es decir, sin recorrido.

// CPP program to demonstrate use of
// std::unordered_map
#include <bits/stdc++.h>
 
int main()
{
    // Unordered map
    std::unordered_map<int, int> order;
 
    // Mapping values to keys
    order[5] = 10;
    order[3] = 5;
    order[20] = 100;
    order[1] = 1;
 
    // Iterating the map and
    // printing unordered values
    for (auto i = order.begin();
         i != order.end(); i++)
    {
        std::cout << i->first
                  << " : "
                  << i->second << '\n';
    }
}

1 : 1
20 : 100
5 : 10
3 : 5

Veamos las diferencias en forma tabular -: