Как использовать unordered_set?

Я пытаюсь определить unordered_set следующим образом:

unordered_set<Point> m_Points;

Когда я скомпилирую его, я получаю следующую ошибку:

Стандарт С++ не предоставляет хэш для этого типа.

Класс 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);
        }
};
  • Как/где определить хэш-функцию для Точка?
  • Что было бы хорошей хэш-функцией для двумерной точки?

Ответы

Ответ 1

std::unordered_set требуется написать хэш-функции для хранения и поиска ваших собственных типов.

Базовые типы и многие типы в пространстве имен std имеют такие хеш-функции в пределах std::hash<Key>. Эти функции следуют определенные правила:

  • Принимает единственный параметр типа Key.

  • Возвращает значение типа size_t, которое представляет хеш-значение параметра.

  • Не вызывает исключения при вызове.

  • Для двух параметров k1 и k2, которые равны, std::hash<Key>()(k1) == std::hash<Key>()(k2).

  • Для двух разных параметров k1 и k2, которые не равны, вероятность того, что std::hash<Key>()(k1) == std::hash<Key>()(k2) должна быть очень малой, приближается к 1.0/std::numeric_limits<size_t>::max().

Теперь, когда мы определили определения, давайте подумаем о том, что будет хорошей хэш-функцией для вашей точечной структуры. Был запрос, который std::pair (который очень похож на точечную структуру) получил хеш-функцию, но, к сожалению, это не превратите его в стандарт С++ 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())
            );
        }
    };
}

И мы закончили.