
Boost : 
Subject: Re: [boost] [hash] Extract module from functional + std::hash_combine
From: Peter Dimov (lists_at_[hidden])
Date: 20171219 16:14:21
Daniel James wrote:
> But it's possible that the next standard will include 'hash_combine', as
> well as functions using variadic arguments:
>
> http://www.openstd.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf
Nico Josuttis has been pushing for std::hash_combine  his latest is
http://www.openstd.org/jtc1/sc22/wg21/docs/papers/2017/p0814r0.pdf
and I vaguely remember it being accepted by LEWG at the last meeting, but at
the moment I'm not convinced that this is the right way forward.
The alternatives proposed by Howard Hinnant and by Google are better.
http://www.openstd.org/jtc1/sc22/wg21/docs/papers/2015/p0029r0.html
http://www.openstd.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html
The problem with our hash_combine is twofold. First, it doesn't allow
intermediate state bigger than size_t. Second, it necessitates that the
value of the object is collapsed into a single size_t before being mixed
into the intermediate state (which is also the final state in our
implementation, but it doesn't need to be.)
So if we have
struct X
{
Y y;
Z z;
};
struct Y
{
U u;
V v;
};
and we evaluate hash<X>()(x), we get
size_t state = 0;
size_t v1 = hash_value(x.y);
size_t st2 = 0;
size_t w1 = hash_value(x.y.u);
hash_combine(st2,w1);
size_t w2 = hash_value(x.y.v);
hash_combine(st2,w2);
return st2;
hash_combine(state, v1);
size_t v2 = hash_value(x.z);
hash_combine(state, v2);
return state; // or f(state)
whereas we'd rather like the following:
State state{}; // hash algorithm dependent
hash_combine(state, x.y);
hash_combine(state, x.y.u);
hash_combine(state, x.y.v);
hash_combine(state, x.z);
return f(state);
The interesting thing is that our hash_combine signature is actually
compatible with the second approach; we just need to make the state
(currently fixed to size_t) a template parameter, and instruct people to
write their custom overloads as:
template<class State> void hash_combine(State& state, X const& x)
{
hash_combine(state, x.y);
hash_combine(state, x.z);
}
instead of providing hash_value.
Hash algorithms, in turn, will (may(*)) provide overloads of the form
void hash_combine(md5& state, int const& x)
{
// mix x into state
}
and the hash<> object will create an instance of the algorithm, call
hash_combine, and return the final state.
This is basically what N3980 does, except with hash_append.
(*) May, because we can provide a generic overload for 'int' that hashes it
at the byte level, as is the standard nowadays.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk