C++11 : The three dots, that is variadic templates, part …

Variadic templates in C++11 allow writing functions that take in multiple parameters that can be of varying types.(*) What could this be useful for?

We sometimes have to be able to generate hash values out of objects, that is a number that represents that object uniquely. (Introductory article : http://en.wikipedia.org/wiki/Hash_function ) If even one bit in the object changes, we hope to see a “big change” in the generated hash value. The details of generating hashes is beyond the scope of this blog post and I will just use the hash facilities available in the C++11 standard library as well as a snippet borrowed from the Boost library. The quality of the hashes produced by the presented code may be sub-optimal but this blog post mainly attempts to demonstrate the C++11 variadic templates, not ideal algorithms to generate hash values.

Let’s say we have a class like :

class hash_test_object
{
public:
    double x=0.0;
    double y=0.0;
    double z=0.0;
    std::string id="Unknown";
};

How can we get a hash value out of an object instance of that? The C++11 standard library provides hash functions for some basic types, including double and std::string that we have in the class. It does not however provide anything to help us to get a hash from multiple values of those basic types. It is possible, however, to write a function like :

template<typename T>
void combine_hash(size_t& seed, const T& x)
{
    // Borrowed from Boost
    seed ^= hash_helper(x) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

Which calls the suitable overload of hash_helper :

template<typename T>
size_t hash_helper(const T& x)
{
    return std::hash<T>()(x);
}
// Dirty trick to enable hashing string literals, may be unacceptably slow in certain situations
size_t hash_helper(const char* x)
{
    return std::hash<std::string>()(std::string(x));
}

Then we can do the following to get a hash value out of the object :

void do_multicall_hash_combine()
{
    hash_test_object obj;
    size_t the_hash=0;
    combine_hash(the_hash,obj.x);
    combine_hash(the_hash,obj.y);
    combine_hash(the_hash,obj.z);
    combine_hash(the_hash,obj.id);
    std::cout << "(multicall) hash is " << the_hash << "\n";
}

Ok, so this works and we could call it a day. Or we could get annoyed about having to write that kind of code. If only there was a way to just do the hash combining with a single function call…And there is, by using variadic templates. I’ll just go straight to it.

template<typename T>
void combine_hashes_helper(size_t& seed, const T& x)
{
    seed ^= hash_helper(x) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

template<typename T, typename... Args>
void combine_hashes_helper(size_t& seed, const T& x, Args&&... args)
{
    seed ^= hash_helper(x) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    combine_hashes_helper(seed,std::forward(args)...);
}

template<typename... Args>
size_t combine_hashes(Args&&... args)
{
    size_t seed=0;
    combine_hashes_helper(seed,std::forward(args)...);
    return seed;
}

That sure is painful to look at, but hopefully writing that kind of code will be the responsibility of library code developers. The client code that wants to use that code will be a lot simpler. (One could of course simultaneously be both the library and client code developer. It does require somewhat of a split personality…)

void do_variadic_hash_combine()
{
    hash_test_object obj;
    size_t the_hash=combine_hashes(obj.x,obj.y,obj.z,obj.id);
    std::cout << "(variadic) hash is " << the_hash << "\n";
}

A lot cleaner on the client code side compared to making the multiple calls to the hash combining function! Obviously it would be even nicer if we had some way to enumerate the class’s member variables automatically and make the hash out of those, but since C++ sadly still doesn’t have such reflection capabilities, we will have to settle to having to write out the member variables of interest ourselves. (We could of course develop a tool using for example Clang that would autogenerate this kind of stuff from the results of static code analysis, but that has some downsides and difficulties too.)

Additional examples of calls into the variadic function :

// The last zero being either float or double changes the hash,
// which is what we want
combine_hashes(0.0,0.0,0.0f); 
combine_hashes(0.0,0.0,0.0);
combine_hashes("The black cat walked on the street",42,0.0001,true);
combine_hashes("The black cat walked on the street",42,0.0001,false);
combine_hashes("The white cat walked on the street",42,0.0001,false);
combine_hashes("The white cat walked on the street",42,0.0002,false);
// Same numbers but in different order 
// give a different hash, as they should
combine_hashes(100,101);
combine_hashes(101,100);

I didn’t go into the details of writing the variadic function templates here, why the things need to be like they are in the library code and so on. I just wanted to give one hopefully motivating example where the C++11 variadic templates can be used to simplify the (client side) code. There are of course variadic class templates too… 😉

Related video of interest :

http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Variadic-Templates-are-Funadic

(*) The C language of course has had for a long time the capability to do something vaguely similar, variadic functions, the most familiar example being the printf() function. The C variadic functions are a mess though and since we live in the year 2014, nobody should really be writing C anyway unless absolutely necessary.