martinus / robin-hood-hashing

Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
https://gitter.im/martinus/robin-hood-hashing
MIT License
1.5k stars 142 forks source link

Make hash<T> accept types other than T #144

Closed acd1034 closed 2 years ago

acd1034 commented 2 years ago

In Issue #80, it was reported that Heterogenious lookup did not work properly. I found that this bug occurs under the following conditions.

  1. User specializes std::hash
  2. User is using robin_hood::hash

Since robin_hood::hash inherits from std::hash, it was expected that operator() of std::hash<Key> would be called when a type other than Key is passed to operator() of robin_hood::hash<Key>. However, it turns out that operator() of std::hash is hidden by operator() of robin_hood::hash.

cf.)

What I would like to do with this pull request

Correctly call operator() of std::hash in operator() of robin_hood::hash.

Specific proposals

robin_hood::hash::operator() is currently declared as follows.

template <typename T, typename Enable = void>
struct hash : public std::hash<T> {
    size_t operator()(T const& obj) const;
};

I would like to replace the above declaration with the one below. Also add an enabler to check if the intended operator() is defined in std::hash<T>.

template <typename T, typename Enable = void>
struct hash : public std::hash<T> {
    template <typename U
              typename = typename detail::void_type<decltype(std::declval<std::hash<T>>().operator()(std::declval<U const&>()))>::type>
    size_t operator()(U const& obj) const;
};

Comments on Issue #80

The reason why the first comment in #80 works is that it is possible to convert from std::string_view to std::string.

On the other hand, the following comment does not work because the conversion from std::string_view to boost::beast::static_string<N> is impossible.

Related issues

Closes #80