使std的数据结构默认使用我现有的非静态哈希函数"hashCode()"

Question

我有一个中等大小的代码库(> 200 .cpp),它使用一个函数hashCode()来返回哈希值: -

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
};

我已在各种位置使用它,例如在我的自定义数据结构中.它运作良好.

现在,我想让std::数据结构识别哈希算法: -

这是我应该做的: - (从cppreference修改,我将调用此代码#D).

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

如果我插入块#D中的每一个类((与适当的执行)B01,B02...),我可以打电话: -

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

不传递第二个模板参数,
我的哈希算法(#H01)将被调用.(默认)

题

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

我可以再补充一个单一的块#D(在顶部集流管？)
,并从那里,重新路由 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>;

然后使用它(使用你的任何Bxx)就像你使用的那样std::unordered_set:

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;
}

概念

如果您可以使用概念,它们可以让您std::hash按照自己的方式专门化课程:

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

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

Answer 2

在创建条件以将std容器模板的hash参数默认为类组的成员方法时,应避免引入新问题.

• 冗余
• 便携性问题
• 奥术结构

经典的面向对象方法可能需要对200多个类进行图案化编辑,以确保它们提供std :: hash容器使用的基础知识.下面给出了一些用于组转换的选项,以提供两种所需的方法.

• 公共hashCode()在具体类中定义,它对于该类是唯一的,或者如果它遵循跨类通用的模式,则通过继承.
• 定义了公共运算符==().

两个模板

这两个模板将删除冗余并简化声明,如图所示.

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 {
    ...
    virtual std::size_t hashCode() const {
        return std::hash<std::string>{}(ms1)
                ^ std::hash<std::string>{}(ms2);
    } }

假设代码使用{inline,则以下sed表达式可以节省转换时间.类似的表达式可以与Boost一起使用或使用像Python这样的脚本语言.

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

基于AST的工具会更可靠. 这解释了如何使用clang功能进行代码转换.有一些新增功能,例如C++代码转换的Python控制器.

讨论

哈希算法可以驻留在几个选项中.

• std容器声明的抽象类的方法
• 具体类的方法(例如示例中的#H01)
• 结构模板(通常适得其反并且不透明)
• 默认的std :: hash

这是一个编译单元,它提供了一个清晰的演示,说明如何实现所需的默认值以及上面列出的其他三个目标,同时为任何给定类定义散列算法提供灵活性.根据具体情况,可以删除各种功能.

#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 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():返回42

另见我的类似问题的相关答案.

然而,概念是解决这类问题的未来之路.

Answer 4

解决方案一

如果您可以使用虚拟参数创建 classes B01, B02, ... 类模板，您可以简单地使用采用std::hash虚拟模板参数的 for 模板模板的专业化：

#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;
}

[现场演示]

解决方案二（包含错误/不使用它）

但我相信你想要的更像是这样的：

#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;
}

[现场演示]

（受到这个答案的启发）

然而，只要这可以在 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;
}

根据这里提出的讨论，它应该是完全有效的。它也适用于gcc , clang , icc , VS

为了能够在不干扰类代码的情况下使用代码，我相信我们可以利用 ADL 规则来使 sfinae 检查给定的类是否不涉及 std 命名空间。您可以在这里找到背景。也感谢干杯和 hth。- 阿尔夫. 该方法可以更改如下：

#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 测试]、[clang 测试]、[icc 测试] [gcc 4.9] [VC]