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

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) y un funtor 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. Previa 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 que el soporte del compilador para C++11 aún es experimental - - - No intenté Clang - - -, estas son mis preguntas:

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

  2. Cuál de las versiones de std::hash<X>::operator(), en su caso, es compatible con C++11 estándar?

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

Author: Community, 2011-11-17
Source

3 answers

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

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ías considerar apoyar son std::less, std::equal_to y std::swap.)

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

 110
Author: Kerrek SB,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-16 20:14:14

Mi apuesta estaría en el argumento de la plantilla Hash para 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 también podría ser una función estática global
  • en el segundo caso, podrías pasar eso
    • el objeto funtor oldfashioned(struct Xhasher { size_t operator(const X&) const; };)
    • std::hash<X>()
    • cualquier expresión de enlace que satisfaga la firma -
 6
Author: sehe,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-16 20:36:29

@Kerrek SB ha cubierto 1) y 3).

2) Aunque g++ y VC10 declaran std::hash<T>::operator() con diferentes firmas, ambas implementaciones de bibliotecas son compatibles con el estándar.

La Norma no especifica los miembros de std::hash<T>. Solo dice que cada especialización debe satisfacer los mismos requisitos de" Hash " necesarios para el segundo argumento de la plantilla de std::unordered_set y así sucesivamente. A saber:

  • Hash type H es un objeto de función, con al menos un tipo de argumento Key.
  • H es una copia construible.
  • {[3] } es destructible.
  • Si h es una expresión de tipo H o const H, y k es una expresión de un tipo convertible (posiblemente const) Key, entonces h(k) es una expresión válida con el tipo size_t.
  • Si h es una expresión de tipo H o const H, y u es un lvalue de tipo Key, entonces h(u) es una expresión válida con el tipo size_t que no modifica u.
 4
Author: aschepler,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-16 20:24:50