创建unordered_set的unordered_set

Question

我想创建一个容器,用于存储唯一的整数集.

我想创造类似的东西

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

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

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

我想要实现的是拥有独特的无符号整数集.

我怎样才能做到这一点？

Answer 1

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

每个人都告诉你,你需要创建一个哈希函数unordered_set<unsigned>,这是正确的.你可以通过专业化来实现std::hash<unordered_set<unsigned>>,或者你可以创建自己的仿函数并像这样使用它:

unordered_set<unordered_set<unsigned>, my_unordered_set_hash_functor> s;

无论哪种方式都没关系. 但是,您需要注意一个很大的问题:

对于任何unordered_set<unsigned>比较equal(x == y)的两个,它们必须散列到相同的值: hash(x) == hash(y).如果您未遵循此规则,则会出现运行时错误.另请注意,以下两个unordered_sets比较相等(为清晰起见,此处使用伪代码):

{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的答案给出了一个具有正确行为的哈希函子:它忽略了计算哈希码的顺序.但他的回答(目前)告诉你,这不是一个好的解决方案.:-) 对于无序容器来说,它实际上是一个很好的解决方案.更好的解决方案是返回单个散列的总和,而不是散列元素的总和.

Answer 2

Hash() 创建集合元素哈希值的默认函数不知道如何将整个集合作为元素进行处理。创建一个哈希函数，为每个唯一的集合创建一个唯一的值，然后您就可以开始了。

这是 unordered_set 的构造函数

explicit unordered_set( size_type bucket_count = /*implementation-defined*/, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(), const Allocator& alloc = Allocator() ); http://en.cppreference.com/w/cpp/container/unordered_set/unordered_set

也许对您来说最简单的事情就是为您的数据创建一个哈希函数unordered_set<unsigned int>

unsigned int my_hash(std::unordered_set<unsigned int>& element)
{
  for( e : element )
  {
     some sort of math to create a unique hash for every unique set
  }
}

编辑：如另一个答案所示，我完全忘记了，哈希函数必须位于哈希对象内。至少根据我粘贴在答案中的构造函数。