使用带有数组的unordered_map作为键

Question

我不明白为什么我不能unordered_map用一个array<int,3>键作为键类型:

#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;
}

我得到一个很长的错误,最相关的部分是

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;
     ^

数组是否因为错过了一些要求而没有资格成为密钥？

Answer 1

相关的错误是

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

在unordered_map需要密钥的哈希值,它看起来对过载std::hash做到这一点.您可以namespace std使用合适的哈希函数扩展它.

Answer 2

为什么？

如http://www.cplusplus.com/reference/unordered_map/unordered_map/中所述

在内部,unordered_map中的元素不会根据其键值或映射值按任何特定顺序排序,而是根据其哈希值组织到桶中,以允许通过键值直接快速访问各个元素(使用常量)平均时间复杂度).

现在根据您的问题,我们需要hash一个尚未在标准c ++内部实现的数组.

如何克服它？

因此,如果要将array值映射到值,则必须实现自己的std :: hash http://en.cppreference.com/w/cpp/utility/hash,您可以从C++获得一些帮助,如何将数组插入到哈希集？.

一些解决方法

如果您可以自由使用,boost那么它可以为您提供数组和许多其他类型的散列.它基本上使用的hash_combine方法可以查看http://www.boost.org/doc/libs/1_49_0/boost/functional/hash/hash.hpp.

Answer 3

你必须实现一个哈希.散列表取决于散列键,找到一个存储桶.C++并不神奇地知道如何散列每个类型,在这种特殊情况下,它不知道如何默认散列3个整数的数组.您可以实现这样的简单哈希结构:

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;
    }   
};

然后使用它:

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

编辑:我更改了将来自天真xor的哈希值与boost用于此目的的函数相结合的函数:http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html.这应该足够强大,可以实际使用.