为符合条件的类专门设计`std::hash`函数

Question

假设我有一个简单的布尔特征类，MyTrait。也就是说，对于任何类型T，我可以执行MyTrait<T>::value并获取true或false。我想为所有类型T，其中MyTrait<T>::value为true，专门定制std::hash。有没有办法做到这一点？以下是一些失败的尝试：

template <class T, typename std::enable_if<
                                MyTrait<T>::value, int
                            >::type = 0>
struct hash<T> {
...
}

失败的原因：

error: default template argument in a class template partial specialization

我也尝试过将所有的局部特化内容放在#后面，但是这样会出现一个错误信息，指出T处于无法推断的上下文中。

有没有办法做到这一点？至少SO上以前的一个问题表明没有：Specializing std::hash to derived classes。

无论是解决方案还是明确的“否”，后跟简要说明都是一个很好的答案。

- Nir Friedman

---

由于 std::hash 只有一个模板参数，因此您可以进行的唯一类型的部分特化是例如 template<typename T> struct hash<unique_ptr<T>> { ... }。我没有看到任何方法来引起替换失败以禁用特化。 - melak47

然而，您可以为std::unordered_map等提供自定义散列类型，您可以自由地为其配备一个虚拟的模板参数，以供特化使用。 - melak47

@melak47 是的，当然这是一个选项，但易用性排名不太高。 - Nir Friedman

Answer 1

不确定是否合法，但是在C++20的概念下，您可以做类似以下的操作：

template <typename T>
concept MyConcept = MyTrait<T>::value;

namespace std
{

    template <MyConcept T>
    struct hash<T>
    {
        std::size_t operator()(const T& t) const { /*..*/ }
        // ...
    };

}

Demo

- Jarod42

---

你能详细说明一下“不确定是否合法”吗？其中哪一部分是非法的？ - jtbandes

不确定通过概念来专门化std是否合法。 - Jarod42

Answer 2

在std命名空间中提供的模板可以为任何用户定义类型进行特化（1）。

为了为某个类型T特化std::hash，如果一个特征为真，我们可以天真地编写以下代码（注意：不起作用）：

namespace std
{
  template<class T>
    struct hash<std::enable_if_t<IsCustomHashable<T>, T>>
    {
       ...
    };
}

当然，它不起作用，因为

23 : error: 模板参数在部分特化中无法推导：

即使它能够工作，我们也有违反上述第一点的风险。

因为如果有人简单地将我们的IsCustomHashable元函数专门针对一个int返回true呢？

现在，我们将为非用户定义类型专门化std::hash，这是被禁止的。

一种快速且简便的方法是，从帮助器基类派生您的std::hash专业化，并将其延迟到自由函数：

#include <functional>
#include <utility>
#include <unordered_set>


// a base class that defers to a free function.
// the free function can be found via ADL and it can be 
// enabled/disabled with enable_if. it's up to you.

template<class T>
  struct impl_hash
  {
    using argument_type = T;
    using result_type = std::size_t;
    result_type operator()(const argument_type& arg) const {
      return hash_code(arg);
    }
  };


// a test class
struct my_hashable
{
  bool operator==(const my_hashable&) const {
    return true;
  }
};

// implement the free function in the same namespace as the argument
// type's definition
std::size_t hash_code(const my_hashable& mh)
{
  // calculate hash here
  return 0;
}

// now defining a hash specialisation becomes easy
// you could even macroify it
namespace std
{
  template<>
    struct hash<my_hashable>
      : impl_hash<my_hashable>
    {
    };
}

// check it compiles
int main()
{
  std::unordered_set<my_hashable> my_set;
  my_set.emplace();
  return 0;
}

- Richard Hodges

---

有用的信息，谢谢。我大致了解宏方法；但出于通常的原因，我希望避免使用它。 - Nir Friedman

Answer 3

据说计算机科学中的所有问题都可以通过增加一层间接性来解决。

如果您愿意，我们可以实现Sean Parent的运行时多态技术，该技术使用类型擦除和少量多态来委托给一个自由函数。我们可以在被擦除的类型上专门化std::hash。

使用方法如下：

template<> struct MyTrait<Foo> : std::true_type{};
template<> struct MyTrait<Bar> : std::true_type{};
// ...
Foo a;
Bar b;
Bad c; // MyTrait<Bad>::value is false

std::cout << std::hash<my_hashable>{}(my_hashable{a}) << std::endl;
std::cout << std::hash<my_hashable>{}(my_hashable{b}) << std::endl;
// compiler error
//std::cout << std::hash<my_hashable>{}(my_hashable{c}) << std::endl;

