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:
Czy dodanie takiej specjalizacji do przestrzeni nazw jest legalne
std
? Mam co do tego mieszane uczucia.Która z
std::hash<X>::operator()
wersji, jeśli w ogóle, jest zgodna ze standardem C ++ 11?Czy można to zrobić w sposób przenośny?
źródło
operator==(const Key, const Key)
std::hash
(w przeciwieństwie do innych rzeczy wstd
przestrzeni nazw) jest odradzana w przewodniku stylistycznym Google ; Dodaj szczyptę soli.Odpowiedzi:
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:(Inne popularne specjalizacje, które można wziąć pod uwagę wsparcie są
std::less
,std::equal_to
istd::swap
.)*) o ile jeden z zaangażowanych typów jest zdefiniowany przez użytkownika, jak przypuszczam.
źródło
unorder_map<eltype, hash, equality>
zamiast tego tworzenie instancji , aby nie zepsuć komuś dnia zabawnym biznesem ADL. ( Edycja rada Pete Beckera na ten temat )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ą dostd
. Jeśli jest to coś osobliwego (np. Porównanie par nieuporządkowanych), określam je jako specyficzne dla typu kontenera.Mój zakład byłby oparty na argumencie szablonu Hash dla klas unordered_map / unorder_set / ...:
Oczywiście
struct Xhasher { size_t operator(const X&) const; };
)std::hash<X>()
źródło
std::hash
jest nadal najmilszym wyjściem :-)char*
!hash
specjalizacja zakłóca ADL? To znaczy, jest to całkowicie prawdopodobne, ale trudno mi wymyślić problem.std::unordered_map<Whatever, Xunset>
a to nie działa, ponieważ twójXunset
typ skrótu nie jest domyślny do skonstruowania.@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 szablonustd::unordered_set
i tak dalej. Mianowicie:H
to obiekt funkcji z co najmniej jednym typem argumentuKey
.H
jest możliwe do skopiowania.H
jest zniszczalny.h
jest wyrażeniem typuH
lubconst H
ik
jest wyrażeniem typu, który można zamienić na (prawdopodobnieconst
)Key
, toh(k)
jest prawidłowym wyrażeniem typusize_t
.h
jest wyrażeniem typuH
lubconst H
iu
jest lwartością typuKey
, toh(u)
jest poprawnym wyrażeniem z typem,size_t
które nie zmienia sięu
.źródło
std::hash<X>::operator()
a niestd::hash<X>
jako całość, a podpisstd::hash<T>::operator()
jest zdefiniowany przez implementację.