How to specialize std::hash<Key>::operator() for user-defined type in unordered containers?
C++HashC++11Unordered MapUnordered SetC++ Problem Overview
To support user-defined key types in std::unordered_set<Key>
and std::unordered_map<Key, Value>
one has to provide operator==(Key, Key)
and a hash functor:
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;
It would be more convenient to write just std::unordered_set<X>
with a default hash for type X
,
like for types coming along with the compiler and library.
After consulting
- C++ Standard Draft N3242 §20.8.12 [unord.hash] and §17.6.3.4 [hash.requirements],
- Boost.Unordered
- g++
include\c++\4.7.0\bits\functional_hash.h
- VC10
include\xfunctional
- various related questions in Stack Overflow
it seems possible to specialize 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
}
Given compiler support for C++11 is yet experimental---I did not try Clang---, these are my questions:
-
Is it legal to add such a specialization to namespace
std
? I have mixed feelings about that. -
Which of the
std::hash<X>::operator()
versions, if any, is compliant with C++11 standard? -
Is there a portable way to do it?
C++ Solutions
Solution 1 - C++
You are expressly allowed and encouraged to add specializations to namespace std
*. The correct (and basically only) way to add a hash function is this:
namespace std {
template <> struct hash<Foo>
{
size_t operator()(const Foo & x) const
{
/* your code here, e.g. "return hash<int>()(x.value);" */
}
};
}
(Other popular specializations that you might consider supporting are std::less
, std::equal_to
and std::swap
.)
*) as long as one of the involved types is user-defined, I suppose.
Solution 2 - C++
My bet would be on the Hash template argument for the unordered_map/unorder_set/... classes:
#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
}
Of course
- hashX could just as well be a global static function
- in the second case, you could pass that
- the oldfashioned functor object (
struct Xhasher { size_t operator(const X&) const; };
) std::hash<X>()
- any bind expression satisfying the signature
- the oldfashioned functor object (
Solution 3 - C++
@Kerrek SB has covered 1) and 3).
- Even though g++ and VC10 declare
std::hash<T>::operator()
with different signatures, both library implementations are Standard compliant.
The Standard does not specify the members of std::hash<T>
. It just says that each such specialization must satisfy the same "Hash" requirements needed for the second template argument of std::unordered_set
and so on. Namely:
- Hash type
H
is a function object, with at least one argument typeKey
. H
is copy constructible.H
is destructible.- If
h
is an expression of typeH
orconst H
, andk
is an expression of a type convertible to (possiblyconst
)Key
, thenh(k)
is a valid expression with typesize_t
. - If
h
is an expression of typeH
orconst H
, andu
is an lvalue of typeKey
, thenh(u)
is a valid expression with typesize_t
which does not modifyu
.