unordered_map hash function c++

Question

I need to define an unordered_map like this unordered_map<pair<int, int>, *Foo>, what is the syntax for defining and passing a hash and equal functions to this map?

I've tried passing to it this object:

class pairHash{
public:
    long operator()(const pair<int, int> &k) const{
        return k.first * 100 + k.second;
    }
};

and no luck:

unordered_map<pair<int, int>, int> map = unordered_map<pair<int, int>, int>(1,
*(new pairHash()));

I have no Idea what is the size_type_Buskets means so I gave it 1. What is the right way to do it? Thanks.

Answer 1

This is an unfortunate omission in C++11; Boost has the answer in terms of hash_combine. Feel free to just paste it from them! Here's how I hash pairs:

template <class T>
inline 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<typename S, typename T> struct hash<pair<S, T>>
  {
    inline size_t operator()(const pair<S, T> & v) const
    {
      size_t seed = 0;
      ::hash_combine(seed, v.first);
      ::hash_combine(seed, v.second);
      return seed;
    }
  };
}

You can use hash_combine as the basis for many other things, like tuples and ranges, so you could hash an entire (ordered) container, for example, as long as each member is individually hashable.

Now you can just declare a new map:

std::unordered_map<std::pair<int, int>, my_mapped_type> mymap;

---

If you want to use your homebrew hasher (which hasn't got good statistical properties), you have to specify the template parameters explicitly:

std::unordered_map<std::pair<int,int>, int, pairHash> yourmap;

Note that there's no need to specify a copy of a hasher object, as the default is to default-construct one for you.

Answer 2

The return type of the hash function should be size_t, not long (although this is not the cause of the error). The syntax you've shown for providing a custom hash function is incorrect.

You'll also need to provide an equal predicate to make the above work properly.

#include <unordered_map>
#include <utility>

using namespace std;

class pairHash{
public:
    size_t operator()(const pair<int, int> &k) const{
        return k.first * 100 + k.second;
    }
};

struct pairEquals : binary_function<const pair<int,int>&, const pair<int,int>&, bool> {
  result_type operator()( first_argument_type lhs, second_argument_type rhs ) const
  {
    return (lhs.first == rhs.first) && (lhs.second == rhs.second);
  }
};     

int main()
{
  unordered_map<pair<int, int>, int, pairHash, pairEquals> myMap;

  myMap[make_pair(10,20)] = 100;
  myMap.insert( make_pair(make_pair(100,200), 1000) );
}

EDIT:
You don't need to define the equal predicate since operator== is defined for std::pair and it does exactly what I've done in pairEquals. You'll only need the pairEquals definition if you expect the comparison to be done differently.

Answer 3

If you are fine with using Boost, a cleaner solution is to rely on Boost's implementation of the hash function for pairs (which in fact does exactly what kerrek-sb explains in his answer). Therefore all you have to do is:

#include <unordered_map>
#include <boost/functional/hash.hpp>

using namespace std;
using namespace boost;

unordered_map<pair<int, int>, int, hash<pair<int, int>>> table;