24

次のように unordered_set を定義しようとしています。

unordered_set<Point> m_Points;

コンパイルすると、次のエラーが発生します。

C++ 標準は、この型のハッシュを提供していません。

クラス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);
        }
};
  • Pointのハッシュ関数を定義する方法/場所は?
  • 2D ポイントの適切なハッシュ関数は何でしょうか?
4

1 に答える 1

27

std::unordered_set独自の型を格納および検索するハッシュ関数を作成する必要があります。

名前空間内の基本型と多くの型は、std内にそのようなハッシュ関数を持っていますstd::hash<Key>。これらの関数は特定の規則に従います。

  1. type の 1 つのパラメーターを受け入れますKey。

  2. size_tパラメータのハッシュ値を表す型の値を返します。

  3. 呼び出されたときに例外をスローしません。

  4. 2 つのパラメーターk1とk2が等しい場合、std::hash<Key>()(k1) == std::hash<Key>()(k2).

  5. 等しくない2 つの異なるパラメーターk1の場合、確率は非常に小さくなり、 に近づきます。k2std::hash<Key>()(k1) == std::hash<Key>()(k2)1.0/std::numeric_limits<size_t>::max()

定義が終わったので、ポイント構造に適したハッシュ関数について考えてみましょう。(ポイント構造に非常に似ている) ハッシュ関数を取得する要求がありましたstd::pairが、残念ながら、C++11 標準にはなりませんでした。

しかし、私たちは幸運です: SO は素晴らしいですし、もちろん、基本的にはすでに答えを見つけることができます. std::hashすでに特殊化されているため、整数を自分でハッシュする必要はないことに注意してください。それでは、この回答に従って、ハッシュ関数を掘り下げましょう。

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

これで完了です。

于 2013-08-07T08:36:12.730 に答える