javaLover javaLover - 4 years ago 61
C++ Question

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

I have a moderate-size codebase (>200

.cpp
) that use a function
hashCode()
to return hash number:-

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


I have used it in various locations, e.g. in my custom data-structure. It works well.

Now, I want to make the hash algorithm recognized by
std::
data structure:-

Here is what I should do :- (modified from cppreference, I will call this code
#D
).

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


If I insert the block
#D
(with appropriate implementation) in every class (
B01
,
B02
,...), I can call :-

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


without passing the second template argument,

and my hash algorithm (
#H01
) will be called. (by default)

Question



To make it recognize all of my
B01::hashCode, B02::hashCode, ...
,

do I have to insert the block
#D
into all 200+
Bxx.h
?

Can I just add a single block
#D
(in a top header?)

and, from there, re-route
std::anyDataStructure
to call
hashCode()
whenever possible?

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


It sounds like a SFINAE question to me.

Side note: The most similar question in SO didn't ask about how to achieve this.

Edit (Why don't I just refactor it? ; 3 Feb 2017)


  • I don't know if brute force refactoring is a right path. I guess there might be a better way.

  • hashCode()
    is my home. I emotionally attach to it.

  • I want to keep my code short and clean as possible.
    std::
    blocks are dirty.

  • It may be just my curiosity. If I stubborn not to refactor my code, how far C++ can go?


Answer Source

Solution one

If you can make classes B01, B02, ... class templates with dummy parameters you could simply go along with the specialization of the std::hash for template template that takes dummy template parameter:

#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]

Solution two (contain error/don't use it)

But I believe what you desire looks more like this:

#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]

(Inspired by this answer)

However as long this can work on gcc it isn't really allowed by the c++ standard (but I'm also not sure if it is actually literally disallowed...). See this thread in this context.

Edit:

As pointed out by @Barry this gcc behaviour is not mandated by c++ standard and as such there is absolutely no guaranties it will work even in the next gcc version... It can be even perceived as a bug as it allows partial specialization of a template that in fact does not specialize that template.

Solution three (preffered)

Another way could be to specialize std::unordered_set instead of 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;
}

According to the discussion presented here it should be perfectly valid. It also work in gcc, clang, icc, VS

To be able to use the code without interfering in the code of classes I believe we can utilize the ADL rules to make sfinae check if given class does not involve std namespace. You can find a background here. Credits also to Cheers and hth. - Alf. The approach could be change as follows:

#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]

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download