Introduction to Variadic templates

Variadic templates have been introduced to the language for roughly three reasons:

1. Define type-safe variadic functions. All of us have messed up using scanf at some point, and those of us who have ever written C99 or C++03 style variadic functions will know the pain that comes with automatic variadic argument promotions and the va_arg family of macros. Writing variadic macros is even more painful…
2. Define algebraic types without having to jump through too many hoops, that is std::tuple and std::variant.
3. Enable a variable numbers of settings and parameters in policy based designs. This is not something I will talk about as I myself don’t know that much about designing software that way.

Variadic templates have introduced very little syntax to the C++11 standard, only new meanings for the ellipsis ... operator as well as a new operator sizeof... (which is very different from the good old sizeof).

The ellipsis operator can be used in three distinct contexts:

1. In the template parameter list it defines a template parameter pack, that is a variable length list of template parameters. It looks as follows:

   template<typename... Ts>
   class C { /* Some code parametrised by all the types in Ts */ };
   

2. Similarly in the argument list of a function it defines a parameter pack that is a variable length list of arguments of the types defined in the template parameter list. This is what it looks like:

   template<typename... Ts>
   void foo(const Ts&... vs) { /* Some code using the values vs of type Ts */ }
   

   At this point it is worth noting that in a primary class template, the template parameter pack must be the final parameter in the template parameter list. In a function template, it is correct to put it earlier in the template parameter list, if and only if all the other template arguments can be deduced from the function arguments, or have default values. To show this better this I have a code snippet from cppreference:

   template<typename... Ts, typename U> struct Invalid; // Error: Ts.. not at the end
   
   template<typename ...Ts, typename U, typename=void>
   void valid(U, Ts...);     // OK: can deduce U
   // void valid(Ts..., U);  // Can't be used: Ts... is a non-deduced context in this position
   
   valid(1.0, 1, 2, 3);      // OK: deduces U as double, Ts as {int,int,int}
   

3. Finally, it defines a smart contextual expansion of the parameter pack(s) to its left. This is known as pack expansion and it is governed by the following rules:

   Usage	Expansion
   Ts...	T1, …, Tn
   Ts&&...	T1&&, …, Tn&&&
   x<Ts&, Y>::z...	x<T1, Y>::z, …, x<Tn, Y>::z
   x<Ts&, Us>::x...	x<T1&, U1>::z, …, x<Tn&, Un>::z
   func(5,v)...	func(5, v1), …, func(5, vn)

Pack expansions may occur in initializer lists, base class specifiers, inside class definitions, in template argument lists, and lambda capture lists.

I want to touch on the fact that parameter packs are not first class citizens of the language, and thus we can not write anything like the following:

template <typename... Ts>
void foo()
{
    Ts things;
    for (T& t : things) doStuff(t);
}

The usage is actually constrained to the following two things:

1. Apply sizeof... to the parameter pack: sizeof...(args). This will not return the number of bytes occupied by the arguments, rather the number of arguments in the parameter pack itself.
2. Expand the parameter pack using the rules described earlier.

The usual concepts of iteration and mutation are not defined on parameter packs and people tend to program them in a fashion very similar to that of functional programming languages such as Haskell or Lisp. Although the syntax for dealing with variadic templates can be a bit awkward and complicated, the benefits are worth it if you have a genuine need for variable numbers of arguments, as it can greatly reduce the complexity of usage of your constructs.

I now want to have a look at a very constrained example I found on HackerRank to see how these concepts (pun intended) are applied in practice.

We wish to implement a function that given 64 or less bool template parameters will return the uint64_t they represent binary notation.

The trick is to notice that the most significant bit, that is the first template argument, needs to be left-shifted by the reamining number of template arguments. In pseudo-code the structure looks as follows:

uint64_t bool2uint64() { return 0; }
uint64_t bool2uint64(msb, ...rest) { return (msb << len(rest)) | bool2uint64(rest...);}

We can jump straight in and write something along the lines of a base case for the no more template parameters case. We could then define another specialization for the recursive case with a template parameter representing the head of the parameter list, and a template parameter pack to represent the tail of the list:

uint64_t bool2uint64()
{
    return 0;
}

template<bool Msb, bool... RestBits>
uint64_t bool2uint64()
{
    return (Msb << sizeof...(RestBits)) | bool2uint64<RestBits...>();
}

Oops! This code does not compile because on the last “recursive” call, since the template parameter pack RestBits is empty and the function template<> bool2uint64<> would get called. The templated version is not the same as the non-templated base case. Furthermore, we would not be able to define the partially specialized form because that is simply not allowed by the language. Thankfully, partial template specialization is allowed for class types, and we can resort to the common idiom of delegating the work to a struct at compile time. Also we notice, that all this work can be done at compile time and thus can be marked as such with constexpr. The resulting implementation looks as follows:

template<bool... RestBits> struct Bool2UInt64;

template<>
struct Bool2UInt64<>
    : std::integral_constant<uint64_t, 0> { };

template<bool Msb, bool... RestBits>
struct Bool2UInt64<Msb, RestBits...>
    : std::integral_constant<uint64_t, (Msb << sizeof...(RestBits)) | Bool2UInt64<RestBits...>::value> { };

template<bool... Bits>
constexpr uint64_t bool2uint64()
{
    return Bool2UInt64<Bits...>::value;
}

An interesting technique I have used here is to have Bool2UInt64 inherit from std::integral_constant<T, V> defined in the type_traits header, which only contains a static constant expression value of type T and value V. This is a common pattern and std::integral_constant is perfect for this purpose as it offers an agreed-upon interface for accessing the result of the compile time computation.

The usage of our new bool2uint64 function is as follows:

constexpr uint64_t eleven = bool2uint64<true, false, true, true>();
static_assert(eleven == 11u, "we have not computed the right number!");

Obviously this example has no practical usage but it shows all of the concepts put together, you can find a gist containing the full code here. Any comments you put on there will of course be read.