2

C++ でハッシュテーブルを使用するプログラムを作成しようとしています。基本的な考え方は、多くのデータ ポイントがあり、新しいポイントが与えられたときに、それが既に存在するかどうかを知ることができるようにハッシュ テーブルを使用したいということです。しかし、そこにはいくつかのバグがあり、それを修正する方法は本当にありません。(エラーメッセージ: 'bool Point::operator==(const Point&)' の 'this' 引数として 'const Point' を渡すと修飾子が破棄されます) よろしくお願いします。

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

1 に答える 1

3

として宣言operator==しますconst。

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

演算子の関数の修飾子は、としても扱われることをconstコンパイラに伝えます。thisconst

それが終わったら、 のハッシュ関数を書く必要がありますclass Point。2 つの方法のいずれかを行うことができます。1 つは専用のハッシュ クラスを作成することで、もう 1 つは 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です。アクセス制御ポリシーを処理する方法は他にもありますが、これはかなりきれいに思えます。

この特定のプロトコル (の特殊化によって転送されるクラスのハッシュ メンバーstd::hash<>) は、アダプター パラダイムに役立つようです。残念ながら、車輪を再発明しているかどうかを確認するための Josuttis の C++11 リファレンス ( http://www.cppstdlib.com/ ) のコピーが手元にありません...

于 2013-11-04T05:50:15.107 に答える