example - unordered_map c++

¿Cómo uso unordered_set?

Question

Esta pregunta ya tiene una respuesta aquí:

• Uso de C ++ 11 unordered_set en Visual C ++ y respuesta 1

Estoy tratando de definir un desordenado_set como este:

unordered_set<Point> m_Points;

Cuando lo compilo, me sale el siguiente error:

El estándar de C ++ no proporciona un hash para este tipo.

Point clase:

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

• ¿Cómo / dónde defino una función hash para Point ?
• ¿Cuál sería una buena función de hash para un punto 2D?

Answer 1

std::unordered_set requiere que escriba funciones hash para almacenar y encontrar sus propios tipos.

Los tipos base y muchos tipos en el std nombres std tienen tales funciones hash dentro de std::hash<Key> . Estas funciones siguen ciertas reglas :

1. Acepta un solo parámetro de tipo Key .

2. Devuelve un valor de tipo size_t que representa el valor hash del parámetro.

3. No lanza excepciones cuando es llamado.

4. Para dos parámetros k1 y k2 que son iguales, std::hash<Key>()(k1) == std::hash<Key>()(k2) .

5. Para dos parámetros diferentes k1 y k2 que no son iguales, la probabilidad de que std::hash<Key>()(k1) == std::hash<Key>()(k2) debe ser muy pequeña, acercándose a 1.0/std::numeric_limits<size_t>::max() .

Ahora que hemos eliminado las definiciones, pensemos en cuál sería una buena función hash para su estructura de puntos. Hubo una request que std::pair (que es muy similar a una estructura de puntos) obtuvo una función hash, pero, desafortunadamente, eso no se hizo en el estándar C ++ 11.

Pero tenemos suerte: SO es increíble y, por supuesto, básicamente ya puedes encontrar la respuesta . Tenga en cuenta que no tiene que hacer hash enteros, porque std::hash tiene una especialización para eso. Así que vamos a profundizar en nuestra función hash, de acuerdo con esta respuesta :

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

Y hemos terminado.