KeyEqual在std :: unordered_set / std :: unordered_map中的用途

Question

我知道这可能是个模糊的问题，但是我想知道当自定义比较器对std中的哈希容器有用时的现实情况是什么？我知道它在有序容器中很有用，但是对于哈希容器，这似乎有点不可思议。

这样做的原因是，根据比较器相等的元素的哈希值必须相同，并且我认为在大多数情况下，这实际上意味着将查找/插入元素转换为某种通用表示形式（它更快，更容易实现）。

例如：

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

注意1：“对称参数”（std::map启用自定义比较器，因此也std::unordred_应该可自定义）是我考虑的，我认为这没有说服力。

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

Answer 1

在内部，这些元素不是按任何特定顺序排序的，而是按桶进行组织。元素放入哪个存储桶完全取决于其值的哈希值。这允许快速访问各个元素，因为一旦计算了哈希，它就指向元素所放置的确切存储桶。

因此，hash函数定义了元素将要存储在的存储桶中，但是一旦确定了存储桶，为了找到该元素，operator ==将使用。

基本上operator ==用于解决哈希冲突，因此，您需要哈希函数且operator ==保持一致。此外，如果操作员operator ==说两个元素相等，则该集合将不允许重复。

对于所关注的自定义，我认为，不区分大小写的想法set的strings是一个很好的一个：给定两个字符串，你需要提供不区分大小写的哈希函数允许set以确定它的字符串存储在桶然后，您将需要提供一个自定义，KeyEqual以允许该集实际检索元素。

过去，我不得不处理的一个案例是一种允许用户插入字符串，跟踪其插入顺序但避免重复的方法。因此，给定一个像这样的结构：

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

您只想根据来检测重复项value。我unordered_set想到的解决方案之一是使用自定义比较器/哈希函数，该函数仅使用value。这使我可以在允许插入之前检查密钥是否存在。