Does it make sense to use std::unordered_map<int, int> instead of std::map<int, int>?

Question

Should std::unordered_map<int, int> be faster than std::map`? I don't care about order, just fast lookup, so I thought I should use a hashtable. But then I thought maybe it'll try to additionally hash my keys or something like that (which I don't need)?

And a related question: I need to retrieve an int value by int key. Should I use unordered_map<int, int> or unordered_set<pair<int, int> > (in which case I'd need to implement hash function for my pair properly)?

Answer 1

The difference between a map<T,K> and an unordered_map<T,K> is that the first implementation relies on a tree while the second relies on an hashmap.

This means that complexities for basic operations (get and set) are logarithmic for a map and constant for an unordered_map.

There are other aspects in any case: an unordered_map may need a rehash when its load factor is reached (and this requires time and can be unpredictable) while a normal map doesn't involve such problems. In addition the unordered_map implementation could use separated chaining with buckets so if it happens to have many collisions, complexity becomes constant+linear for retrieval of the key.

I'd suggest you to benchmark both structures with some data with a pattern similar to the one you need, that will make your choice.

You don't need to define your own hash<int> for the unordered_map as it's already implemented.