This works on gcc 4.5 allowing all c++0x tuples containing standard hashable types to be members of unordered_map and unordered_set without further ado. (I put the code in a header file and just include it.) The function has to live in the std namespace so that it is picked up by argument-dependent name lookup (ADL). … 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
Okay, here you go: std::vector<Key> keys; keys.reserve(map.size()); std::vector<Val> vals; vals.reserve(map.size()); for(auto kv : map) { keys.push_back(kv.first); vals.push_back(kv.second); } Efficiency can probably be improved, but there it is. You’re operating on two containers though, so there’s not really any STL magic that can hide that fact. As Louis said, this will work for any of the … Read more
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
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
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
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
To be able to use std::unordered_map (or one of the other unordered associative containers) with a user-defined key-type, you need to define two things: A hash function; this must be a class that overrides operator() and calculates the hash value given an object of the key-type. One particularly straight-forward way of doing this is to … Read more
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