Re: [boost] [hash] Extract module from functional + std::hash_combine

Subject: Re: [boost] [hash] Extract module from functional + std::hash_combine
From: Peter Dimov (lists_at_[hidden])
Date: 2017-12-19 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.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf

Nico Josuttis has been pushing for std::hash_combine - his latest is

http://www.open-std.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.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0029r0.html
http://www.open-std.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.