unordered-map

How to specialize std::hash::operator() for user-defined type in unordered containers?

You are expressly allowed and encouraged to add specializations to namespace std*. The correct (and basically only) way to add a hash function is this: namespace std { template <> struct hash<Foo> { size_t operator()(const Foo & x) const { /* your code here, e.g. “return hash<int>()(x.value);” */ } }; } (Other popular specializations that … Read more

How std::unordered_map is implemented

The Standard effectively mandates that implementations of std::unordered_set and std::unordered_map – and their “multi” brethren – use open hashing aka separate chaining, which means an array of buckets, each of which holds the head of a linked list†. That requirement is subtle: it is a consequence of: the default max_load_factor() being 1.0 (which means the … Read more

Why can’t I compile an unordered_map with a pair as key?

You need to provide a suitable hash function for your key type. A simple example: #include <unordered_map> #include <functional> #include <string> #include <utility> // Only for pairs of std::hash-able types for simplicity. // You can of course template this struct to allow other hash functions struct pair_hash { template <class T1, class T2> std::size_t operator … Read more

Is there any advantage of using map over unordered_map in case of trivial keys?

Don’t forget that map keeps its elements ordered. If you can’t give that up, obviously you can’t use unordered_map. Something else to keep in mind is that unordered_map generally uses more memory. map just has a few house-keeping pointers, and memory for each object. Contrarily, unordered_map has a big array (these can get quite big … Read more