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

b09cbbtk  于 2024-01-09  发布在  其他
关注(0)|答案(5)|浏览(162)

我有一个中等大小的代码库（>200 .cpp），它使用函数hashCode()返回哈希值：

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

字符串
我已经在不同的地方使用过它，例如在我的自定义数据结构中。它工作得很好。
现在，我想让std::数据结构识别的哈希算法：
下面是我应该做的：-（修改自cppreference，我将此代码称为#D）。

  1. //#D
  2. namespace std {
  3.     template<> struct hash<B01> {
  4.         std::size_t operator()(const B01& b) const {
  5.             /* hash algorithm #H01 */
  6.         }
  7.     };
  8. }

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

  1. std::unordered_set<B01> b01s;
  2. std::unordered_set<B02> b02s;

型

**不传递第二个模板参数，

我的哈希算法（#H01）将被调用。（默认）

问题

为了让它识别我所有的B01::hashCode, B02::hashCode, ...，
我必须将块#D插入到所有200+ Bxx.h中吗？
我可以只添加一个单个块#D（在顶部标题中？）
并从那里，* 重新路由 * std::anyDataStructure调用hashCode()只要可能？

  1. //pseudo code
  2. namespace std{
  3.     template<> struct hash<X>   {
  4.         std::size_t operator()(const X& x) const { // std::enable_if??
  5.             if(X has hashCode()){    //e.g. T=B01 or B02       
  6.                 make this template highest priority   //how?
  7.                 return hashCode();
  8.             }else{                   //e.g. T=std::string
  9.                 don't match this template;  
  10.             }
  11.         }
  12.     };
  13. }

型
这听起来像一个SFINAE问题给我。

旁注：SO中的The most similar question没有询问如何实现这一点。
Edit（Why don't I just refactor it？; 3 Feb 2017）

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

5条答案

按热度按时间
tjjdgumg

tjjdgumg1#

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

  1. struct MyHash {
  2.     template <class T>
  3.     auto hashCode(const T & t, int) const -> decltype(t.hashCode()) {
  4.         return t.hashCode();
  5.     }
  6.     template <class T>
  7.     auto hashCode(const T & t, long) const -> decltype(std::hash<T>{}(t)) {
  8.         return std::hash<T>{}(t);
  9.     }
  10.     
  11.     template <class T>
  12.     auto operator()(const T & t) const -> decltype(hashCode(t,42)) {
  13.         return hashCode(t,42);
  14.     }
  15. };

字符串
别名为std::unordered_set，哈希类型为MyHash：

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

型
或者如果你还想提供 Equal 函子和分配器，可以更完整：

  1. template<
  2.     class Key,
  3.     class KeyEqual = std::equal_to<Key>,
  4.     class Allocator = std::allocator<Key>
  5. >
  6. using my_unordered_set = std::unordered_set<Key, MyHash, KeyEqual, Allocator>;

型
然后像使用std::unordered_set一样使用它（与任何Bxx一起使用）：

  1. int main() {
  2.     my_unordered_set<B01> b01s;
  3.     my_unordered_set<B02> b02s;
  5.     // or lonely with your type:
  6.     B01 b01{/*...*/};
  7.     std::cout << MyHash{}(b01) << std::endl;
  9.     // or any other:
  10.     std::string str{"Hello World!"};
  11.     std::cout << MyHash{}(str) << std::endl;
  12. }

型

概念

如果你可以使用concepts，它们可以让你按照你想要的方式专门化std::hash类：

  1. template <class T>
  2. concept HashCodeConcept = requires(T const & t)
  3. {
  4.     {t.hashCode()} -> std::same_as<std::size_t>;
  5. };
  7. namespace std {
  8.     template <HashCodeConcept T>
  9.     struct hash<T> {
  10.         std::size_t operator()(const T& t) const {
  11.             return  t.hashCode();
  12.         }
  13.     };
  14. }

型