演示

关于这种方法的深入讲解，请参考Sean的演讲，以下是代码（附有我的简短解释）。

首先，我们的类型抹除类持有指向任何T的指针，只要存在一个自由函数std::size_t do_hash(const T&)。

class my_hashable
{
  public:
  template <class T>
  my_hashable(T& x) : self_(std::make_shared<impl_hashable<T>>(&x))
  {}

  friend std::size_t do_hash(const my_hashable& x)
  {
      return x.self_->hash_();
  }

  private:
  struct base_hashable
  {
    virtual ~base_hashable() = default;
    virtual std::size_t hash_() const = 0;
  }; // base_hashable

  template <class T>
  struct impl_hashable final : base_hashable
  {
    impl_hashable(T* x) : data_(x) { }
    std::size_t hash_() const override
    {
        return do_hash(*data_); // call to free function
    }

    T* data_;
  }; // impl_hashable

 std::shared_ptr<const base_hashable> self_;
}; 

接下来，我们仅针对类型抹除类的std::hash专门化：

namespace std
{
  template<>
  struct hash<my_hashable>
  {
    std::size_t operator()(const my_hashable& h) const{return do_hash(h);}
  };
}

它是如何工作的：

• my_hashable是一个非模板类，没有虚方法（很好）。
• 它唯一的成员是std::shared_ptr<const base_hashable> self_;，其中base_hashable是一个私有抽象类，要求子类实现一个函数std::size_t _hash() const。
• impl_hashable在这里是工作主力；它是一个模板类，其所有实例都派生自bash_hashable，它们都将它们的std::size_t hash_() const override函数委托给一个接受const T&的自由函数。
• 当我们使用任意类型T构造一个my_hashable时，我们取T的地址并用该指针构造一个impl_hashable<T>。我们将这个impl_hashable隐藏在基类指针base_hashable中。
• 调用do_hash(const my_hashable&)将通过动态分派将调用委托给适当的impl_hashable的hash_函数。
• 我们只需要在my_hashable上专门化std::hash，并将其委托给my_hashable的do_hash友元函数。

我的方法与Sean的略有不同，因为类型擦除对象不拥有我们给它的 T，而是采用非拥有指针指向预先存在的对象。这样将允许您仅在需要时构造（轻量级）my_hashable。

现在我们可以定义我们的自由函数，它只适用于 MyTrait<T>::value 为 true 的类型。

template<class T>
std::size_t do_hash(const T& t)
{
    static_assert(MyTrait<T>::value, "Can only call do_hash for types for which MyTrait is true");
    return std::hash<typename T::data_t>{}(t.data);
}

然后，正如我在本文开头所示，我们可以定义我们的类并决定哪些类满足该特性。在这里，T 取决于 Foo 和 Bar 类型（而不是 my_hashable，因为我们已经委托给 impl_hashable，它会恢复我们在构造 my_hashable 实例时传递的类型）。

- AndyG

---

我看到可以通过包装T来创建std::hash<my_hashable>，但是似乎仍然没有std::hash<T>。这种方法是否允许将特化MyTrait为true的类型直接用于诸如std::unordered_set之类的东西中，而无需在集合的模板参数中指定非默认哈希类型？ - jtbandes

@jtbandes：很遗憾，我们无法这样做。我们可以创建一个拥有底层T的my_hashable版本，然后我们可以创建一个unordered_set<my_hashable>。我意识到额外的间接层并不理想，因此在我的帖子顶部进行了限定。 - AndyG

我熟悉SP多态性，但这并没有回答问题，尽管我很感激你的努力。这不是专门针对T符合某个特征，而是针对其他类型。这很关键，因为这个练习的目标，实际上也是我能想到的唯一专门化std::hash的原因，就是让std::unordered_map/set<K, (V)>“正常工作”。如果我将键类型设置为my_hashable，那么会有很多不良后果，所以我只能使用你的解决方案。 - Nir Friedman

@NirFriedman：可以的。我同意你的观点。尽管标准并没有真正允许或禁止这种做法，但我倾向于认为Jarod42的答案是正确的。根据特质的不同，对于标准库中的某个类型来说，可能会是正确的，但这可能是非法的。否则，我们只能使用宏或者类型擦除。 - AndyG

@AndyG 是的，我想我需要确保这个特质永远不会对我无法控制的类型求值为真。在这个特定的例子中，这个特质是从我的某个类型继承而来的，所以我认为在这方面是安全的。 - Nir Friedman