¿Cómo especializar std :: hash <Key> :: operator () para el tipo definido por el usuario en contenedores desordenados?

101

Para admitir tipos de clave definidos por el usuario en std::unordered_set<Key>y std::unordered_map<Key, Value> uno tiene que proporcionar operator==(Key, Key)un functor hash:

struct X { int id; /* ... */ };
bool operator==(X a, X b) { return a.id == b.id; }

struct MyHash {
  size_t operator()(const X& x) const { return std::hash<int>()(x.id); }
};

std::unordered_set<X, MyHash> s;

Sería más conveniente escribir solo std::unordered_set<X> con un hash predeterminado para el tipo X, como para los tipos que vienen junto con el compilador y la biblioteca. Después de consultar

parece posible especializarse std::hash<X>::operator():

namespace std { // argh!
  template <>
  inline size_t 
  hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } // works for MS VC10, but not for g++
  // or
  // hash<X>::operator()(X x) const { return hash<int>()(x.id); }     // works for g++ 4.7, but not for VC10 
}                                                                             

Dado que el soporte del compilador para C ++ 11 aún es experimental --- no probé Clang ---, estas son mis preguntas:

  1. ¿Es legal agregar tal especialización al espacio de nombres std? Tengo sentimientos encontrados respecto de eso.

  2. ¿Cuál de las std::hash<X>::operator()versiones, si alguna, es compatible con el estándar C ++ 11?

  3. ¿Existe una forma portátil de hacerlo?

René Richter
fuente
Con gcc 4.7.2, tuve que proporcionar un globaloperator==(const Key, const Key)
Victor Lyuboslavsky
Tenga en cuenta que la guía de estilo de Google desaconseja la especialización de std::hash(a diferencia de otras cosas en el stdespacio de nombres) ; Tómelo con un grano de sal.
Franklin Yu

Respuestas:

128

Se le permite y se le anima expresamente a agregar especializaciones al espacio de nombres std*. La forma correcta (y básicamente única) de agregar una función hash es esta:

namespace std {
  template <> struct hash<Foo>
  {
    size_t operator()(const Foo & x) const
    {
      /* your code here, e.g. "return hash<int>()(x.value);" */
    }
  };
}

(Otras especializaciones populares que podría considerar apoyar son std::less, std::equal_toy std::swap).

*) siempre que uno de los tipos involucrados esté definido por el usuario, supongo.

Kerrek SB
fuente
3
si bien esto es posible, ¿recomendaría en general hacerlo de esta manera? Preferiría la creación de instancias en su unorder_map<eltype, hash, equality>lugar, para evitar arruinar el día de alguien con negocios divertidos de ADL. ( Edite el consejo de Pete Becker sobre este tema )
vea el
2
@sehe: Si tiene un functor hash por ahí que sea construible por defecto, tal vez, pero ¿por qué? (La igualdad es más fácil, ya que solo implementaría member- operator==). Mi filosofía general es que si la función es natural y esencialmente la única "correcta" (como la comparación de pares lexicográficos), entonces la agrego std. Si es algo peculiar (como una comparación de pares desordenada), lo hago específico para un tipo de contenedor.
Kerrek SB
3
No estoy en desacuerdo, pero ¿en qué parte del estándar se nos permite y se nos alienta a agregar especializaciones a la norma?
razeh
3
@Kerrek, estoy de acuerdo, pero esperaba una referencia de capítulo y versículo a un lugar en el estándar. Encontré la redacción que permite la inyección en 17.6.4.2.1 donde dice que no está permitida "a menos que se especifique lo contrario", pero no he podido encontrar la parte "especificada de otra manera" en medio de la especificación de más de 4000 páginas.
razeh
3
@razeh aquí puede leer "Un programa puede agregar una especialización de plantilla para cualquier plantilla de biblioteca estándar al espacio de nombres std solo si la declaración depende de un tipo definido por el usuario y la especialización cumple con los requisitos de biblioteca estándar para la plantilla original y no está explícitamente prohibido . ". Entonces esta solución está bien.
Marek R
7

Mi apuesta estaría en el argumento de la plantilla Hash para las clases unordered_map / unorder_set / ...:

#include <unordered_set>
#include <functional>

struct X 
{
    int x, y;
    std::size_t gethash() const { return (x*39)^y; }
};

typedef std::unordered_set<X, std::size_t(*)(const X&)> Xunset;
typedef std::unordered_set<X, std::function<std::size_t(const X&)> > Xunset2;

int main()
{
    auto hashX = [](const X&x) { return x.gethash(); };

    Xunset  my_set (0, hashX);
    Xunset2 my_set2(0, hashX); // if you prefer a more flexible set typedef
}

Por supuesto

  • hashX también podría ser una función estática global
  • en el segundo caso, podrías pasar eso
    • el objeto functor anticuado ( struct Xhasher { size_t operator(const X&) const; };)
    • std::hash<X>()
    • cualquier expresión de enlace que satisfaga la firma -
sehe
fuente
Aprecio que pueda escribir algo que no tenga un constructor predeterminado, pero siempre encuentro que requerir que cada construcción de mapa recuerde el argumento adicional es un poco pesado, demasiado pesado para mi gusto. Estoy de acuerdo con un argumento de plantilla explícito, aunque la especialización std::hashsigue siendo la mejor salida :-)
Kerrek SB
tipos definidos por el usuario al rescate :-) Más en serio, espero que les peguemos en las muñecas ya en la etapa donde su clase contiene un char*!
Kerrek SB
Hmm ... ¿tienes un ejemplo de cómo una hashespecialización interfiere a través de ADL? Quiero decir, es completamente plausible, pero me cuesta encontrar un caso problemático.
Kerrek SB
Todo es diversión y juegos hasta que necesitas un std::unordered_map<Whatever, Xunset>y no funciona porque tu Xunsettipo de hasher no es constructivo predeterminado.
Brian Gordon
4

@Kerrek SB ha cubierto 1) y 3).

2) Aunque g ++ y VC10 declaran std::hash<T>::operator() con firmas diferentes, ambas implementaciones de bibliotecas cumplen con los estándares.

La Norma no especifica los miembros de std::hash<T>. Simplemente dice que cada una de estas especializaciones debe satisfacer los mismos requisitos de "Hash" necesarios para el segundo argumento de plantilla de std::unordered_sety así sucesivamente. A saber:

  • El tipo hash Hes un objeto de función, con al menos un tipo de argumento Key.
  • H es copia construible.
  • H es destructible.
  • Si hes una expresión de tipo Ho const H, y kes una expresión de un tipo convertible a (posiblemente const) Key, entonces h(k)es una expresión válida con tiposize_t .
  • Si hes una expresión de tipo Ho const H, y ues un valor de tipo Key, entonces h(u)es una expresión válida con tipo size_tque no modifica u.
aschepler
fuente
No, ninguna de las implementaciones cumple con los estándares, ya que intentan especializarse std::hash<X>::operator()más que std::hash<X>como un todo, y la firma de std::hash<T>::operator()está definida por la implementación.
ildjarn
@ildjarn: Aclarado: estaba hablando de las implementaciones de la biblioteca, no de los intentos de especialización. No estoy seguro de qué pretendía preguntar exactamente el OP.
aschepler