关于哈希表的 C++ 问题

Question

我正在尝试编写一个使用 C++ 中的哈希表的程序。基本思想是我有很多数据点，我想使用哈希表，以便给定一个新点，我可以知道它是否已经存在。但它有一些错误，我真的不知道如何修复它。 (错误消息:将“const Point”作为“bool Point::operator==(const Point&)”的“this”参数传递会丢弃限定符)提前致谢。

#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;
}

Answer 1

声明operator==本身为 const .

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

const运算符函数上的限定符告诉编译器 this也将被视为 const .

完成此操作后，您需要为 class Point 编写一个哈希函数。 。您可以通过以下两种方式之一进行操作。一是创建一个专用的哈希类，二是专门化 std::hash<>。此处描述了两种方法:http://en.wikipedia.org/wiki/Unordered_associative_containers_%28C%2B%2B%29#Custom_hash_functions

编辑:这是为 hash<Point> 提供模板特化的示例回调 Point 中的哈希方法。请注意，我编写的哈希函数是任意的 - 您应该尝试并找出适合您目的的良好哈希函数。

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

原因std::hash<Point>::operator()回拨Point::hash()方法是被散列的成员( x 和 y )是 private至Point 。还有其他方法来处理访问控制策略，但这看起来相当干净。

这个特定的协议(protocol)(通过 std::hash<> 的专门化转发到的类中的散列成员)似乎适合适配器范例。不幸的是，我手边没有 Josuttis 的 C++11 引用文献 ( http://www.cppstdlib.com/ ) 来看看我是否在重新发明轮子......