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

hash is deleted for std::pair? #140

Open h-2 opened 2 years ago

h-2 commented 2 years ago

And I have another one. Simply declaring this flat_map already fails:

robin_hood::unordered_flat_map<std::pair<uint16_t, uint16_t>, std::vector<std::pair<uint16_t, uint16_t>>> foo;

Godbolt link: https://godbolt.org/z/Ezca6K1xn

capitalai commented 2 years ago

You can change 2 lines and it may works.

struct hash: public std::hash<T> { => 'struct hash { auto result = std::hash<T>::operator()(obj); => auto result = std::hash<T>{}(obj);

slavenf commented 2 years ago

@h-2 The specialization of std::hash for std::pair<T1, T2> does not exist in standard C++ library. You have to write it yourself. You can see that note on https://en.cppreference.com/w/cpp/utility/hash

slavenf commented 2 years ago

Here is an example how to write specialization of std::hash for std::pair:

// This is similar to boost::hash_combine
//
template <class T>
void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{

template <class T1, class T2>
struct hash<std::pair<T1, T2>>
{
    std::size_t operator()(const std::pair<T1, T2>& p) const noexcept
    {
        std::size_t seed = 0;

        hash_combine(seed, p.first);
        hash_combine(seed, p.second);

        return seed;
    }
};

}