Suppose I wanted to map data with a string as the key.
What container should I have chosen, map
or unordered_map
? unordered_map
takes up more memory so let's suppose memory isn't an issue, and the concern is speed.
unordered_map
should generally give average complexity of O(1) with the worst case of O(n).
In what cases would it get to O(n)?
When does a map
get more time efficient than unordered_map
? Does it happen when n is small?
Assuming I would use STL unordered_map
with the default haser Vs. map. string is the key.
If I'm going to iterate over the elements rather than access an individual element each time, should I prefer map
?
| map | unordered_map
---------------------------------------------------------
element ordering | strict weak | n/a
| |
common implementation | balanced tree | hash table
| or red-black tree|
| |
search time | log(n) | O(1) if there are no hash collisions
| | Up to O(n) if there are hash collisions
| | O(n) when hash is the same for any key
| |
Insertion time | log(n)+rebalance | Same as search
| |
Deletion time | log(n)+rebalance | Same as search
| |
needs comparators | only operator < | only operator ==
| |
needs hash function | no | yes
| |
common use case | when good hash is| In most other cases.
| not possible or |
| too slow. Or when|
| order is required|