1 | map | unordered_map
2---------------------------------------------------------
3Ordering | increasing order | no ordering
4 | (by default) |
5
6Implementation | Self balancing BST | Hash Table
7 | like Red-Black Tree |
8
9search time | log(n) | O(1) -> Average
10 | | O(n) -> Worst Case
11
12Insertion time | log(n) + Rebalance | Same as search
13
14Deletion time | log(n) + Rebalance | Same as search
15
16
17::-> Use std::map when
181. You need ordered data.
192. You would have to print/access the data (in sorted order).
203. You need predecessor/successor of elements.
21
22::-> Use std::unordered_map when
231. You need to keep count of some data (Example – strings) and no ordering is required.
242. You need single element access i.e. no traversal.