自定义类的嵌套 unordered_set 的自定义哈希和等价函数

Question

我有一个结构体

MyStruct

，我有一个

unordered_set

，它有自己的哈希函数

MyStructHash

，这样我就可以定义

unordered_set<MyStruct, MyStructHash> struct_set;

。

MyStruct

类似于：

struct MyStruct{
  int a;
  double c;
  std::string b;

  std::string toString()...
}

哈希函数为：

struct MyStructHash{
    std::size_t operator()(const MyStruct& ms) const{
        return std::hash<std::string>()(ms.toString());
    }
};

然后我想定义一个

unordered_set<unordered_set<MyStruct>>

来阻止集合重复。我有一个像这样的哈希函数：

struct MyStructHashSetHash{
  size_t operator()(const std::unordered_set<MyStruct>& set) const{
    size_t hash_val = 0;
    for (const MyStructHash& obj: set){
      hash_val ^= AbstractionHash{}(obj);
    }
    return hash_val;
  }
};

我也有类似的等价函数。然后我尝试将 unordered_set 定义为

unordered_set<unordered_set<MyStruct, MyStructHash>, MyStructHashSetHash, MyStructSetEqual> struct_set_set;

但是，当我这样做时，我收到错误：

/usr/include/c++/11/bits/hashtable_policy.h:1614:23: error: static assertion failed: key equality predicate must be invocable with two arguments of key type
 1614 |         static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

我在网上找不到太多有关此错误的信息。我发现密钥存在问题，并且您必须为您想要 unordered_set 的任何内容定义一个哈希函数。但这就是我认为我已经用

MyStructHashSetHash

所做的事情。

任何帮助都会很棒。谢谢！

Answer 1

当我想要创建一系列嵌套哈希时，我使用 ADL。

namespace myns{


  namespace adl{
    template<class T>
    std::size_t customhash(T const& t){
      return ::std::hash<T>{}(t);
    }
  }
  template<class T>
  std::size_t autohash(T const&t){
    using adl::customhash;
    return customhash(t);
  }
  struct hasher {
    template<class T>
    std::size_t operator()(T const& t) const {
      return autohash(t);
    }
  };
}

这是基本框架。

您可以使用

::myns::hasher

作为哈希对象来代替

std::hash<T>

。

要扩展它，您可以将

customhash

重载添加到类型的命名空间或

myns::adl

。由于您无法向

std

添加重载，因此要支持无序映射的散列，只需执行以下操作：

namespace myns::adl{
  template<class...Ts>
  std::size_t customhash(std::unordered_map<Ts...> cobst& um ){
    // has the unordered map
    // to hash elements simply call customhash(element)
  }
}

要支持散列您的结构，请执行相同的操作 - 重载

customhash

。

现在嵌套在无序映射的无序映射中的递归结构可以工作了。

（如果您需要从外部调用

customhash

，请改为调用

myns::adl

，或者执行使用技巧。）