为什么不能将pair用作unordered_set / unordered_map的键？

Question

无论是 std::set<> 还是 std::map<> 都可以使用 std::pair 作为键，但为什么 std::unordered_set<> 和 std::unordered_map<> 不行呢？

例如：

unordered_set<pair<int,int> > S;
S.insert(make_pair(0, 1));

无法编译。

- Rafer

Answer 1

unordered_*容器需要一个哈希函数。默认情况下，它们使用std::hash，但标准库中没有为std::pair<T1,T2>提供专门的std::hash特化版本。另一方面，有序容器依赖于std::less（默认情况下）和std::pair确实提供了operator<。这就是为什么它能够正常工作的原因。

为了使用包含pair的无序容器，您将不得不自己提供一个哈希函数。例如：

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

std::unordered_set<std::pair<int, int>, SimpleHash> S;
S.insert(std::make_pair(0, 1));

- Barry

---

S.emplace(...)会起作用吗？如果不行，你会做出什么改变？ - HeinrichStack

@Barry 可以通过 p.first ^ p.second 获取不同的一对值（如 p_a 和 p_b）相同的值吗？ - olivia

@olivia 当然。它肯定会为 (a,b) 和 (b,a) 给出相同的值。它并不打算成为一个完美的哈希函数，只是一个简单的例子。 - Barry

Answer 2

你需要为pair提供一个哈希函数。

- Xiaotian Pei