创建unordered_set的unordered_set [英] Creating unordered_set of unordered_set

问题描述

我想创建类似于

的

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

但g ++不会让我这样做，并说：

 使用不完整类型的结构'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的答案给出了一个具有正确行为的散列函子：它忽略了计算散列码的顺序。但他的回答（当前）告诉你，这不是一个好的解决方案。 :-)它实际上是对于无序容器的一个很好的解决方案。一个更好的解决方案是返回单个散列的总和而不是散列元素的总和。

I want to create a container that will store unique sets of integers inside.

I want to create something similar to

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

But g++ does not let me do that and says:

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

What I want to achieve is to have unique sets of unsigned ints.

How can I do that?

解决方案

I'm adding yet another answer to this question as currently no one has touched upon a key point.

Everyone is telling you that you need to create a hash function for unordered_set<unsigned>, and this is correct. You can do so by specializing std::hash<unordered_set<unsigned>>, or you can create your own functor and use it like this:

unordered_set<unordered_set<unsigned>, my_unordered_set_hash_functor> s;

Either way is fine. However there is a big problem you need to watch out for:

For any two unordered_set<unsigned> that compare equal (x == y), they must hash to the same value: hash(x) == hash(y). If you fail to follow this rule, you will get run time errors. Also note that the following two unordered_sets compare equal (using pseudo code here for clarity):

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

Therefore hash({1, 2, 3}) must equal hash({3, 2, 1}). Said differently, the unordered containers have an equality operator where order does not matter. So however you construct your hash function, its result must be independent of the order of the elements in the container.

Alternatively you can replace the equality predicate used in the unordered_set such that it does respect order:

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

The burden of getting all of this right, makes:

unodered_set<set<unsigned>, my_set_hash_functor>

look fairly attractive. You still have to create a hash functor for set<unsigned>, but now you don't have to worry about getting the same hash code for {1, 2, 3} and {3, 2, 1}. Instead you have to make sure these hash codes are different.

I note that Walter's answer gives a hash functor that has the right behavior: it ignores order in computing the hash code. But then his answer (currently) tells you that this is not a good solution. :-) It actually is a good solution for unordered containers. An even better solution would be to return the sum of the individual hashes instead of hashing the sum of the elements.

这篇关于创建unordered_set的unordered_set的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！