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 ?

Solution 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.

Solution 2

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.

Comments

[Zakaria Jaiathe]

What does the hash table use the memory for? Isn't it just a hash function? So for my understanding: memory of hash map = memory of map = O(n)

[Kirill V. Lyadvinsky]

@ZakariaJaiathe consider you have a hash function that has an int16 as a return type. So you need a table with 2^16 elements in it, because you need to map the function output to the elements. Independently of how many real elements you have in your container you need a memory for the placeholders. There's a trick with using a so called pre-hash function to reduce the field of the mapped values, but it requires the more characters to describe it in details then a comment allows

[Zakaria Jaiathe]

Thanks. Maybe you can write it on multiple comments or if you have some useful link.

[wildturtle]

I don't understand how lookup can be O(1).. Theta(1) makes more sense where the number of buckets is sufficiently close to N, but the worst case complexity for a lookup should always be O(N/c) where c (constant) is the number of buckets which simplifies to O(N).