CODEWITHSUNDEEP
c++hashmaphashtable
Ming
Ming

Reputation: 497

C++ questions about hashtable

I am trying to write a program that uses hashtable in C++. The basic idea is that I have many data points, and I want to use a hashtable so that given a new point, I could know if it already exists or not. But there is some bug in it and I really don't how to fix it. (Error message : passing 'const Point' as 'this' argument of 'bool Point::operator==(const Point&)' discards qualifiers) Thanks in advance.

#include <iostream>
#include <unordered_map>
using namespace std;

class Point {
public:
    Point(int _x, int _y):x(_x), y(_y) {}
    bool operator==(const Point& lhs)
    { return this->x==lhs.x && this->y ==lhs.y; }
private:
    int x;
    int y;
};    
int main ()
{
    Point p1=Point(1,2);
    Point p2=Point(2,3);
    Point p3=Point(4,5);

    unordered_map<Point,bool> mymap = {{p1,true},{p2,true},{p3,true} };

    Point p4=Point(1,2);

    unordered_map<Point,bool>::const_iterator got = mymap.find(p4);

    if (got == mymap.end())
        cout << "not found";
    else
        cout << "already exists";

    cout<<endl;

    return 0;
}

Upvotes: 2

Views: 175

Answers (1)

Joe Z
Joe Z

Reputation: 17936

Declare operator== itself as const.

bool operator==(const Point& lhs) const   // add this 'const' at the end

The const qualifier on the operator's function tells the compiler that this will also be treated as const.

Once you've done that, you need to write a hashing function for class Point. You can do that one of two ways. One is to make a dedicating hashing class, and the other is to specialize std::hash<>. Both methods are described here: http://en.wikipedia.org/wiki/Unordered_associative_containers_%28C%2B%2B%29#Custom_hash_functions

Edit: Here's an example of providing a template specialization for hash<Point> that calls back to a hashing method in Point. Note that the hashing function I wrote is arbitrary—you should experiment and figure out a good hashing function for your purposes.

class Point {
public:
    Point(int _x, int _y):x(_x), y(_y) {}
    bool operator==(const Point& lhs) const
    { return this->x==lhs.x && this->y ==lhs.y; }

    size_t hash() const
    {
        return (x * 0xAAAA) ^ (y * 0x5555);
    }
private:
    int x;
    int y;
};    


namespace std
{
    template <> class hash<Point>
    {
      public:
        size_t operator()( const Point &p ) const
        {
            return p.hash();
        }
    };
}

The reason std::hash<Point>::operator() calls back to the Point::hash() method is that the members being hashed (x and y) are private to Point. There are other ways to handle the access control policies, but this seems fairly clean.

This particular protocol (hashing member in a class forwarded to by a specialization of std::hash<>) seems like it'd lend itself to an adaptor paradigm. I unfortunately don't have my copy of Josuttis' C++11 reference handy ( http://www.cppstdlib.com/ ) to see if I'm reinventing the wheel...

Upvotes: 3

Related Questions