That’s a bit unusual trip to side roads for me. I’ve been working with C++ for many years and considered myself pretty experienced with STL containers. I remembered (I thought) how to extend a class so. C++ is a language that does not forgive hiatuses. My approach to custom hash function was similar to what highest ranking answer in this stackoverflow answer is showing:

http://stackoverflow.com/questions/647967/how-to-extend-stdtr1hash-for-custom-types

First of all, it’s a bit outdated, because with introduction of C++11 tr1 namespace became obsolete. Secondly, to my shame, I was unable to make my example compile. So after some head scratching, I decided to go for even simpler solution. It may be not as beautiful as what you can find in C++ books, but it works. So here it is.

Our sample class looks like this:

struct Square
{
unsigned long long x;
unsigned long long y;

Square(unsigned long long _x, unsigned long long _y) : x(_x), y(_y) {};
};

To make class work with STL containers like map and set you need to implement a method returning a hash value of the object.

struct SquareHash
{
size_t operator() (const Square& square) const
{
return square.y * 1000 + square.y;
}
};

Besides that you either need to implement a function that compares two values. In case of regular std::map or std::set it should be “<” and in case of unordered_map and unordered_set – “==”. You can do it by implementing an operator< or operator== for operands of your custom class, but I found it even clearer syntactically to implement a class:

struct SquareEqual
{
bool operator() (const Square& lhs, const Square& rhs) const
{
return (lhs.x == rhs.x) && (lhs.y == rhs.y);
}
};

Just in case, look at unordered_map declaration:

template < class Key, // unordered_map::key_type
class T, // unordered_map::mapped_type
class Hash = hash, // unordered_map::hasher
class Pred = equal_to, // unordered_map::key_equal
class Alloc = allocator < pair<const Key,T> >// unordered_map::allocator_type
class unordered_map;

That’s it! Now you can declare an unordered_map:

unordered_set <Square, SquareHash, SquareEqual> visitedSquares;