unordered_set unordered_map example c++ hash c++11 unordered-map unordered-set

c++ - unordered_map - ¿Cómo especializar std:: hash<Key>:: operator() para tipo definido por el usuario en contenedores no ordenados?



unordered_map c++ example (3)

Para admitir los tipos de clave definidos por el usuario en std::unordered_set<Key> y std::unordered_map<Key, Value> uno debe proporcionar 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 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 especializar 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 versiones std::hash<X>::operator() , si hay alguna, cumple con el estándar C ++ 11?

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


@Kerrek SB ha cubierto 1) y 3).

2) Aunque g ++ y VC10 declaran std::hash<T>::operator() con diferentes firmas, ambas implementaciones de la biblioteca cumplen con las normas.

El estándar no especifica los miembros de std::hash<T> . Simplemente dice que cada especialización debe cumplir los mismos requisitos de "Hash" necesarios para el segundo argumento de la plantilla de std::unordered_set y así sucesivamente. A saber:

  • Hash tipo H es un objeto de función, con al menos un tipo de argumento Key .
  • H es copiable.
  • H es destructible.
  • Si h es una expresión de tipo H o const H , y k es una expresión de un tipo convertible a (posiblemente const ) Key , entonces h(k) es una expresión válida con 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 tipo size_t que no modifica u .

Está expresamente permitido y animado 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 son std::less , std::equal_to y std::swap ).

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


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