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?

I get an error saying there is no hash function for the array. I guess this is expected and you should implement one. _"error: no match for call to '(const std::hash >) (const std::array&)'"_ GCC 5.1.0 — Richard Critten, Mar 09 '17 at 17:28
Thanks to all people who pointed the lack of a hash function for arrays. I naively thought it's a pretty common thing, for example to store a sparse matrix (not what I'm doing here). — Adrien, Mar 09 '17 at 17:42

Nir Friedman · Answer 1 · 2020-06-10T15:47:37.490

13

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.

edited Jun 10 '20 at 15:47

answered Mar 09 '17 at 17:35

Nir Friedman

17,108
2
44
72

Thanks a lot. Yeah, I don't know much about hashes function and what makes a good hash function, so I guess I'll just move to ordered maps and suffer an additional log complexity time! – Adrien Mar 09 '17 at 17:40
@Adrien Well the biggest hit with ordered maps is probably not the logN time, but the really bad cache coherency. Also, combining hashes well can be done with a simple formula; see the edit to my answer. You should be able to use the code above as is in your project. – Nir Friedman Mar 09 '17 at 19:04
1

The answer no longer compiles. It needs ` std::size_t operator()(const std::array& a) const {` instead. – ivo Welch Jun 09 '20 at 22:59

score 10 · Accepted Answer · edited May 23 '17 at 11:33

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.

score 8 · Answer 3 · answered Mar 09 '17 at 17:31

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.

score 2 · Answer 4 · answered Mar 09 '17 at 17:34

2

Compiled with msvc14 gives the following error:

"The C++ Standard doesn't provide a hash for this type."

I guess this is self-explanatory.

answered Mar 09 '17 at 17:34

Ervin Szilagyi

14,274
2
25
40

Using an unordered_map with arrays as keys

4 Answers4

Linked