search

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

Use pair as key #109

Closed xissburg closed 3 years ago

xissburg commented 3 years ago

I am unable to create a robin_hood::unordered_flat_map<robin_hood::pair<int, int>, int> or robin_hood::unordered_flat_map<std::pair<int, int>, int>. This is the error I get:

https://raw.githubusercontent.com/martinus/robin-hood-hashing/master/src/include/robin_hood.h:1488:31: error: call to implicitly-deleted default constructor of 'robin_hood::hash<std::pair<int, int>>'

More details at https://godbolt.org/z/8WGoKz. Another observation was that I had to add #include <limits> in order to compile.

martinus commented 3 years ago

That's because there is no hash for robin_hood::pair. E.g. this might work (untested):

namespace robin_hood {

template<>
struct hash<robin_hood::pair<int, int>> {
    size_t operator()(robin_hood::pair<int, int> const& p) const noexcept {
        auto a = hash<int>{}(p.first);
        auto b = hash<int>{}(p.second);
        return hash_combine(a, b);
    }

    static size_t hash_combine(size_t seed, size_t v) noexcept {
        // see https://www.boost.org/doc/libs/1_55_0/doc/html/hash/reference.html#boost.hash_combine
        seed ^= v + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

}

See https://godbolt.org/z/dT5roq