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

101

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

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?

René Richter
źródło
Z gcc 4.7.2, musiałem dostarczyć globalnyoperator==(const Key, const Key)
Victor Lyuboslavsky
Zauważ, że specjalizacja std::hash(w przeciwieństwie do innych rzeczy w stdprzestrzeni nazw) jest odradzana w przewodniku stylistycznym Google ; Dodaj szczyptę soli.
Franklin Yu

Odpowiedzi:

128

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.

Kerrek SB
źródło
3
chociaż jest to możliwe, czy ogólnie zalecałbyś zrobienie tego w ten sposób? Wolałbym unorder_map<eltype, hash, equality>zamiast tego tworzenie instancji , aby nie zepsuć komuś dnia zabawnym biznesem ADL. ( Edycja rada Pete Beckera na ten temat )
sehe
2
@sehe: Jeśli masz funktor haszujący, który może być domyślnie konstruowany, ale dlaczego? (Równość jest łatwiejsza, ponieważ po prostu zaimplementowałbyś element członkowski operator==). Moja ogólna filozofia jest taka, że ​​jeśli funkcja jest naturalna i zasadniczo jedyna „poprawna” (jak porównanie par leksykograficznych), to dodaję ją do std. Jeśli jest to coś osobliwego (np. Porównanie par nieuporządkowanych), określam je jako specyficzne dla typu kontenera.
Kerrek SB
3
Nie zgadzam się, ale gdzie w standardzie możemy i zachęcamy do dodawania specjalizacji do std?
razeh
3
@Kerrek, zgadzam się, ale liczyłem na odniesienie do rozdziału i wersetu do miejsca w standardzie. Znalazłem sformułowanie zezwalające na wstrzyknięcie w 17.6.4.2.1, gdzie jest napisane, że jest to niedozwolone „chyba że określono inaczej”, ale nie byłem w stanie znaleźć części „inaczej określonej” w specyfikacji zawierającej ponad 4000 stron.
razeh
3
@razeh tutaj możesz przeczytać "Program może dodać specjalizację szablonu dla dowolnego standardowego szablonu biblioteki do standardowej przestrzeni nazw tylko wtedy, gdy deklaracja zależy od typu zdefiniowanego przez użytkownika, a specjalizacja spełnia standardowe wymagania biblioteki dla oryginalnego szablonu i nie jest wyraźnie zabroniona . ”. Więc to rozwiązanie jest w porządku.
Marek R
7

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 -
sehe
źródło
Doceniam, że możesz napisać coś, co nie ma domyślnego konstruktora, ale zawsze uważam, że wymaganie od każdej konstrukcji mapy zapamiętania dodatkowego argumentu jest trochę obciążeniem - zbyt dużym obciążeniem jak na mój gust. Nic mi nie jest z wyraźnym argumentem dotyczącym szablonu, chociaż specjalizacja std::hashjest nadal najmilszym wyjściem :-)
Kerrek SB
na ratunek typy zdefiniowane przez użytkownika :-) A mówiąc poważnie, mam nadzieję, że uderzylibyśmy ich w nadgarstki już na etapie, gdy ich klasa zawiera char*!
Kerrek SB
Hmm ... masz przykład, jak hashspecjalizacja zakłóca ADL? To znaczy, jest to całkowicie prawdopodobne, ale trudno mi wymyślić problem.
Kerrek SB
To wszystko jest zabawne i gry, dopóki nie potrzebujesz, std::unordered_map<Whatever, Xunset>a to nie działa, ponieważ twój Xunsettyp skrótu nie jest domyślny do skonstruowania.
Brian Gordon,
4

@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.
aschepler
źródło
Nie, żadna z implementacji nie jest zgodna ze standardami, ponieważ starają się specjalizować, std::hash<X>::operator()a nie std::hash<X>jako całość, a podpis std::hash<T>::operator()jest zdefiniowany przez implementację.
ildjarn
@ildjarn: Wyjaśniono - mówiłem o wdrożeniach bibliotek, a nie o próbach specjalizacji. Nie jestem pewien, o który dokładnie OP chciał zapytać.
aschepler