Using an unordered_map with arrays as keys

Question

I don't understand why I can't have an unordered_map with an 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 pertinent part being

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 eligible to be keys because they miss some requirements?

Answer 1

You have to implement a hash. Hash tables depending on hashing the key, to find a bucket to put them in. C++ doesn't magically know how to hash every type, and in this particular case it doesn't know how to hash an array of 3 integers by default. You can implement a simple hash struct like this:

struct ArrayHasher {
    std::size_t operator()(const std::array<int, 3>& a) const {
        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 for combining hashes from a 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 robust enough to actually use.

Answer 2

Why?

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

Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average).

Now as per your question we need to hash an array which has not been implemented internally in standard c++.

How to get over with it?

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 might get some help from C++ how to insert array into hash set?.

Some work around

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

Answer 3

The relevant error is

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

The unordered_map needs a hash of the key, and it looks for an overload of std::hash to do that. You can extend the namespace std with a suitable hash function.