gpt4 book ai didi

c++ - 创建 unordered_set 的 unordered_set

转载 作者:塔克拉玛干 更新时间:2023-11-02 23:07:10 29 4
gpt4 key购买 nike

我想创建一个容器来存储唯一的整数集。

我想创建类似的东西

std::unordered_set<std::unordered_set<unsigned int>>

但是 g++ 不允许我这样做并说:

invalid use of incomplete type 'struct std::hash<std::unordered_set<unsigned int> >'

我想要实现的是拥有一组独特的无符号整数。

我该怎么做?

最佳答案

我正在为这个问题添加另一个答案,因为目前还没有人触及关键点。

每个人都在告诉您,您需要为 unordered_set<unsigned> 创建一个哈希函数,这是正确的。您可以通过专门化 std::hash<unordered_set<unsigned>> 来做到这一点,或者您可以创建自己的仿函数并像这样使用它:

unordered_set<unordered_set<unsigned>, my_unordered_set_hash_functor> s;

无论哪种方式都可以。 但是有一个大问题你需要注意:

对于任意两个 unordered_set<unsigned>比较相等(x == y),它们必须散列到相同的值:hash(x) == hash(y) .如果您不遵守此规则,您将遇到运行时错误。还要注意下面两个unordered_set s 比较相等(为清楚起见,此处使用伪代码):

{1, 2, 3} == {3, 2, 1}

因此hash({1, 2, 3}) 必须等于hash({3, 2, 1}) .换句话说,无序容器有一个相等运算符,其中顺序无关紧要。因此,无论您如何构建哈希函数,其结果都必须独立于容器中元素的顺序。

或者,您可以替换 unordered_set 中使用的相等谓词这样它确实尊重秩序:

unordered_set<unordered_set<unsigned>, my_unordered_set_hash_functor,
my_unordered_equal> s;

获得所有这些权利的负担,使得:

unodered_set<set<unsigned>, my_set_hash_functor>

看起来很吸引人。您仍然需要为 set<unsigned> 创建一个散列仿函数,但现在您不必担心为 {1, 2, 3} 获取相同的哈希码。和 {3, 2, 1} .相反,您必须确保这些哈希码不同。

我注意到 Walter's answer给出一个具有正确行为的散列仿函数:它忽略计算散列码的顺序。但随后他的回答(目前)告诉您这不是一个好的解决方案。 :-) 它实际上 是无序容器的一个很好的解决方案。更好的解决方案是返回各个散列的总和,而不是散列元素的总和。

关于c++ - 创建 unordered_set 的 unordered_set,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27757164/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com