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

unordered_map c++ example

Question

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

• Proyecto estándar de C ++ N3242 §20.8.12 [unord.hash] y §17.6.3.4 [requisitos de hash],
• Boost.Unordered
• g ++ include/c++/4.7.0/bits/functional_hash.h
• VC10 include/xfunctional
• varias preguntas relacionadas en Stack Overflow

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?

Answer 1

@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 .

Answer 2

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.}

Answer 3

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 -