Does it make sense to use std::unordered_map<int, int> instead of std::map<int, int>?
c++, c++11, hashmap, stl, unordered-map
Solution
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.
Problem
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)?