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

Question

para soportar tipos de claves definidas por el usuario en std::unordered_set<Key> y std::unordered_map<Key, Value> uno tiene que proporcionar operator==(Key, Key) y un funtor de 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 simplemente std::unordered_set<X> con un hash predeterminado para el tipo X , me gusta para los tipos que vienen junto con el compilador y la biblioteca. Después de consultar

• C++ estándar Draft N3242 §20.8.12 [unord.hash] y §17.6.3.4 [hash.requirements],
• Boost.Unordered
• g ++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• diversos related question s en desbordamiento de pila

se ems 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 
}                    

apoyo compilador para C++ Dada 11 todavía es experimental --- Yo no probar Clang ---, estas son mis preguntas:

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

2. ¿Cuál de las versiones de std::hash<X>::operator(), si las hay, cumple con el estándar C++ 11?

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

Answer 1

Se le permite de forma expresa y anima a añadir especializaciones de espacio de nombres std *. La forma correcta (y básicamente solamente) para agregar una función hash es la siguiente: (. Otras especialidades populares que usted puede considerar el apoyo se std::less, std::equal_to y std::swap)

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

_{*), siempre y cuando uno de los tipos implicados es definido por el usuario, supongo.}

Answer 2

@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 de este tipo debe cumplir los mismos requisitos de "Hash" necesarios para el argumento de la segunda plantilla de std::unordered_set y así sucesivamente.A saber:

• Hash tipo H es un objeto de función, con al menos un argumento de tipo 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 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.

Answer 3

Mi apuesta sería en el argumento de plantilla de hash para el 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 podría muy bien ser una estática mundial función
• en el segundo caso, podría pasar que
  • the oldfashioned functor obj ect (struct Xhasher { size_t operator(const X&) const; };)
  • std::hash<X>()
  • cualquier expresión unen satisfacer la firma -