Ordered map vs unordered map

#1

the ordered map takes o(logn) time to search while unordered takes constant time how?

#2 
Hey @guptashubham210a
The both are implemented in different ways that is why there is such difference.



When it comes to efficiency, there is a huge difference between maps and unordered maps.
We must know the internal working of both to decide which one is to be used.

Difference :

                  | 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

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.

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.
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.