When should I use unordered_map and not std::map

Question

I'm wondering in which case I should use unordered_map instead of std::map.

I have to use unorderd_map each time I don't pay attention of order of element in the map ?

Answer 1

map

1. Usually implemented using red-black tree.
2. Elements are sorted.
3. Relatively small memory usage (doesn't need additional memory for the hash-table).
4. Relatively fast lookup: O(log N).

unordered_map

1. Usually implemented using hash-table.
2. Elements are not sorted.
3. Requires additional memory to keep the hash-table.
4. Fast lookup O(1), but constant time depends on the hash-function which could be relatively slow. Also keep in mind that you could meet with the Birthday problem.

Answer 2

unordered_map is O(1) but quite high constant overhead for lookup, insertion, and deletion. map is O(log(n)), so pick the complexity that best suits your needs. In addition, not all keys can be placed into both kinds of map.

Answer 3

Compare hash table (undorded_map) vs. binary tree (map), remember your CS classes and adjust accordingly.

The hash map usually has O(1) on lookups, the map has O(logN). It can be a real difference if you need many fast lookups.

The map keeps the order of the elements, which is also useful sometimes.

Answer 4

The reason you'd choose one over the other is performance. Otherwise they'd only have created std::map, since it does more for you :)

Use std::map when you need elements to automatically be sorted. Use std::unordered_map other times.

See the SGI STL Complexity Specifications rationale.

Answer 5

map allows to iterate over the elements in a sorted way, but unordered_map does not.
So use the std::map when you need to iterate across items in the map in sorted order.