c++ - std::hash vs std::equal_to 没有必需函数的实例化

Question

我仍在学习如何使用标准库容器 std::map 和 std::unordered_map。我最近尝试提供一个哈希函数或比较函数。

有两点我不明白:

std::map<int, int, equal_to<int>> myMap1; // Works
std::map<int, int, hash<int>> myMap2; // Works

std::unordered_map<int, int, equal_to<int>> myMap3; // Doesn't work
std::unordered_map<int, int, hash<int>> myMap4; // Works

为什么我可以为 std::map 提供哈希函数，而不能为 std::unordered_map 提供比较函数？

此外，如果我为比较函数 std::equal_to 使用自定义结构而不重载 == 运算符，我不会出错。为什么会这样？

Answer 1

标准 C++ 库中有一个东西叫做“概念”。概念是一组需求。通过使用 std::unordered_map(或任何遵循某个概念的事物)，您同意您将遵守它规定的要求。

通过使用

std::map<int, int, equal_to<int>> myMap1;
std::map<int, int, hash<int>> myMap2;
std::unordered_map<int, int, equal_to<int>> myMap3;

你违反了 std::map 和 std::unordered_map 的要求 - 编译器不需要检查你的错误，myMap1, myMap2 和 myMap3 肯定不能正常工作。

恰好 Hash要求它返回 std::size_t 类型的值。这很容易检查。

这与 Compare 不同该状态要求不容易检查(例如，std::size_t 可转换为 bool)- 因此，它的使用很可能会在运行时失败。

此外，您似乎对散列函数和比较函数的用途感到困惑 - 它们是不同的。

Hash 返回一个 std::size_t 类型的值，对于 T

类型的任何值 a, b

Hash(a) != Hash(b) implies a != b
and
a == b implies Hash(a) == Hash(b)

就是这样 - 仅此而已。它应该比比较函数更快，因此您可以轻松比较值 - 如果哈希值不同，则值肯定不同，如果哈希值相同，则进行完整比较。