unordered_set 不支持 `unordered_set<vector<int>>` 或 `unordered_set<pair<int,int>>` 吗？

Question

unordered_set<pair<int,int>> vis;
unordered_set<vector<int>> vis;

两者都是错的，但如果我把它们改成

set<vector<int>> vis;
set<pair<int,int>> vis;

那么他们是正确的。为什么？

int test()
{
        unordered_set<pair<int,int>> vis;
        return 0;
}

编译错误：

unordered_set<pair<int,int>> vis;
unordered_set<vector<int>> vis;

Answer 1

默认情况下，否。对于unordered_set，它需要能够对对象进行哈希处理，并且std::pair没有std::vector默认的哈希实现。有两种典型的方法可以做到这一点；提供您自己的Hash类型，或实现std::hash这些类型的仿函数。让我们看看两者。

首先，这是如何std::unordered_set定义的：

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

我们感兴趣的是第二个模板参数Hash = std::hash<Key>。就目前情况而言，您的程序无法编译，因为 的 专业化std::hash<std::pair<int, int>>不存在。所以我们可以提供它：

template <>
struct std::hash<std::pair<int, int>>
{
    std::size_t operator()(std::pair<int, int> p) {
        return std::hash<int>{}(p.first) ^ std::hash<int>{}(p.second);
    }
};

在这里，我委托std::hash<int>实现哈希，但是您可以按照自己的意愿实现。

或者，您可以提供自己的结构而不是实现std::hash，您只需在定义unordered_set对象时声明它：

struct MyHash
{
    std::size_t operator()(std::pair<int, int> p) {
        return std::hash<int>{}(p.first) ^ std::hash<int>{}(p.second);
    }
};

int main() {
    std::unordered_set<std::pair<int, int>, MyHash> mySet; // Using my own hashing class.
}

为了一点乐趣，在 C++20 中，您可以在未计算的上下文（例如 ）中使用 lambda decltype，因此以下内容也是有效的：

int main() {
    const auto hash = [](std::pair<int, int> p) {
        return std::hash<int>{}(p.first) ^ std::hash<int>{}(p.second);
    }

    std::unordered_set<std::pair<int, int>, decltype(hash)> mySet; 
}