38

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>’
Rakholiya Jenish
  • 3,165
  • 18
  • 28
Shambo
  • 898
  • 1
  • 10
  • 17

2 Answers2

59

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.

Community
  • 1
  • 1
Casey
  • 41,449
  • 7
  • 95
  • 125
  • 10
    (same comment I made to Jesse) `std::hash()(x.first) ^ std::hash()(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. – Tony Delroy Oct 06 '14 at 10:54
  • 12
    Wait so not only does the stl not implement `std::hash` for `std::pair`s but it also doesn't let you implement it yourself? Why? – Claudiu Dec 23 '14 at 22:43
  • 2
    @Claudiu: You can implement it yourself, but only if at least one of the template parameters is a user-defined type. – David Stone Apr 14 '15 at 05:11
  • 1
    @Casey: I don't understand the reason behind keeping such a standard. Can you please explain the reason for it? – Sidak Apr 05 '16 at 18:25
  • 8
    @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>` 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. – Casey Apr 05 '16 at 19:59
  • 5
    @Casey, damn! C++35... About two more decades? That's harsh... :-) – WhiZTiM Feb 11 '17 at 09:28
4

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);
    }
};
Vladimir Reshetnikov
  • 11,750
  • 4
  • 30
  • 51
  • 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. – Konchog Mar 28 '19 at 09:29
  • `sizeof`gives the size in bytes, but `<<` takes the number of bits to shift by. https://en.cppreference.com/w/cpp/language/sizeof – Vladimir Reshetnikov Mar 28 '19 at 17:33
  • 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 Mar 29 '19 at 10:03
  • This, (for eg. uintmax_t) would compile to rol 32: hash = (hash << (sizeof(uintmax_t) << 2)) | (hash >> (sizeof(uintmax_t)) << 2)); – Konchog Mar 29 '19 at 14:58