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

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&>()))>

我该如何解决这个问题？还是有更好的way/data结构？

Answer 1

问题是 unordered_set 不是为用作无序容器中的键而构建的。

如果您总是恰好使用两个整数，那么使用一对整数作为键会更经济，并添加一个函数从两个整数中生成正确排序的对：

pair<int,int> unordered_key(int a, int b) {
    return a<b?make_pair(a, b):make_pair(b, a);
}

Answer 2

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 类型上的这个特定哈希实现。

Answer 3

如前所述，要将 std::pair 直接用作键，您需要为其显式定义哈希函数。如果你想避免这种情况，你可以将 2 个无符号整数按位组合成 1:

uint64_t makeKey(uint32_t a, uint32_t b)
{
    return a < b ? (static_cast<uint64_t>(a) << 32) + b : (static_cast<uint64_t>(b) << 32) + a;
}

int main ()
{
    auto key_set1 = makeKey(21, 42);

    unordered_map<uint64_t, char> map;
    map[key_set1] = 'a';
    //...

    auto key_set2 = makeKey(42, 21);
    if(map[key_set1] == map[key_set2])
        std::cout << "success" << std::endl;
}

Answer 4

由于顺序在这里并不重要，您可以使用 std::pair 和自定义工厂来强制两个整数的顺序：

std::pair<int, int> make_my_pair(int x, int y) {
    return std::make_pair(std::min(x, y), std::max(x, y));
}

当然，这只有在您始终如一地使用 make_my_pair 时才有效。

或者，您可以定义自己的密钥 class，它具有类似的属性。

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

C++ using an unordered key combination for a map lookup

c++

unordered-map