error for hash function of pair of ints

Question

I have the following class with an unordered_map member, and a hash function defined for pair<int,int>

class abc
{public :
    unordered_map < pair<int,int> , int > rules ;
    unsigned nodes;
    unsigned packet ;     
};

namespace std {
template <>
    class hash < std::pair< int,int> >{
    public :
        size_t operator()(const pair< int, int> &x ) const
        {
            size_t h =   std::hash<int>()(x.first) ^ std::hash<int>()(x.second);
            return  h ;
        }
    };
}

But I am getting the following errors :

error: invalid use of incomplete type ‘struct std::hash<std::pair<int, int> >

error: declaration of ‘struct std::hash<std::pair<int, int> >

error: type ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>’ is not a direct base of ‘std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>’

Solution 1

Unfortunately, this program has undefined behavior. C++11 §17.6.4.2.1:

A program may add a template specialization for any standard library template to namespace std only if the declaration depends on a user-defined type and the specialization meets the standard library requirements for the original template and is not explicitly prohibited.

hash<pair<int,int>> depends on primitive and standard library types only. This is easily worked around by defining your hash class outside of namespace std, and using that hash explicitly in your map declaration:

struct pairhash {
public:
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const
  {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};

class abc {
  std::unordered_map<std::pair<int,int>, int, pairhash> rules;
};

EDIT: I've used xor to combine the hashes of the pair members here because I'm lazy, but for serious use xor is a fairly crappy hash combining function.

Solution 2

I prefer to rely on the standard implementation of std::hash<uintmax_t> to mix hashes of components of an std::pair:

#include <functional>
#include <utility>

struct hash_pair final {
    template<class TFirst, class TSecond>
    size_t operator()(const std::pair<TFirst, TSecond>& p) const noexcept {
        uintmax_t hash = std::hash<TFirst>{}(p.first);
        hash <<= sizeof(uintmax_t) * 4;
        hash ^= std::hash<TSecond>{}(p.second);
        return std::hash<uintmax_t>{}(hash);
    }
};

Comments

[Tony Delroy]

(same comment I made to Jesse) std::hash<T>()(x.first) ^ std::hash<T>()(x.second); - that's a spectacularly collision-prone way to hash a pair, as every pair with two identical value hashes to 0, and every pair {a, b} hashes the same as {b, a}. For vaguely demanding use, much better to find a hash_combine function and employ that.

[Claudiu]

Wait so not only does the stl not implement std::hash for std::pairs but it also doesn't let you implement it yourself? Why?

[David Stone]

@Claudiu: You can implement it yourself, but only if at least one of the template parameters is a user-defined type.

[Sidak]

@Casey: I don't understand the reason behind keeping such a standard. Can you please explain the reason for it?

[Casey]

@Sidak The general rule exists to keep users from interfering with library implementors and/or future changes to the standard. A library implementation can, for example, provide a specialization of std::hash<std::pair<T, U>> as a conforming extension. Or C++35 might define such a specialization. Neither would be possible - without breaking some programs - if users were allowed to define such specializations themselves.

[WhiZTiM]

@Casey, damn! C++35... About two more decades? That's harsh... :-)

[Konchog]

hash <<= sizeof(uintmax_t) * 4; Won't this just remove the hash altogether? E.g imagine a uintmax of 64 bits. shifting it left (4*64) bits is pushing it beyond it's limit.

[Vladimir Reshetnikov]

sizeofgives the size in bytes, but << takes the number of bits to shift by. en.cppreference.com/w/cpp/language/sizeof

[Konchog]

Thanks Vlad. I had forgotten that it was measured in bytes, not bits. So the purpose is to shift the first hash exactly half the size of TFirst. Would it not be better to rotate the hash that number of bits? Otherwise we lose half the bits of the first hash.

[Konchog]

This, (for eg. uintmax_t) would compile to rol 32: hash = (hash << (sizeof(uintmax_t) << 2)) | (hash >> (sizeof(uintmax_t)) << 2));