How do I use unordered_set?

c++, set, stl, unordered-set

Solution

`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:

Accepts a single parameter of type `Key`.

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

Does not throw exceptions when called.

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

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.

Problem

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?

Original source

Related problems