Jak specjalizować std :: hash <Key> :: operator() dla typu zdefiniowanego przez użytkownika w nieuporządkowanych kontenerach?

Question

Wspieranie zdefiniowane przez użytkownika kluczowe typy w std::unordered_set<Key> i std::unordered_map<Key, Value> jeden musi zapewnić operator==(Key, Key) a funktor 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; 

Byłoby wygodniej pisać tylko std::unordered_set<X> z domyślnej hash na typ X , podobne do typów pochodzących z kompilatora i biblioteki. po konsultacji

• C++ standardowe Draft N3242 §20.8.12 [unord.hash] i §17.6.3.4 [hash.requirements]
• Boost.Unordered
• g ++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• różne related question s w przepełnieniu stosu

it se EMS można specjalizować 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 
}                    

Biorąc pod uwagę wsparcie dla C++ kompilator 11 jest jeszcze eksperymentalny --- ja nie spróbować dzyń --- są to moje pytania:

1. Czy go prawnych, aby dodać taką specjalizację do przestrzeni nazw std? Mam mieszane uczucia na ten temat.

2. Która z wersji, jeśli jest, jest zgodna ze standardem C++ 11?

3. Czy istnieje przenośny sposób na zrobienie tego?

Answer 1

Jesteś wyraźnie dozwolone i zachęcał, aby dodać specjalizacje do przestrzeni nazw std *. Prawidłowe (iw zasadzie tylko) sposób na dodanie funkcji skrótu to: (. Inne popularne specjalizacje, które można rozważyć wsparcie są std::less, std::equal_to i 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);" */ 
    } 
    }; 
} 

_{*) tak długo, jak jeden z zaangażowanych typów jest przypuszczalnie zdefiniowany przez użytkownika.}

Answer 2

@Kerrek SB obejmuje 1) i 3).

2) Mimo że g ++ i VC10 deklarują std::hash<T>::operator() z różnymi sygnaturami, obydwie implementacje bibliotek są zgodne ze standardami.

Standard nie określa członków std::hash<T>. Po prostu mówi, że każda taka specjalizacja musi spełniać takie same wymagania "Hash", jakie są wymagane dla drugiego argumentu szablonu: std::unordered_set i tak dalej.Mianowicie:

• Hash typ H to obiekt funkcji, z co najmniej jednego rodzaju argumentu Key.
• H jest kopiowalna.
• H jest zniszczalny.
• Jeśli h jest wyrazem typu H lub const H i k jest wyrazem typu zamienny do (ewentualnie const) Key, następnie h(k) jest ważne wyrażeniem typu size_t.
• Jeśli h jest wyrazem typu H lub const H i u jest lwartością typu Key, następnie h(u) jest ważne wyrażeniem typu size_t który nie zmienia u.

Answer 3

Mój zakład byłby na argumencie szablonu Hash dla unordered_map/unorder_set/... zajęcia:

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

Oczywiście

• hashX może równie dobrze być globalny statyczny funkcja
• w drugim przypadku możesz przekazać to
  • oldfashioned functor obj ect (struct Xhasher { size_t operator(const X&) const; };)
  • std::hash<X>()
  • dowolne wyrażenie wiążą spełniających podpis -