c++ - C++：无序容器如何防止重复？

Question

我们以 unordered_set 为例。用于确定两个元素是否相等的默认谓词std::equal_to<T>(t1,t2)是简单的t1==t2。现在假设我已经实现了这种 T 类型，operator==()因此并非所有成员变量都是此比较的一部分，即两个不同的 T 元素 t1,t2 在比较时可以相等。

如果底层哈希表为这些 t1 和 t2 中的每一个计算不同的哈希，它甚至何时执行t1==t2密钥重复检查？如果有更多检查，它如何平均保持恒定时间？

标签： c++hashstlunordered-mapunordered-set

Answer 1

我认为您缺少的关键点是您为无序容器提供了两个仿函数，并且它们必须一起工作。

有哈希函数，它从一个对象计算一个数字。

有一个比较功能，可以比较两个对象的“等价性”。

正如@Eljay 在他的评论中所说，对于比较“等效”（比较函数返回true）的两个对象，哈希函数必须返回相同的值。

如果您的函数不提供此保证，则容器将无法正常工作。

比较好的参考（虽然不权威）

std::unordered_set：满足 UnorderedAssociativeContainer 的要求。
UnorderedAssociativeContainer：由 Key/Hash/Pred 参数化。
有要求：
* 如果两个 Keys 根据 Pred 相等。
* 哈希必须为两个键返回相同的值。