Map vs Unordererd_map

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

Implementation  | Self balancing BST  | Hash Table
                |   

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

Use std::map when

• You need ordered data.
• You would have to print/access the data (in sorted order).
• You need predecessor/successor of elements.

// CPP program to demonstrate use of std::map #include   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';     } }

Output :

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

Use std::unordered_map when

• You need to keep count of some data (Example – strings) and no ordering is required.
• You need single element access i.e. no traversal.

// CPP program to demonstrate use of // std::unordered_map #include   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;      //Modify       order[3] = 15;     // Iterating the map and printing unordered values     for (auto i = order.begin(); i != order.end(); i++) {         std::cout << i->first << " : " << i->second << '\n';     } }

Output :

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