使用带有数组作为键的 unordered_map

Question

我不明白为什么我不能使用 array<int,3> 作为键类型的 unordered_map：

#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/

所述

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).

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

如何克服它？

因此，如果您想将 array 映射到一个值，您必须实现自己的 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?.

一些解决方法

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

Answer 3

使用 msvc14 编译出现以下错误：

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

我想这是不言自明的。

Answer 4

您必须实现哈希。哈希表取决于对键进行哈希处理，找到一个桶来放入它们。C++ 并不知道如何对每种类型进行哈希处理，在这种特殊情况下，默认情况下它不知道如何对 3 个整数的数组进行哈希处理。您可以像这样实现一个简单的哈希结构：

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

然后使用它：

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

编辑：我将用于组合哈希的函数从简单的异或更改为 boost 为此目的使用的函数：http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html。这应该足够强大，可以实际使用。

使用带有数组作为键的 unordered_map

Using an unordered_map with arrays as keys

c++

stl

unordered-map

c++11