Using unordered_map with arrays as keys

Question

I do not understand why I cannot have unordered_map with array<int,3> as the key type:

 #include <unordered_map> using namespace std; int main() { array<int,3> key = {0,1,2}; unordered_map< array<int,3> , int > test; test[key] = 2; return 0; } 

I get a long error, the most appropriate part of which is

 main.cpp:11:9: error: no match for 'operator[]' (operand types are std::unordered_map<std::array<int, 3ul>, int>' and 'std::array<int, 3ul>') test[key] = 2; ^ 

Are arrays not matching keys because they miss some requirements?

Answer 1

Why?

As mentioned at http://www.cplusplus.com/reference/unordered_map/unordered_map/

Internally, the elements in unordered_map are not sorted in any particular order with respect to their key or displayed values, but are organized in buckets depending on their hash values, so that quick access to individual elements directly by their key values ​​(with average average time complexity on average )

Now, according to your question, we need a hash array that was not implemented inside standard C ++.

How to deal with this?

So, if you want to map an array to a value, you must implement your own std :: hash http://en.cppreference.com/w/cpp/utility/hash , for which you can get some help from C ++, like insert array into hash set? .

Some work

If you can use boost , then it can provide you with hashing of arrays and many other types. It mainly uses the hash_combine method, for which you can take a look at http://www.boost.org/doc/libs/1_49_0/boost/functional/hash/hash.hpp .

Answer 2

Corresponding error

error: no match for call to '(const std::hash<std::array<int, 3ul> >) (const std::array<int, 3ul>&)'

unordered_map needs a key hash, and it looks for std::hash overload for this. You can extend namespace std with a suitable hash function.

Answer 3

You must implement the hash. Hash tables depending on the hashed key to find a bucket for their input. C ++ does not magically know how to hash each type, and in this particular case, it does not know how to use an array of 3 integers by default. You can implement a simple hash structure as follows:

 struct ArrayHasher { std::size_t operator()(const std::array<int, 3>& a) { std::size_t h = 0; for (auto e : a) { h ^= std::hash<int>{}(e) + 0x9e3779b9 + (h << 6) + (h >> 2); } return h; } }; 

And then use it:

 unordered_map< array<int,3> , int, ArrayHasher > test; 

Edit: I changed the function of combining hashes from naive xor to the function used by boost for this purpose: http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html , This should be enough Durable to actually use.

Answer 4

Compiled with msvc14 gives the following error:

"The C ++ standard does not provide a hash for this type."

I think this is self-evident.