提问人:Sourav Kannantha B 提问时间:7/5/2023 更新时间:7/5/2023 访问量:41
如果 Hash 和 KeyEqual 基于不同的子对象,std::unordered_set 如何正确检测相等的元素?
How std::unordered_set correctly detects equal elements if Hash and KeyEqual are based on different subobjects?
问:
请考虑以下代码片段:
struct Foo
{
int a, b;
};
template<>
struct std::hash<Foo>
{
constexpr std::size_t operator()(const Foo& obj) const noexcept
{
return std::hash<int>{}(obj.a);
}
};
template<>
struct std::equal_to<Foo>
{
constexpr bool operator()(const Foo& lhs, const Foo& rhs) const noexpect
{
return std::equal_to<int>{}(lhs.b, rhs.b);
}
}
在这里,我为 和 使用不同的子对象。如果只在当前存储桶中检查唯一性,那么在这种情况下如何正确确保唯一性?Hash
KeyEqual
std::unordered_set
答:
4赞
Sam Varshavchik
7/5/2023
#1
它根本无法确保唯一性。这是完全未定义的行为。
如果将两个对象进行比较为相等,则哈希函数也必须生成相等的哈希值。任何其他结果都是未定义的行为。引用 C++ 标准:
[unord.req]
如果容器的键相等谓词 pred(k1, k2) 为 valid 并在传递这些值时返回 true。如果 k1 和 k2 等效,则容器的哈希函数 应为两者返回相同的值。
评论
Hash
需要为返回的任何对象返回相同的值,因此不存在在不同存储桶中找到相同元素的风险。KeyEqual
true