How do I use unordered_set?

Question

I am trying to define an unordered_set like this:

unordered_set<Point> m_Points;

When I compile it, I get the following error:

The C++ Standard doesn't provide a hash for this type.

Class Point:

class Point{
    private:
        int x, y;
    public:
        Point(int a_x, int a_y)
            : x(a_x), y(a_y)
        {}
        ~Point(){}

        int getX()const { return x; }
        int getY()const { return y; }

        bool operator == (const Point& rhs) const{
            return x == rhs.x && y == rhs.y;
        }

        bool operator != (const Point& rhs) const{
            return !(*this == rhs);
        }
};

• How/where do I define a hash function for Point?
• What would be a good hash function for a 2D point?

Answer 1

std::unordered_set requires you to write hash functions to store and find your own types.

Base types and many types in the std namespace do have such hash functions within std::hash<Key>. These functions follow certain rules:

1. Accepts a single parameter of type Key.

2. Returns a value of type size_t that represents the hash value of the parameter.

3. Does not throw exceptions when called.

4. For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2).

5. For two different parameters k1 and k2 that are not equal, the probability that std::hash<Key>()(k1) == std::hash<Key>()(k2) should be very small, approaching 1.0/std::numeric_limits<size_t>::max().

Now that we got the definitions out of the way, let's think about what would be a good hash function for your point structure. There was a request that std::pair (which is very similar to a point structure) got a hash function, but, unfortunately, that did not make it into the C++11 standard.

But we are lucky: SO is awesome and, of course, you can basically already find the answer. Note that you do not have to hash integers yourself, because std::hash has a specialization for that already. So let's dig into our hash function, according to this answer:

namespace std
{
    template <>
    struct hash<Point>
    {
        size_t operator()(Point const & x) const noexcept
        {
            return (
                (51 + std::hash<int>()(x.getX())) * 51
                + std::hash<int>()(x.getY())
            );
        }
    };
}

And we are done.