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

Question

Я пытаюсь определить 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-точки?

Answer 1

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

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

1. Принимает один параметр типа Key,

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

3. Не выдает исключений при вызове.

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

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

Теперь, когда у нас нет определений, давайте подумаем о том, что будет хорошей хеш-функцией для вашей точечной структуры. Был запрос, который std::pair (который очень похож на структуру точек) получил хеш-функцию, но, к сожалению, это не вошло в стандарт C++11.

Но нам повезло: ТАК здорово, и, конечно, вы уже можете найти ответ. Обратите внимание, что вам не нужно хешировать целые числа самостоятельно, потому что 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())
            );
        }
    };
}

И мы сделали.