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);
}
};
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.