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
- 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:
¿Es legal agregar tal especialización al espacio de nombres
std
? Tengo sentimientos encontrados respecto de eso.¿Cuál de las versiones
std::hash<X>::operator()
, si hay alguna, cumple con el estándar C ++ 11?¿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 argumentoKey
. -
H
es copiable. -
H
es destructible. - Si
h
es una expresión de tipoH
oconst H
, yk
es una expresión de un tipo convertible a (posiblementeconst
)Key
, entoncesh(k)
es una expresión válida con tiposize_t
. - Si
h
es una expresión de tipoH
oconst H
, yu
es un lvalue de tipoKey
, entoncesh(u)
es una expresión válida con tiposize_t
que no modificau
.
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 -
- el objeto functor