93 votos

Cómo se especializan std::hash<Key>::operator() de tipo definido por el usuario en desordenada de los contenedores?

Para apoyar la clave definida por el usuario tipos en std::unordered_set<Key> y std::unordered_map<Key, Value> uno tiene que aportar operator==(Key, Key) y un hash functor:

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 para escribir sólo 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 la consulta

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 soporte para el compilador de C++11 es aún experimental---yo no trato Clang---, estas son mis preguntas:

  1. Es legal para añadir una especialización para el espacio de nombres std? Tengo sentimientos encontrados acerca de eso.

  2. Que de la std::hash<X>::operator() versiones, si alguna, es compatible con C++11 estándar?

  3. Es allí una manera portátil para hacerlo?

115voto

Kerrek SB Puntos 194696

Está expresamente permitido y alentado para agregar especializaciones para el espacio de nombres std*. La correcta (y, básicamente, la única) manera de añadir una función de hash es este:

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

(Entre otras especializaciones que usted podría considerar la posibilidad de apoyar son std::less, std::equal_to y std::swap.)

*) siempre y cuando uno de los tipos definidos por el usuario, supongo.

6voto

sehe Puntos 123151

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

#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 bien podría ser una función estática
  • en el segundo caso, podría pasar que
    • el anticuado functor objeto (struct Xhasher { size_t operator(const X&) const; };)
    • std::hash<X>()
    • cualquier enlazar la expresión de la satisfacción de la firma -

4voto

aschepler Puntos 23731

@Kerrek SB ha cubierto 1) y 3).

2) a pesar de g++ y VC10 declarar std::hash<T>::operator() con diferentes firmas, tanto de la biblioteca implementaciones son conformes a las normas.

El Estándar no especifica los miembros de std::hash<T>. Se dice que cada uno de esos especialización debe satisfacer la misma "Hash" de los requisitos necesarios para que el segundo argumento de plantilla de std::unordered_set y así sucesivamente. A saber:

  • Tipo de Hash H es un objeto de función, con al menos un tipo de argumento Key.
  • H es copia edificable.
  • H es destructible.
  • Si h es una expresión de tipo H o const Hy k es una expresión de un tipo convertible (posiblemente const) Key, a continuación, h(k) es una expresión válida con el tipo size_t.
  • Si h es una expresión de tipo H o const Hy u es un lvalue de tipo Key, a continuación, h(u) es una expresión válida con el tipo size_t que no modifica u.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X