How do I use unordered_set? [duplicate]

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?

Alwyn

There's a pretty good description here. – Inseminate

A lazy solution might be to derive your class from std::pair<int, int>... – Hellbender

can I define a hash function in class Point and pass that as a functor to unordered_set in second argument of template ? – Alwyn

@Alwyn Yep - the 2nd argument is class Hash defaulted to std::hash<Key> – Bomarc

@Bomarc 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. – Alwyn

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.

Olivo

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 ? – Alwyn

also, what is the noexcept for ? Is that a standard keyword ? – Alwyn

noexcept is the promise we give to the compiler that there will be no exception while running the function. – Glasgow

Aha! Good to know, but it seems, dumb VS2012 hasn't learnt about it yet. – Alwyn

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)) – Alwyn

@Alwyn 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. – Olivo

@Alwyn VS2012 doesn't have noexcept, which is annoying. A discussion about what it means happened here: #18085883 – Bomarc

Furthermore, yes you can include your hash functor within your class as long as it is public and declare std::unordered_set<Point, Point::hash>. – Olivo

@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 – Bomarc

@Bomarc No idea why, it works in gcc and I don't have MSVC; here is an ideone sample – Olivo

I got the signature wrong - I tried a member function, not a member struct. D'oh – Bomarc

@Bomarc You could technically declare a size_t operator()(Point const &) noexcept within Point and use std::unordered_set<Point, Point> (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. – Olivo

Thanks for the insight nijansen. I was wondering which method is preferred over the other(specializing std::hash over class-member functor) – Alwyn

Specialise std::hash - it's the expected thing to do. – Bomarc

@nijansen Why is specializing std::hash preferred? I thought extending std namespace was a bad practice. – Consumable