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.