Customizing TR1 unordered_map Hashing and Equality Functions

A common problem people run into when using the C++ std::tr1::unordered_map or std::tr1::unordered_set is when they want to use a custom or aggregate type as the key in the hash table, and aren’t sure how to do it.

There isn’t really any official documentation about this; you can find some forum and StackOverflow discussions which may help; but I’ll run through a detailed example here too. Let’s start by taking a look at how the unordered_map class is defined:

template<class Key,
         class T,
         class Hash = hash<Key>,
         class Pred = std::equal_to<Key>,
         class Alloc = std::allocator<std::pair<const Key, T> > >
  class unordered_map;

The templated types in the class are:

• class Key: key type (duh)
• class T: value type
• class Hash: hash function for type Key
• class Pred: an equality predicate for type Key
• class Alloc: the memory allocator for <Key, T>

The function represented in class Hash produces a hash value given a reference to type Key. This is the value that the map will use to locate the appropriate bucket to insert the corresponding value. The function represented by Pred is a predicate; it returns true if the values (as opposed to hash values) of Key types are equal. If the Key type is a class with operator== () defined, then defining a separate Pred function won’t be an issue.

Changing the Hash and Pred types is easy, but non-obvious. The most common reasons for this are either using a custom type as the key for the hash table, as I mentioned above, or for using a custom hash function to achieve better performance from the container.

Let’s say we have the following setup:

typedef struct
{
  uint32_t a;
  double x;
  double y;
} AggregateKey;

{ ... }

AggregateKey k;

{...}

std::tr1::unordered_map<AggregateKey, int> M;
M[k] = 1;

{...}

Attempting to compile this will generate a ton of error output. Depending on the situation, it’ll complain about Pred with something like

error: no match for ‘operator==’ in ‘__x == __y’

or about Hash with

undefined reference to `std::tr1::hash<AggregateKey>::operator()(AggregateKey) const'

Fix the issue by defining the following functors:

typedef struct
{
  long operator() (const AggregateKey &k) const { return my_hash_fnct (k); }
} AggregateKeyHash;

typedef struct
{
  bool operator() (const AggregateKey &x, const AggregateKey &y) const { return my_eq_test (x, y); }
} AggregateKeyEq;

AggregateKey k;

{...}

// Now, hash value generation and equality testing are
// defined for the AggregateKeyHash type, so declare the
// map using the functors above in the object's template list
std::tr1::unordered_map<AggregateKey, int, AggregateKeyHash, AggregateKeyEq> M;
M[k] = 1;

{...}

The same logic applies to the std::tr1::unordered_set, with the exception that its template list doesn’t include a class T value type. Also note that you can grab the any map’s default hash function and equality predicate at any time from the object:

std::tr1::unordered_map<int, int> M;

const std::tr1::unordered_map<int, int>::hasher &hfn = M.hash_function ();
const std::tr1::unordered_map<int, int>::key_equal &eqfn = M.key_eq ();

long h = hfn (123);
bool b = eqfn (1, 2);

Advertisement