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

Aby obsługiwać typy kluczy zdefiniowane przez użytkownika w programie std::unordered_set<Key>i std::unordered_map<Key, Value> należy podać operator==(Key, Key)funktor skrótu:

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ślnym hashem dla typu X, tak jak w przypadku typów dostarczanych wraz z kompilatorem i biblioteką. Po konsultacji

• C ++ Standard Draft N3242 §20.8.12 [unord.hash] i §17.6.3.4 [hash.requirements],
• Wzmocnienie. Nieuporządkowane
• g ++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• różne powiązane pytania w Stack Overflow

wydaje się możliwe wyspecjalizowanie 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ę, że obsługa kompilatora dla C ++ 11 jest jeszcze eksperymentalna --- nie próbowałem Clang ---, oto moje pytania:

1. Czy dodanie takiej specjalizacji do przestrzeni nazw jest legalne std? Mam co do tego mieszane uczucia.

2. Która z std::hash<X>::operator()wersji, jeśli w ogóle, jest zgodna ze standardem C ++ 11?

3. Czy można to zrobić w sposób przenośny?

Wyraźnie wolno i zachęcamy do dodawania specjalizacji do przestrzeni nazw std*. Prawidłowy (i w zasadzie jedyny) sposób dodania funkcji skrótu jest następujący:

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

(Inne popularne specjalizacje, które można wziąć pod uwagę wsparcie są std::less, std::equal_toi std::swap.)

_{*) o ile jeden z zaangażowanych typów jest zdefiniowany przez użytkownika, jak przypuszczam.}

Mój zakład byłby oparty na argumencie szablonu Hash dla klas 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
}

Oczywiście

• hashX równie dobrze mógłby być globalną funkcją statyczną
• w drugim przypadku możesz to przekazać
  • staromodny obiekt funktora ( struct Xhasher { size_t operator(const X&) const; };)
  • std::hash<X>()
  • dowolne wyrażenie wiążące zgodne z podpisem -

@Kerrek SB omówił 1) i 3).

2) Mimo że g ++ i VC10 deklarują std::hash<T>::operator()różne podpisy, obie implementacje bibliotek są zgodne ze standardem.

Standard nie określa członków std::hash<T>. Mówi tylko, że każda taka specjalizacja musi spełniać te same wymagania „skrótu”, które są potrzebne dla drugiego argumentu szablonu std::unordered_seti tak dalej. Mianowicie:

• Typ skrótu Hto obiekt funkcji z co najmniej jednym typem argumentu Key.
• H jest możliwe do skopiowania.
• H jest zniszczalny.
• Jeśli hjest wyrażeniem typu Hlub const Hi kjest wyrażeniem typu, który można zamienić na (prawdopodobnie const) Key, to h(k)jest prawidłowym wyrażeniem typu size_t.
• Jeśli hjest wyrażeniem typu Hlub const Hi ujest lwartością typu Key, to h(u)jest poprawnym wyrażeniem z typem, size_tktóre nie zmienia się u.