为什么 std::map 接受 std::pair 作为键，但是 std::unordered_map 却不接受？

Question

在考虑复制之前，请了解我的问题基础。

为什么C++的std::map可以接受std::pair作为键类型，但std::unordered_map却不行？

第一种情况可以完美编译：

#include <map>
#include <utility>

using namespace std;

typedef pair<int,int> int_pair;

int main()
{
    map<int_pair,int> m;

    return 0;
}

第二个案例出现了很多编译错误。从这个SO问题和这个SO问题中可以清楚地看到，必须创建一个自定义的哈希函数和等价运算符。

#include <unordered_map>
#include <utility>

using namespace std;

typedef pair<int,int> int_pair;

int main()
{
    unordered_map<int_pair,int> m;

    return 0;
}

这里的问题不是如何为std :: unordered_map编写哈希函数。问题在于，为什么需要哈希函数，而std :: map则不需要？

我知道std :: map是一棵二叉搜索树（BST），但对于非基本类型（int_pair）的键之间的比较究竟是如何进行的？

- Max

---

std::map需要std::less<T>，而std::unordered_map需要std::hash<T>，就是这么简单。至于“为什么”，只需查找如何实现红黑树（map）与哈希表（unordered_map），然后你就会得到答案。 - Cory Kramer

请看答案 https://dev59.com/x2Ij5IYBdhLWcg3wIx7W?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa - Neargye

std::map 可以编译，因为 std::pair 有一个被 std::less 调用的 operator<。请参见：http://en.cppreference.com/w/cpp/utility/pair/operator_cmp - Richard Critten

@Neargye，你好像没有理解我的问题，我是在问它们的区别，而不仅仅是为什么unordered_map无法编译。 - Max

Answer 1

std::map 不会对任何东西进行哈希操作。它使用 std::less 作为默认比较器。只要支持 operator< 的类型，都可以使用它。

std::unordered_map 使用由 std::hash 提供的哈希函数来对其元素进行排序。

碰巧的是，std::pair 提供了 operator<，但没有针对 std::hash 进行特化。

- François Andrieux

---

谢谢你的澄清，本质上归结为 std::pair 提供了 operator<。 - Max

对于那些想知道的人，你可以在这里找到配对运算符。 - Max