使用以数组为键的 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;
     ^

数组是否因为缺少某些要求而没有资格成为键？

原文由 Adrien 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

为什么？

如 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 。

原文由 Shridhar R Kulkarni 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

你必须实现一个哈希。哈希表取决于散列键，找到一个存储桶来放入它们。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;

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

原文由 Nir Friedman 发布，翻译遵循 CC BY-SA 4.0 许可协议