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?

There's a pretty good description [here](https://en.wikipedia.org/wiki/Unordered_associative_containers_(C%2B%2B)#Custom_hash_functions). — Joachim Isaksson, Aug 07 '13 at 08:22
A lazy solution might be to derive your class from `std::pair`... — Kerrek SB, Aug 07 '13 at 08:23
can I define a hash function in class Point and pass that as a functor to unordered_set in second argument of template ? — brainydexter, Aug 07 '13 at 08:26
@brainydexter Yep - the 2nd argument is class Hash defaulted to std::hash — doctorlove, Aug 07 '13 at 08:31
@doctorlove Yea..what I'm trying to figure out is, if I specify a hash function in class Point, how can I specify it as a functor when i define unordered_set ? I am not sure if I can even do that. — brainydexter, Aug 07 '13 at 08:34

score 29 · Accepted Answer · edited May 23 '17 at 12:02

29

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.

edited May 23 '17 at 12:02

Community

1
1

answered Aug 07 '13 at 08:36

nikolas

8,707
9
50
70

Thanks for the elaborate reply and links. Can I specify the above hash object-function as a part of my Point class and use that as a functor to, when I define the unordered_set ? – brainydexter Aug 07 '13 at 08:43
also, what is the noexcept for ? Is that a standard keyword ? – brainydexter Aug 07 '13 at 08:45
1

noexcept is the promise we give to the compiler that there will be no exception while running the function. – sgun Aug 07 '13 at 08:50
Aha! Good to know, but it seems, dumb VS2012 hasn't learnt about it yet. – brainydexter Aug 07 '13 at 08:55
Also, I think the above hash function is incorrect...for point(2,4) and point(4,2) will be same => (51 + hash(2)) * (51 + hash(4)) – brainydexter Aug 07 '13 at 08:56
1

@brainydexter your parantheses are off. it's `(51+hash(2))*51 + hash(4)` which is not equal to `(51+hash(4))*51 + hash(2)` I've edited the answer to make this more clear. – nikolas Aug 07 '13 at 09:01
@brainydexter VS2012 doesn't have noexcept, which is annoying. A discussion about what it means happened here: http://stackoverflow.com/questions/18085383/c11-rvalue-reference-calling-copy-constructor-too – doctorlove Aug 07 '13 at 09:04
Furthermore, yes you can include your hash functor within your class as long as it is public and declare `std::unordered_set`. – nikolas Aug 07 '13 at 09:04
@nijansen VS2012 gives me "error C2923: 'std::unordered_set' : 'Point::Hash' is not a valid template type argument for parameter '_Hasher'" when I try to make it use a member function – doctorlove Aug 07 '13 at 09:05
@doctorlove No idea why, it works in gcc and I don't have MSVC; here is an [ideone sample](http://ideone.com/Zd57Cn) – nikolas Aug 07 '13 at 09:13
I got the signature wrong - I tried a member function, not a member struct. D'oh – doctorlove Aug 07 '13 at 09:14
2

@doctorlove You could technically declare a `size_t operator()(Point const &) noexcept` within `Point` and use `std::unordered_set` (given that Point has a default constructor, which it doesn't in the above example), but I find that very confusing ;) Also I want to remark that specializing `std::hash` is explicitly encouraged. – nikolas Aug 07 '13 at 09:24
Thanks for the insight nijansen. I was wondering which method is preferred over the other(specializing std::hash over class-member functor) – brainydexter Aug 07 '13 at 09:28
Specialise std::hash - it's the expected thing to do. – doctorlove Aug 07 '13 at 09:31
2

@nijansen Why is specializing std::hash preferred? I thought extending std namespace was a bad practice. – Draex_ Dec 31 '16 at 22:48

How do I use unordered_set?

1 Answers1

Linked