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

b09cbbtk 于 9个月前发布在其他

关注(0)|答案(5)|浏览(123)

我有一个中等大小的代码库（>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 */
        }
    };
}

型
如果我在每个类（B01，B02，.）中插入块#D（使用适当的实现），我可以调用：

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中的The most similar question没有询问如何实现这一点。
Edit（Why don't I just refactor it？; 3 Feb 2017）

我不知道蛮力重构是不是一条正确的道路。我想可能有更好的方法。
hashCode()是我的家我对它有感情
我想让我的代码尽可能简短和干净。std::块是脏的。
可能只是我的好奇心，如果我固执地不重构我的代码，C++能走多远？

c++

来源：https://stackoverflow.com/questions/41867111/make-stds-data-structure-use-my-existing-non-static-hash-function-hashcode

5条答案

按热度按时间

tjjdgumg1#

不一定要这样，你也可以有一个仿函数：

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类：

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

型

赞(0）回复(0）举报 9个月前

r7xajy2e2#

您正在寻找的基于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);
}

字符串
produces（在MacOS上使用clang++）
B：：hashvalue（）：return 42
this related answer也是我的一个类似问题。
然而，concepts是未来解决此类问题的方法。

赞(0）回复(0）举报 9个月前

ckx4rj1h3#

在创建条件以将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);
    } }

型
下面的sed表达式可以保存转换时间，假设代码使用{ inline。类似的表达式可以使用Boost或使用Python等脚本语言。

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

型
基于AST的工具会更可靠。This解释了如何使用clang功能进行代码转换。有新的补充，如C++代码转换的this Python controller。

讨论

对于哈希算法可以驻留的位置，有几个选项。

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

型

赞(0）回复(0）举报 9个月前

brjng4g34#

我已经想出了一些看起来部分工作的东西。这是一个变通方案，允许你在实现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的类中检索哈希值。std::hash专门化查找hashable的示例，但模板化构造函数允许从具有hasCode的类中构造示例。
这里唯一的问题是，你将不得不编写unordered_set而不是std::unordered_set来使用它，你将不得不确保std::unordered_set没有以任何方式被带入范围。所以你不能在你的源代码中有像using namespace std或using std::unordered_set这样的东西。但是除了使用中的一些问题之外，这对你来说可能是可行的。
当然，这只是解决真实的问题的一个权宜之计..
我还想指出的是，与此代码替代是一个错误.
编辑：
尝试跑步后：

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

型
我注意到有一些编译器错误。
我已经通过添加以下内容将test类更新为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();
    }
};

型

赞(0）回复(0）举报 9个月前

yc0p9oo05#

解决方案一

如果你可以用伪参数创建类B01，B02，. class template，你可以简单地沿着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(http://melpon.org/wandbox/permlink/M8tPQVQjmaZ6AcJF)

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

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

#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(http://melpon.org/wandbox/permlink/SD7kOcXwMtLWF3te)的
（受此答案启发）
然而，只要这可以在gcc上工作，c++标准就不允许这样做（但我也不确定是否真的不允许这样做）。

编辑：

正如@巴里所指出的，这种gcc行为不是由c++标准强制执行的，因此绝对没有任何限制，它甚至可以在下一个gcc版本中工作.它甚至可以被认为是一个bug，因为它允许模板的部分专门化，而实际上并没有专门化该模板。

解决方案三（首选）

另一种方法是专门化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的讨论，它应该是完全有效的。它也适用于gcc，clang，icc，VS
为了能够使用代码而不干扰类的代码，我相信我们可以利用ADL规则来检查sfinae是否给定类不涉及std命名空间。你可以找到一个背景here。也归功于Cheers and hth. - Alf。方法可以改变如下：

#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(http://melpon.org/wandbox/permlink/D1dWjQn1V8ThrGRi)、clang test(http://melpon.org/wandbox/permlink/FHMZ9DWGY0RlhyDJ)、icc test(https://godbolt.org/g/CqcE1d) gcc 4.9(http://melpon.org/wandbox/permlink/3nAjQBRqVXQ7BlAX) VC(http://rextester.com/VTLZWI97536)

赞(0）回复(0）举报 9个月前

我来回答

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

问题

5条答案

概念

相关问题

热门标签

最新问答