C++使用无序键组合进行 map 查找

Question

我想创建一个 unordered_map，其中的键是两个整数的组合。由于在比较时应忽略键值顺序，我想到了使用 unordered_set 作为键，如下所示:

#include <unordered_set>
#include <unordered_map>

using namespace std;

int main ()
{
    unordered_set<int> key_set1 = {21, 42};
    unordered_map<unordered_set<int>, char> map;
    map[key_set1] = 'a';
    ...
    unordered_set<int> key_set2 = {42, 21};
    if(map[key_set2] == map[key_set2])
        success();
}

在编译时，哈希函数似乎有问题:

error: no match for call to ‘(const std::hash<std::unordered_set<int> >) (const std::unordered_set<int>&)’
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>

我该如何解决这个问题？还是有更好的方式/数据结构？

Answer 1

unordered_set 没有预定义的散列函数，因此您必须自己实现；这里有相关的文档 http://en.cppreference.com/w/cpp/utility/hash .

基本上你需要:

// custom specialization of std::hash can be injected in namespace std
namespace std
{
    template<> struct hash<unordered_set<int>>
    {
        std::size_t operator()(unordered_set<int> const& s) const
        {
            std::size_t hash = 0;
            for (auto && i : s) hash ^= std::hash<int>()(i);
            return hash;
        }
    };
}

现在 xor 不是组合哈希函数的推荐方法，但它应该在这种情况下特别有效，因为它既是无序又是集合。因为它是无序的，所以你需要一个可交换的函数。推荐的哈希组合器没有此属性，因为您通常希望“abc”的哈希值不同于“bca”。其次，它是一个集合这一事实确保您不会有任何重复的元素。这可以避免您的哈希函数因 x ^ x == 0 而失败。

我还应该提到，您想在 cpp 文件中定义它，这样您就不会向所有人公开 std 类型上的这个特定哈希实现。