Boost logo

Boost :

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:

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

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.

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);
  size_t w2 = hash_value(x.y.v);
  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, gregod at, cpdaniel at, john at