c++ - KeyEqual 在 std::unordered_set/std::unordered_map 中的用处

Question

我知道这可能是一个模糊的问题，但我想知道当自定义比较器对 std 中的哈希容器有用时，现实世界中有哪些情况。我知道它在有序容器中很有用，但对于散列容器来说似乎有点奇怪。

这样做的原因是，根据比较器，相等的元素的散列值需要相同，而且我相信在大多数情况下，这实际上意味着将查找/插入元素转换为一些通用表示(它更快更容易实行)。

例如:

• 一组不区分大小写的字符串:如果您想正确散列，则无论如何都需要将整个字符串大写/小写。
• 一组分数(其中 2/3 == 42/63):您需要将 42/63 转换为 2/3，然后对其进行哈希处理...

所以我想知道是否有人可以提供一些关于自定义 std::unordered_ 有用性的真实示例模板参数，以便我可以在以后编写的代码中识别这些模式。

注 1:“对称参数”(std::map 允许自定义比较器，因此 std::unordred_ 也应该是可自定义的)是我考虑过的，但我认为它没有说服力。

注意 2:为了简洁起见，我在帖子中混合了两种比较器( < 和 == )，我知道 std::map使用 <和 std::unordered_map使用 == .

Answer 1

根据 https://en.cppreference.com/w/cpp/container/unordered_set

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

所以哈希函数定义了你的元素最终将进入的桶，但是一旦决定了桶，为了找到元素，将使用运算符==。

基本上 operator == 用于解决散列冲突，因此，您需要您的散列函数和 operator == 保持一致。此外，如果您的运算符 operator == 表示两个元素相等，则该集合将不允许重复。

关于自定义，我认为 string 的不区分大小写的 set 的想法是一个很好的想法:给定两个字符串，您需要提供一个大小写-insensitive hash-function 允许 set 确定它必须存储字符串的桶。然后你需要提供一个自定义的 KeyEqual 来允许 set 实际上检索元素。

在过去，我必须处理的一个案例是一种允许用户插入字符串的方法，跟踪他们的插入顺序但避免重复。所以，给定一个像这样的结构:

struct keyword{
  std::string value;
  int sequenceCounter;
};

您只想根据值 检测重复项。我想出的解决方案之一是带有自定义比较器/哈希函数的 unordered_set，它仅使用 value。这使我能够在允许插入之前检查 key 是否存在。