By brainydexter


2013-08-07 08:17:38 8 Comments

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?

1 comments

@nijansen 2013-08-07 08:36:12

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.

@brainydexter 2013-08-07 08:43:48

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 2013-08-07 08:45:11

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

@sgun 2013-08-07 08:50:37

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

@brainydexter 2013-08-07 08:55:15

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

@brainydexter 2013-08-07 08:56:36

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

@nijansen 2013-08-07 09:01:51

@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.

@doctorlove 2013-08-07 09:04:00

@brainydexter VS2012 doesn't have noexcept, which is annoying. A discussion about what it means happened here: stackoverflow.com/questions/18085383/…

@nijansen 2013-08-07 09:04:01

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>.

@doctorlove 2013-08-07 09:05:56

@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

@nijansen 2013-08-07 09:13:40

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

@doctorlove 2013-08-07 09:14:36

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

@nijansen 2013-08-07 09:24:53

@doctorlove 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.

@brainydexter 2013-08-07 09:28:42

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

@doctorlove 2013-08-07 09:31:24

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

@Draex_ 2016-12-31 22:48:44

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

Related Questions

Sponsored Content

29 Answered Questions

[SOLVED] How do you set, clear, and toggle a single bit?

17 Answered Questions

[SOLVED] What should main() return in C and C++?

79 Answered Questions

[SOLVED] How do I iterate over the words of a string?

  • 2008-10-25 08:58:21
  • Ashwin Nanjappa
  • 2187582 View
  • 3004 Score
  • 79 Answer
  • Tags:   c++ string split

11 Answered Questions

[SOLVED] Static constant string (class member)

5 Answered Questions

2 Answered Questions

[SOLVED] Why can't I store my objects in an unordered_set?

2 Answered Questions

[SOLVED] Access to custom objects in unordered_set

  • 2016-03-17 08:44:13
  • qloq
  • 772 View
  • 1 Score
  • 2 Answer
  • Tags:   c++ stl

4 Answered Questions

[SOLVED] How to use unordered_set in STL?

  • 2009-11-30 03:22:14
  • user855
  • 10175 View
  • 5 Score
  • 4 Answer
  • Tags:   c++ stl

2 Answered Questions

[SOLVED] std::unordered_set<Foo> as member of class Foo

3 Answered Questions

Sponsored Content