Unfortunately, this program has undefined behavior. C++11 §17.6.4.2.1: A program may add a template specialization for any standard library template to namespace std only if the declaration depends on a user-defined type and the specialization meets the standard library requirements for the original template and is not explicitly prohibited. hash<pair<int,int>> depends on primitive and standard … Read more
I guess that because std::unordered_map needs to rehash, and therefore copy elements, the types need to be complete, whereas a map, only ever working with pointers to elements, will not exhibit that problem. The solution here is to have an unordered map to a pointer: std::unordered_map<uint32_t, std::shared_ptr<Test> >.
This happens because there is no specialization for std::tr1::hash<Key> with Key = std::pair<int, int>. You must to specialize std::tr1::hash<Key> with Key = std::pair<int, int> before declaring tr1::unordered_map<Pair,bool> h;. This happens because std don’t know how to hash a pair<int, int>. Following there is a example of how to specialize std::tr1::hash<> template <> struct std::tr1::hash<std::pair<int, int> … Read more
They are both forbidden by the standard. For the (ordered) associative containers, the definition of strict weak order (25.4/4) says: If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations … equiv(a, b) && equiv(b, c) implies equiv(a, c) This fails for … Read more
The standard defines a little more about this than most people seem to realize. Specifically, the standard requires (§23.2.5/9): The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The interface includes a bucket_count that runs in constant time. (table 103). It also … Read more
The function object std::hash<> is used. Standard specializations exist for all built-in types, and some other standard library types such as std::string and std::thread. See the link for the full list. For other types to be used in a std::unordered_map, you will have to specialize std::hash<> or create your own function object. The chance of … Read more
| map | unordered_map ——————————————————— element ordering | strict weak | n/a | | common implementation | balanced tree | hash table | or red-black tree| | | search time | log(n) | O(1) if there are no hash collisions | | Up to O(n) if there are hash collisions | | O(n) when hash … Read more
The standard library’s maps are, indeed, inherently slow (std::map especially but std::unoredered_map as well). Google’s Chandler Carruth explains this in his CppCon 2014 talk; in a nutshell: std::unordered_map is cache-unfriendly because it uses linked lists as buckets. This SO question mentioned some efficient hash map implementations – use one of those instead.
This is an unfortunate omission in C++11; Boost has the answer in terms of hash_combine. Feel free to just paste it from them! Here’s how I hash pairs: template <class T> inline void hash_combine(std::size_t & seed, const T & v) { std::hash<T> hasher; seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> … Read more
As already mentioned, map allows to iterate over the elements in a sorted way, but unordered_map does not. This is very important in many situations, for example displaying a collection (e.g. address book). This also manifests in other indirect ways like: (1) Start iterating from the iterator returned by find(), or (2) existence of member … Read more