展开查看全部
赞(0）分享  回复(0）举报  2024-01-09
r7xajy2e

r7xajy2e2#

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

  1. #include <type_traits>
  2. #include <unordered_set>
  3. #include <iostream>
  5. template<typename T = void>
  6. struct B {
  7.   B(int i) : x(i) {}
  8.   std::size_t hashCode() const
  9.   {
  10.     std::cout<<"B::hashCode(): return "<<x<<std::endl;
  11.     return x;
  12.   }
  13.   bool operator==(B const&b) const
  14.   { return x==b.x; }
  15. private:
  16.   int x;
  17. };
  19. template<typename T,
  20.          typename = decltype(std::declval<T>().hashCode())> 
  21. using enable_if_has_hashCode = T;
  23. namespace std {
  24.   template<template<typename...> class T, typename... As> 
  25.   struct hash<enable_if_has_hashCode<T<As...>>> 
  26.   {
  27.     std::size_t operator()(const T<As...>& x) const
  28.     { return x.hashCode(); }
  29.   };
  30.   // the following would not work, as its not a partial specialisation
  31.   //    (some compilers allow it, but clang correctly rejects it)
  32.   // tempate<typename T>
  33.   // struct hash<enable_if_hashCode<T>>
  34.   // { /* ... */ }; 
  35. }
  37. int main()
  38. {
  39.   using B00 = B<void>;
  40.   B00 b(42);
  41.   std::unordered_set<B00> set;
  42.   set.insert(b);
  43. }

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

展开查看全部
赞(0）分享  回复(0）举报  2024-01-09
ckx4rj1h

ckx4rj1h3#

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

  • 冗余
  • 可移植性问题
  • 《双城之战》结构

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

  • 公共hashCode（）在具体类中定义，它对该类是唯一的，或者如果它遵循跨类通用的模式，则通过继承来定义。
  • 定义了一个公共运算符==（）。
    两个模板

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

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

字符串

节省积分时间

一个超类的例子：

  1. class AbstractB {
  2.     ...
  3.     virtual std::size_t hashCode() const {
  4.         return std::hash<std::string>{}(ms1)
  5.                 ^ std::hash<std::string>{}(ms2);
  6.     } }

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

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

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

讨论

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

  • std容器声明的抽象类的方法
  • 具体类的方法（如示例中的#H01）
  • 结构模板（通常会产生反效果且不透明）
  • 默认的std：：hash

这里有一个编译单元，它提供了一个经典的演示，演示了如何实现所需的默认值和上面列出的其他三个目标，同时提供了为任何给定类定义哈希算法的灵活性。根据具体情况，可以删除各种功能。

  1. #include <string>
  2. #include <functional>
  3. #include <unordered_set>
  5. template <typename T>
  6.     struct HashStructForPtrs {
  7.         std::size_t operator()(const T tp) const {
  8.             return tp->hashCode(); } };
  9. template <class T>
  10.     using SetOfBPtrs = std::unordered_set<T, HashStructForPtrs<T>>;
  12. template <typename T>
  13.     struct HashStruct {
  14.         std::size_t operator()(const T & t) const {
  15.             return t.hashCode(); } };
  16. template <class T>
  17.     using SetOfB = std::unordered_set<T, HashStruct<T>>;
  19. class AbstractB {
  20.     protected:
  21.         std::string ms;
  22.     public:
  23.         virtual std::size_t hashCode() const {
  24.             return std::hash<std::string>{}(ms); }
  25.         // other option: virtual std::size_t hashCode() const = 0;
  26.         bool operator==(const AbstractB & b) const {
  27.             return ms == b.ms; } };
  29. class B01 : public AbstractB {
  30.     public:
  31.         std::size_t hashCode() const {
  32.             return std::hash<std::string>{}(ms) ^ 1; } };
  34. class B02 : public AbstractB {
  35.     public:
  36.         std::size_t hashCode() const {
  37.             return std::hash<std::string>{}(ms) ^ 2; } };
  39. int main(int iArgs, char * args[]) {
  41.     SetOfBPtrs<AbstractB *> setOfBPointers;
  42.     setOfBPointers.insert(new B01());
  43.     setOfBPointers.insert(new B02());
  45.     SetOfB<B01> setOfB01;
  46.     setOfB01.insert(B01());
  48.     SetOfB<B02> setOfB02;
  49.     setOfB02.insert(B02());
  51.     return 0; };

型

展开查看全部
赞(0）分享  回复(0）举报  2024-01-09
brjng4g3

brjng4g34#

我已经想出了一些看起来部分工作的东西。这是一个变通方案，允许你在实现hashCode的类型上使用std::hash。看看：

  1. //some class that implements hashCode
  2. struct test
  3. {
  4.     std::size_t hashCode() const
  5.     {
  6.         return 0;//insert your has routine
  7.     }
  8. };
  9. //helper class
  10. struct hashable
  11. {
  12.     hashable():value(0){}
  13.     template<typename T>
  14.     hashable(const T& t):value(t.hashCode())
  15.     {}
  16.     template<typename T>
  17.     std::size_t operator()(const T& t) const
  18.     {
  19.         return t.hashCode();
  20.     }
  22.     std::size_t value;
  23. };
  25. //hash specialization of hashable
  26. namespace std {
  27.     template<>
  28.     struct hash<hashable>
  29.     {
  30.         typedef hashable argument_type;
  31.         typedef std::size_t result_type;
  32.         result_type operator()(const argument_type& b) const {
  33.             return b.value;
  34.         }
  35.     };
  36. }
  37. //helper alias so you dont have to specify the hash each time.
  38. template<typename T, typename hash = hashable>
  39. using unordered_set = std::unordered_set<T,hash>;
  41. int main(int argc, char** argv)
  42. {
  43.     unordered_set<test> s;
  44.     test t;
  45.     std::cout<<std::hash<hashable>{}(t)<<std::endl;
  46. }

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

  1. unordered_set<test> s;
  2. test t;
  3. s.insert(t);

型
我注意到有一些编译器错误。
我已经通过添加以下内容将test类更新为equality comparable：

  1. bool operator==(const test& other) const
  2. {
  3.     return hashCode() == other.hashCode();
  4. }

型
到test，这使得：

  1. //some class that implements hashCode
  2. struct test
  3. {
  4.     std::size_t hashCode() const
  5.     {
  6.         return 0;//insert your has routine
  7.     }
  8.     bool operator==(const test& other) const
  9.     {
  10.         return hashCode() == other.hashCode();
  11.     }
  12. };

型

展开查看全部
赞(0）分享  回复(0）举报  2024-01-09
yc0p9oo0

yc0p9oo05#

解决方案一

如果你可以用伪参数创建类B01，B02，. class template，你可以简单地沿着std::hash的特殊化，以获取伪模板参数：

  1. #include <iostream>
  2. #include <unordered_set>
  4. struct Dummy {};
  6. template <class = Dummy>
  7. class B01{ 
  8.     public: size_t hashCode() const { return 0; }  
  9. };
  10. template <class = Dummy>
  11. class B02{ 
  12.     public: size_t hashCode() const { return 0; } 
  13. };
  15. namespace std{
  16.     template<template <class> class TT> struct hash<TT<Dummy>>   {
  17.         std::size_t operator()(const TT<Dummy>& x) const { 
  18.             return x.hashCode();
  19.         }
  20.     };
  21. }
  23. int main() {
  24.     std::unordered_set<B01<>> us;
  25.     (void)us;
  26. }

字符串
live demo(http://melpon.org/wandbox/permlink/M8tPQVQjmaZ6AcJF)

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

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

  1. #include <iostream>
  2. #include <unordered_set>
  4. class B01{ 
  5.     public: size_t hashCode() const { return 0; }  
  6. };
  8. class B02{ 
  9.     public: size_t hashCode() const { return 0; } 
  10. };
  12. template <class T, class>
  13. using enable_hash = T;
  15. namespace std{
  16.     template<class T> struct hash<enable_hash<T, decltype(std::declval<T>().hashCode())>>   {
  17.         std::size_t operator()(const T& x) const { 
  18.             return x.hashCode();
  19.         }
  20.     };
  21. }
  23. int main() {
  24.     std::unordered_set<B01> us;
  25.     (void)us;
  26. }

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

编辑：

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

解决方案三（首选）

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

  1. #include <iostream>
  2. #include <type_traits>
  3. #include <unordered_set>
  5. class specializeUnorderedSet { };
  7. class B01: public specializeUnorderedSet { 
  8.     public: size_t hashCode() const { return 0; }  
  9. };
  11. class B02: public specializeUnorderedSet { 
  12.     public: size_t hashCode() const { return 0; } 
  13. };
  15. template <class T>
  16. struct my_hash {
  17.     std::size_t operator()(const T& x) const { 
  18.         return x.hashCode();
  19.     }
  20. };
  22. template <class...>
  23. using voider = void;
  25. template <class T, class = void>
  26. struct hashCodeTrait: std::false_type { };
  28. template <class T>
  29. struct hashCodeTrait<T, voider<decltype(std::declval<T>().hashCode())>>: std::true_type { };
  31. namespace std{
  32.     
  33.     template <class T>
  34.     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>>:
  35.            unordered_set<T, my_hash<T>, std::equal_to<T>, std::allocator<T>> { };
  36.     
  37. }
  39. int main() {
  40.     std::unordered_set<B01> us;
  41.     (void)us;
  42. }

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

  1. #include <utility>
  2. #include <unordered_set>
  3. #include <string>
  4. #include <type_traits>
  5. #include <functional>
  7. template< class Type >
  8. void ref( Type&& ) {}
  10. template< class Type >
  11. constexpr auto involve_std()
  12.    -> bool
  13. {
  14.     using std::is_same;
  15.     using std::declval;
  16.     return not is_same< void, decltype( ref( declval<Type &>() ) )>::value;
  17. }
  19. class B01 { 
  20.     public: size_t hashCode() const { return 0; }  
  21. };
  23. class B02 { 
  24.     public: size_t hashCode() const { return 0; } 
  25. };
  27. template <class T>
  28. struct my_hash {
  29.     std::size_t operator()(const T& x) const { 
  30.         return x.hashCode();
  31.     }
  32. };
  34. template <class...>
  35. struct voider {
  36.     using type = void;
  37. };
  39. template <class T, class = void>
  40. struct hashCodeTrait: std::false_type { };
  42. template <class T>
  43. struct hashCodeTrait<T, typename voider<decltype(std::declval<T>().hashCode())>::type>: std::true_type { };
  45. namespace std{
  47.     template <class T>
  48.     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>>:
  49.            unordered_set<T, my_hash<T>, std::equal_to<T>, std::allocator<T>> { };
  51. }
  53. int main() {
  54.     std::unordered_set<B01> usb01;
  55.     std::unordered_set<std::string> uss;
  56.     static_assert(std::is_base_of<std::unordered_set<B01, my_hash<B01>>, std::unordered_set<B01>>::value, "!");
  57.     static_assert(!std::is_base_of<std::unordered_set<std::string, my_hash<std::string>>, std::unordered_set<std::string>>::value, "!");
  58.     (void)usb01;
  59.     (void)uss;
  60. }

型
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）举报  2024-01-09
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com