创建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;

无论哪种方式都可以。然而，有一个很大的问题需要注意：

对于任何两个比较相等的散列(x == y)，它们必须散列为相同的值：hash(x) == hash(y)。如果你没有遵循这个规则，你将会得到运行时错误。还请注意，以下两个unordered_set比较相等(为清楚起见，此处使用伪代码)：

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

Answer 2

您可以这样做，但是像每种unsorted_set/map元素类型一样，内部的unsorted_set现在需要定义一个散列函数。默认情况下它没有，但您可以自己编写一个。

Answer 3

您需要做的是为std::unordered_set<unsigned int>类型的键定义一个适当的散列(因为对于这个键，operator==是already defined，所以您不需要为std::unordered_set<std::unordered_set<unsigned int>, Hash, EqualKey>提供EqualKey模板参数。

一种简单(尽管效率不高)的选择是对集合中所有元素的总和进行散列。如下所示：

template<typename T>
struct hash_on_sum
: private std::hash<typename T::element_type>
{
  typedef T::element_type count_type;
  typedef std::hash<count_type> base;
  std::size_t operator()(T const&obj) const
  {
    return base::operator()(std::accumulate(obj.begin(),obj.end(),count_type()));
  }
};

typedef std::unordered_set<unsigned int> inner_type;
typedef std::unordered_set<inner_type, hash_on_sum<inner_type>> set_of_unique_sets;

然而，虽然很简单，但这并不好，因为它不能保证满足以下要求。对于两个不相等的不同参数k1和k2，std::hash<Key>()(k1) == std::hash<Key>()(k2)的概率应该非常小，接近1.0/std::numeric_limits<size_t>::max()__。