Cómo usar unordered_set con tipos personalizados?

Question

¿Es necesario que cree mi propia función hash para tipos personalizados? ¿No hay valores predeterminados que pueda usar con unordered_set?

Answer 1

La biblioteca estándar contiene especializaciones de std::hash<T> para los tipos fundamentales, para los punteros y para std::string (o más bien, para todas las especializaciones de std::basic_string).

Por desgracia, la biblioteca no no contener la siguiente función vital nueva a partir de edad combinación, que sin embargo es parte de Boost, y que se debe copiar en su código:

template <class T> 
inline void hash_combine(std::size_t & seed, const T & v) 
{ 
    std::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
} 

Con esta función, puede hash pares, tuplas, matrices y cualquier tipo de rango de elementos que son ellos mismos hashable. Explore las fuentes de Boost para obtener muchos ejemplos e implementaciones útiles. Y, obviamente, puede usar esta función para crear una función hash para sus propios tipos. Por ejemplo, aquí hay un par de hash:

template<typename S, typename T> struct pair_hash<std::pair<S, T>> 
{ 
    inline std::size_t operator()(const std::pair<S, T> & v) const 
    { 
     std::size_t seed = 0; 
     hash_combine(seed, v.first); 
     hash_combine(seed, v.second); 
     return seed; 
    } 
}; 

Por favor, tenga en cuenta, sin embargo, que la combinación de hash no produce buenos valores hash. Los resultados tienen cualidades estadísticas muy pobres (por ejemplo, es muy fácil crear colisiones hash). Un buen hashing necesita poder ver todos los bits de entrada sin procesar, y no se puede factorizar mediante hashes parciales. (Es por eso que no hay una solución mejor en la biblioteca estándar actual, nadie ha podido encontrar un diseño satisfactorio).

Answer 2

Sí, tendrá que escribir su propia función hash. Esto no es tan malo como parece: si su clase tiene algún miembro hashable que sabe que será razonablemente único, puede simplemente devolver el hash de ese miembro.

Puede proporcionar este hash especializándose std::hash, o pasando explícitamente la clase hash como parámetro de plantilla.