hashing c++ code

C++ 11: ¿Existen motivos por los cuales algunos tipos regulares no deberían tener a `std:: hash` especializado?

Question

Con un Tipo Regular, me refiero a la definición de Stepanov en Elementos de Programación , básicamente, que existe el concepto de igualdad y que los objetos que son copias de otros se comparan de igual a igual.

Entonces, cuando tiene un Tipo T Regular y la relación de igualdad es transitiva ( a == b && b == c => a == c ), puede definir una función hash ( no trivial ) que sea consistente con la definición de igualdad ( a == b => h (a) == h (b) ). Siempre.

Pero el estándar no incluye muchas especializaciones std::hash . Por ejemplo, std::complex no tiene uno, ni ninguno de los contenedores, con las notables excepciones de vector<bool> y bitset .

Así que me pregunto cuál es el principio de diseño aquí.

O bien, pregunte de manera diferente: ¿Hay razones para no proporcionar especializaciones std::hash para sus propios tipos, siempre que sean regulares y la igualdad sea transitiva?

Answer 1

Sí.

Cuando un tipo tiene las siguientes dos propiedades, no creo que std::hash definir std::hash :

• No existe una manera eficiente de crear de manera consistente un hash de calidad que cubra todos los datos utilizados para describir la igualdad.

• No hay una forma eficiente y / o intuitiva de seleccionar un subconjunto consistente de datos para el hash.

Answer 2

Proporcionar especialización para los propios tipos no tiene sentido, si son clases de plantilla, ya que la función hash (con una alta probabilidad muy alta) también depende de los tipos de parámetros de la plantilla, que son desconocidos.

Si no hay parámetros de plantilla, o los parámetros de plantilla están restringidos a ciertos tipos

// provide no implementation to restrict all types
template<typename T> container;

// int is allowed
template<> container<int> {
    ...
}

// double is allowed
template<> container<double> {
    ...
}

es posible proporcionar una especialización de std::hash , ya que las implementaciones de las clases (o las clases de plantilla instanciadas) son conocidas, como lo es para el vector<bool> contrario al complex<T> .