使 std 的 data-structure 默认使用我现有的 non-static 散列函数 "hashCode()"

Question

我有一个 moderate-size 代码库 (>200 .cpp)，它使用函数 hashCode() 到 return 哈希值：-

class B01{  //a class
    //..... complex thing ....
    public: size_t hashCode(){ /* hash algorithm #H01 */}  
};
class B02{  //just another unrelated class
    //..... complex thing ....
    public: size_t hashCode(){/* #H02 */}  //This is the same name as above
};

我在不同的地方使用过它，例如按照我的习惯 data-structure。效果很好。

现在，我想让std::数据结构识别的散列算法：-

这是我应该做的:-（修改自 cppreference，我将调用此代码 #D）。

//#D
namespace std {
    template<> struct hash<B01> {
        std::size_t operator()(const B01& b) const {
            /* hash algorithm #H01 */
        }
    };
}

如果我在每个 class（B01、B02、...）中插入块 #D（通过适当的实现），我可以调用：-

std::unordered_set<B01> b01s;
std::unordered_set<B02> b02s;

没有传递第二个模板参数，
我的哈希算法 (#H01) 将被调用。（按默认值）

问题

让它识别我所有的 B01::hashCode, B02::hashCode, ...,
我是否必须将块 #D 插入所有 200+ Bxx.h？

我可以只添加一个单个块 #D （在顶部 header 吗？）
然后，re-route std::anyDataStructure 尽可能调用 hashCode()?

//pseudo code
namespace std{
    template<> struct hash<X>   {
        std::size_t operator()(const X& x) const { // std::enable_if??
            if(X has hashCode()){    //e.g. T=B01 or B02       
                make this template highest priority   //how?
                return hashCode();
            }else{                   //e.g. T=std::string
                don't match this template;  
            }
        }
    };
}

对我来说这听起来像是一个 SFINAE 问题。

旁注： 在 SO 中没有询问如何实现这一点。

编辑（我为什么不直接重构它？；2017 年 2 月 3 日）

我不知道强力重构是否是一条正确的道路。我想可能有更好的方法。
hashCode()是我家。我在情感上依恋它。
我希望我的代码尽可能简洁明了。 std:: 块脏了。
这可能只是我的好奇心。如果我固执不去重构我的代码，C++能走多远？

Answer 1

不一定非要这样，你也可以有一个函子：

struct MyHash {
    template <class T>
    auto hashCode(const T & t, int) const -> decltype(t.hashCode()) {
        return t.hashCode();
    }
    template <class T>
    auto hashCode(const T & t, long) const -> decltype(std::hash<T>{}(t)) {
        return std::hash<T>{}(t);
    }
    
    template <class T>
    auto operator()(const T & t) const -> decltype(hashCode(t,42)) {
        return hashCode(t,42);
    }
};

并且有一个 std::unordered_set 的别名，MyHash 作为散列类型：

template <class Key>
using my_unordered_set = std::unordered_set<Key, MyHash>;

或更完整，如果您还希望能够提供 Equal 仿函数和分配器：

template<
    class Key,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
>
using my_unordered_set = std::unordered_set<Key, MyHash, KeyEqual, Allocator>;

然后像使用 std::unordered_set:

一样使用它（与您的任何 Bxx）

int main() {
    my_unordered_set<B01> b01s;
    my_unordered_set<B02> b02s;

    // or lonely with your type:
    B01 b01{/*...*/};
    std::cout << MyHash{}(b01) << std::endl;

    // or any other:
    std::string str{"Hello World!"};
    std::cout << MyHash{}(str) << std::endl;
}

概念

如果您可以使用 concepts，它们可以让您按照自己的方式专攻 std::hash class：

template <class T>
concept HashCodeConcept = requires(T const & t)
{
    {t.hashCode()} -> std::same_as<std::size_t>;
};

namespace std {
    template <HashCodeConcept T>
    struct hash<T> {
        std::size_t operator()(const T& t) const {
            return  t.hashCode();
        }
    };
}

Answer 2

我想出了一些似乎部分有效的方法。这是一种解决方法，允许您在实现 hashCode 的类型上使用 std::hash。看一看：

   //some class that implements hashCode
struct test
{
    std::size_t hashCode() const
    {
        return 0;//insert your has routine
    }
};
//helper class
struct hashable
{
    hashable():value(0){}
    template<typename T>
    hashable(const T& t):value(t.hashCode())
    {}
    template<typename T>
    std::size_t operator()(const T& t) const
    {
        return t.hashCode();
    }

    std::size_t value;
};


//hash specialization of hashable
namespace std {
    template<>
    struct hash<hashable>
    {
        typedef hashable argument_type;
        typedef std::size_t result_type;
        result_type operator()(const argument_type& b) const {
            return b.value;
        }
    };
}
//helper alias so you dont have to specify the hash each time.
template<typename T, typename hash = hashable>
using unordered_set = std::unordered_set<T,hash>;

int main(int argc, char** argv)
{
    unordered_set<test> s;
    test t;
    std::cout<<std::hash<hashable>{}(t)<<std::endl;
}

该代码利用 hashable 的模板构造函数和模板运算符从任何实现 hashCode 的 class 中检索散列。 std::hash 特化正在寻找 hashable 的实例，但模板构造函数允许从具有 hasCode 的 class 构造实例。

这里唯一的问题是您必须编写 unordered_set 而不是 std::unordered_set 才能使用它，并且您必须确保 std::unordered_set 没有进入范围反正。因此，您的源代码中不能包含 using namespace std 或 using std::unordered_set 之类的内容。但除了使用中的一些陷阱外，这可能对您有用。

当然，这只是一个 band-aid 真正的问题......不想经历为每个类型正确专业化 std::hash 的痛苦。 (我不怪你)

我还要注意，使用此代码 替换是错误的...如果您更喜欢 SFINAE，则需要修改。

编辑：

尝试后运行:

unordered_set<test> s;
test t;
s.insert(t);

我注意到有一些编译器错误。

我已将 test class 更新为 equality comparable，方法是添加：

bool operator==(const test& other) const
{
    return hashCode() == other.hashCode();
}

到 test 现在使得：

//some class that implements hashCode
struct test
{
    std::size_t hashCode() const
    {
        return 0;//insert your has routine
    }
    bool operator==(const test& other) const
    {
        return hashCode() == other.hashCode();
    }
};

Answer 3

您正在寻找的基于 SFINAE 的方法需要 std::hash 的部分特化。如果您的类 Bxx 是模板（如果它们是从 CRTP 基础派生的，则可以这样做）。例如（注释在编辑中充实）

#include <type_traits>
#include <unordered_set>
#include <iostream>

template<typename T = void>
struct B {
  B(int i) : x(i) {}
  std::size_t hashCode() const
  {
    std::cout<<"B::hashCode(): return "<<x<<std::endl;
    return x;
  }
  bool operator==(B const&b) const
  { return x==b.x; }
private:
  int x;
};

template<typename T,
         typename = decltype(std::declval<T>().hashCode())> 
using enable_if_has_hashCode = T;

namespace std {
  template<template<typename...> class T, typename... As> 
  struct hash<enable_if_has_hashCode<T<As...>>> 
  {
    std::size_t operator()(const T<As...>& x) const
    { return x.hashCode(); }
  };
  // the following would not work, as its not a partial specialisation
  //    (some compilers allow it, but clang correctly rejects it)
  // tempate<typename T>
  // struct hash<enable_if_hashCode<T>>
  // { /* ... */ }; 
}

int main()
{
  using B00 = B<void>;
  B00 b(42);
  std::unordered_set<B00> set;
  set.insert(b);
}

生成（在 MacOS 上使用 clang++）

B::hashvalue(): return 42

另请参阅 this related answer 我的一个类似问题。

但是，concepts 是解决此类问题的未来方式。

Answer 4

在创造条件将 std 容器模板的哈希参数默认为 classes 组的成员方法时，应避免引入新问题。

冗余
可移植性问题
奥术构造体

classic 面向对象的方法可能需要对 200 多个 classes 进行模式化编辑，以确保它们提供 std::hash 容器使用的基础知识。下面给出了组转换的一些选项，以提供两种需要的方法。

A public hashCode() 是在具体的 class 中定义的，它对于那个 class 是唯一的，或者如果它遵循 class 中通用的模式则通过继承来定义es.
定义了一个public运算符==()。

两个模板

这两个模板将删除冗余并简化声明。

template <typename T>
    struct HashStruct {
        std::size_t operator()(const T & t) const {
            return t.hashCode();
        } };
template <class T>
    using SetOfB = std::unordered_set<T, HashStruct<T>>;

节省积分时间

一个例子super-class:

class AbstractB {
    ...
    virtual std::size_t hashCode() const {
        return std::hash<std::string>{}(ms1)
                ^ std::hash<std::string>{}(ms2);
    } }

以下 sed 表达式可能会节省转换时间，假设代码使用 { inline.类似的表达式适用于 Boost 或使用脚本语言，如 Python.

"s/^([ \t]*class +B[a-zA-Z0-9]+ *)(:?)(.*)$"
        + "/  : public AbstractB,  [{]/"
        + "; s/ {2,}/ /g"
        + "; s/: ?:/:/g"

基于 AST 的工具会更可靠。 This explains how to use clang capabilities for code transformation. There are new additions such as this Python controller 的 C++ 代码转换。

讨论

散列算法可以驻留的位置有多种选择。

std 容器声明的抽象方法class
一个具体的方法class（比如例子中的#H01）
结构模板（通常适得其反且不透明）
默认std::hash

这是一个编译单元，它提供了 classic 的清晰演示，说明了如何实现所需的默认设置和上面列出的其他三个目标，同时在为任何给定的哈希算法定义位置方面提供了灵活性class。根据具体情况，可以删除各种功能。

#include <string>
#include <functional>
#include <unordered_set>

template <typename T>
    struct HashStructForPtrs {
        std::size_t operator()(const T tp) const {
            return tp->hashCode(); } };
template <class T>
    using SetOfBPtrs = std::unordered_set<T, HashStructForPtrs<T>>;

template <typename T>
    struct HashStruct {
        std::size_t operator()(const T & t) const {
            return t.hashCode(); } };
template <class T>
    using SetOfB = std::unordered_set<T, HashStruct<T>>;

class AbstractB {
    protected:
        std::string ms;
    public:
        virtual std::size_t hashCode() const {
            return std::hash<std::string>{}(ms); }
        // other option: virtual std::size_t hashCode() const = 0;
        bool operator==(const AbstractB & b) const {
            return ms == b.ms; } };

class B01 : public AbstractB {
    public:
        std::size_t hashCode() const {
            return std::hash<std::string>{}(ms) ^ 1; } };

class B02 : public AbstractB {
    public:
        std::size_t hashCode() const {
            return std::hash<std::string>{}(ms) ^ 2; } };

int main(int iArgs, char * args[]) {

    SetOfBPtrs<AbstractB *> setOfBPointers;
    setOfBPointers.insert(new B01());
    setOfBPointers.insert(new B02());

    SetOfB<B01> setOfB01;
    setOfB01.insert(B01());

    SetOfB<B02> setOfB02;
    setOfB02.insert(B02());

    return 0; };

Answer 5

方案一

如果您可以使用虚拟参数制作 classes B01、B02、... class 模板，您可以简单地使用 std::hash 对于采用虚拟模板参数的模板模板：

#include <iostream>
#include <unordered_set>

struct Dummy {};

template <class = Dummy>
class B01{ 
    public: size_t hashCode() const { return 0; }  
};
template <class = Dummy>
class B02{ 
    public: size_t hashCode() const { return 0; } 
};

namespace std{
    template<template <class> class TT> struct hash<TT<Dummy>>   {
        std::size_t operator()(const TT<Dummy>& x) const { 
            return x.hashCode();
        }
    };
}

int main() {
    std::unordered_set<B01<>> us;
    (void)us;
}

[live demo]

方案二（包含error/don不使用）

但我相信你想要的看起来更像这样：

#include <iostream>
#include <unordered_set>

class B01{ 
    public: size_t hashCode() const { return 0; }  
};

class B02{ 
    public: size_t hashCode() const { return 0; } 
};

template <class T, class>
using enable_hash = T;

namespace std{
    template<class T> struct hash<enable_hash<T, decltype(std::declval<T>().hashCode())>>   {
        std::size_t operator()(const T& x) const { 
            return x.hashCode();
        }
    };
}

int main() {
    std::unordered_set<B01> us;
    (void)us;
}

[live demo]

（灵感来自）

然而，只要这可以在 gcc 上工作，它就不是真正被 c++ 标准所允许的 ~~（但我也不确定它是否真的被字面上禁止...）~~.请参阅此上下文中的线程。

编辑：

正如@Barry 所指出的那样，这种 gcc 行为不是由 c++ 标准强制执行的，因此绝对不能保证即使在下一个 gcc 版本中它也能工作...它甚至可以被视为一个错误，因为它允许部分特化实际上不特化该模板的模板。

方案三（首选）

另一种方法是专门化 std::unordered_set 而不是 std::hash:

#include <iostream>
#include <type_traits>
#include <unordered_set>

class specializeUnorderedSet { };

class B01: public specializeUnorderedSet { 
    public: size_t hashCode() const { return 0; }  
};

class B02: public specializeUnorderedSet { 
    public: size_t hashCode() const { return 0; } 
};

template <class T>
struct my_hash {
    std::size_t operator()(const T& x) const { 
        return x.hashCode();
    }
};

template <class...>
using voider = void;

template <class T, class = void>
struct hashCodeTrait: std::false_type { };

template <class T>
struct hashCodeTrait<T, voider<decltype(std::declval<T>().hashCode())>>: std::true_type { };

namespace std{

    template <class T>
    struct unordered_set<T, typename std::enable_if<hashCodeTrait<T>::value && std::is_base_of<specializeUnorderedSet, T>::value, std::hash<T>>::type, std::equal_to<T>, std::allocator<T>>:
           unordered_set<T, my_hash<T>, std::equal_to<T>, std::allocator<T>> { };

}

int main() {
    std::unordered_set<B01> us;
    (void)us;
}

根据所提出的讨论here it should be perfectly valid. It also work in gcc, clang, icc, VS

为了能够在不干扰 classes 代码的情况下使用代码，我相信如果给定 class 不涉及 std 命名空间，我们可以利用 ADL 规则来进行 sfinae 检查。你可以找到一个背景. Credits also to 。该方法可以更改如下：

#include <utility>
#include <unordered_set>
#include <string>
#include <type_traits>
#include <functional>

template< class Type >
void ref( Type&& ) {}

template< class Type >
constexpr auto involve_std()
   -> bool
{
    using std::is_same;
    using std::declval;
    return not is_same< void, decltype( ref( declval<Type &>() ) )>::value;
}

class B01 { 
    public: size_t hashCode() const { return 0; }  
};

class B02 { 
    public: size_t hashCode() const { return 0; } 
};

template <class T>
struct my_hash {
    std::size_t operator()(const T& x) const { 
        return x.hashCode();
    }
};

template <class...>
struct voider {
    using type = void;
};

template <class T, class = void>
struct hashCodeTrait: std::false_type { };

template <class T>
struct hashCodeTrait<T, typename voider<decltype(std::declval<T>().hashCode())>::type>: std::true_type { };

namespace std{

    template <class T>
    struct unordered_set<T, typename std::enable_if<hashCodeTrait<T>::value && !involve_std<T>(), std::hash<T>>::type, std::equal_to<T>, std::allocator<T>>:
           unordered_set<T, my_hash<T>, std::equal_to<T>, std::allocator<T>> { };

}

int main() {
    std::unordered_set<B01> usb01;
    std::unordered_set<std::string> uss;
    static_assert(std::is_base_of<std::unordered_set<B01, my_hash<B01>>, std::unordered_set<B01>>::value, "!");
    static_assert(!std::is_base_of<std::unordered_set<std::string, my_hash<std::string>>, std::unordered_set<std::string>>::value, "!");
    (void)usb01;
    (void)uss;
}

[gcc test], [clang test], [icc test] [gcc 4.9] [VC]

使 std 的 data-structure 默认使用我现有的 non-static 散列函数 "hashCode()"

Make std's data-structure use my existing non-static hash function "hashCode()" by default

c++

hash

templates

sfinae

c++11

问题

概念