如果 Hash 和 KeyEqual 基于不同的子对象,std::unordered_set 如何正确检测相等的元素?

How std::unordered_set correctly detects equal elements if Hash and KeyEqual are based on different subobjects?

提问人:Sourav Kannantha B 提问时间:7/5/2023 更新时间:7/5/2023 访问量:41

问:

请考虑以下代码片段:

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);
    }
}

在这里,我为 和 使用不同的子对象。如果只在当前存储桶中检查唯一性,那么在这种情况下如何正确确保唯一性?HashKeyEqualstd::unordered_set

C++ 哈希 相等 无序集

评论

0赞 Yksisarvinen 7/5/2023
Hash需要为返回的任何对象返回相同的值,因此不存在在不同存储桶中找到相同元素的风险。KeyEqualtrue

答:

4赞 Sam Varshavchik 7/5/2023 #1

它根本无法确保唯一性。这是完全未定义的行为。

如果将两个对象进行比较为相等,则哈希函数也必须生成相等的哈希值。任何其他结果都是未定义的行为。引用 C++ 标准:

[unord.req]

如果容器的键相等谓词 pred(k1, k2) 为 valid 并在传递这些值时返回 true。如果 k1 和 k2 等效,则容器的哈希函数 应为两者返回相同的值。