C++ Variadic templates from the ground up

Its  the new projec’s kickoff meeting. You’ve  been assigned one of the most important tasks: writing a sum function  (yes I know,  work with me here..)

the function needs to accept two values and return their sum. You implant the function and try it out:

double sumf_v1(double a, double  b) 
{
	return a + b;
}

 

int main()
{
	double a = 1;
	double b = 2;

	double  theSum = sumf_v1(a,b);
	cout << "the sum is: " << theSum << endl;
	return 0;
}

the sum is: 3

After completing the implementation you notice that every argument is cast to double.  You decide to rewrite sumf  as a  template function:

template <typename T>
double sumf_v2(T a, T  b)
{
	return a + b;
}

In this version, if the user calls sunf with two integers  the addition operation will be done on two integers leaving only the result to be cast to double,  which is cleaner.

However,  your unit tests reveal a problem:  This test program do not compile,  with several errors. One of which is  ‘double sumf_v2(T,T)’: could not deduce template argument for ‘T’ from ‘int’:

int main()
{
	double  theSum = sumf_v2(1.5,2);
	cout << "the sum is: " << theSum << endl;
	return 0;
}

The compiler has found the first argument in the sumf call   sumf_v2(1.5,2)  and deduced its type as  float (so the template type is set to a float type)
moving over to the next argument, sumf_v2(1.5,2)  the compiler decides  it’s of type int ,  so now the compiler tries to set T to int,  but T is already a float, so compilation stops and a complaint is issued to you.

Fortunately, this is easily fixable by adding another template type:

template <typename T1, typename T2>
double sumf_v3(T1 a, T2  b)
{
	return a + b;
}

Now each value has its own independent  type.  Any  combination of numerical types will compile. All the unit tests compile and pass!  you commit your code and move on.

a couple of days later  you get an email from the project’s lead , your new  function  works great, it’s just that the requirements have changed and now sumf needs to sum-up either 2 or 3 numerical.

Leveraging on your earlier efforts you create and overload of  sumf_v2.
Now have these two functions:

template <typename T1, typename T2>
double sumf_v2(T1 a, T2  b)
{
	return a + b;
}

template <typename T1, typename T2, typename T3>
double sumf_v2(T1 a, T2  b, T3 c)
{
	return a + sumf_v2(b,c);
}

You can now compile and run this program:

int main()
{
	double  theSumOfTwo   = sumf_v2(1.5,2);
	double  theSumOfThree = sumf_v2(1.5,2,3);
	cout << "the sum of two is: " 
	  << theSumOfTwo
	  << " The sum of three is: "
	  << theSumOfThree 
	  << endl;
	return 0;
}

Before you get a chance to  commit your code,  another email arrives informing you requirements have changed again:  in some cases, your function will need to sum 4 arguments!

You wearily  create yet another overload for sumf_v2 

template <typename T1, typename T2, typename T3, typename T4>
double sumf_v2(T1 a, T2  b, T3 c, T4 d)
{
	return a + sumf_v2(b, c, d);
}

so now your sum function  can  sum 2,3 or 4 arguments. But, that not enough for the greedy project lead as he drops by and asks you to also support 5 arguments.

Ok, you’ve  had it! there simply  must  be a better way! besides rewriting the code and adding overloads.  Well, you can have the compiler write all these functions for you when they are needed!

If the long forward didn’t make you forget what this post is all about, you probably  guessed the solution  will involve variadic templates.

let’s define another version for sumf at this time we’ll  define only the prototype as the implementation requires one more step

template <typename... AllT>
double sumf_v3(AllT.. ts)

the  funny typename  keyword with the three dots  in the first line  is called a parameter pack.  It’s our way to tell the compiler that this function template can take any number of arguments (including  0 –   that is no arguments at all)

It’s similar to what we’ve manually done with sumf_v2, by creating overloads  :

template <typename T1, typename T2>
double sumf_v2(T1 a, T2  b);
  
template <typename T1, typename T2, typename T3>
double sumf_v2(T1 a, T2  b, T3 c);

template <typename T1, typename T2, typename T3, typename T4>
double sumf_v2(T1 a, T2  b, T3 c, T4 d);

we told the compiler our function might have 2,3 or 4 arguments.  With the  parameter pack declaration,  we are telling the compiler to create templates with these types:

template <>
template <typename T1>
template <typename T1, typename T2>
template <typename T1, typename T2, typename T3>
template <typename T1, typename T2, typename T3, typename T4>
.
.
.

But which of these overloads   the compiler should create?  this list can be very long.  The answer – only the functions we need – that is the ones that actually get called in the code.  So if there is a function call trying to sum-up  5 arguments the compiler will create :

template <typename T1, typename T2, typename T3, typename T4, typename T5>
double sumf_v3(T1 a, T2  b, T3 c, T4 d, T5 e);

We can employ the strategy used while expanding  sumf_v2 to support more than two values:  calculate sum of arguments by adding the first argument to the  sum of the other n-1  arguments. It’s a recursive pattern that pops up a lot when dealing with variadic templates.   Look again at the implementation of  sumf_v2(T1 a, T2  b, T3 c)  and try to identify this pattern.

To get the  system,  we developed for sumf_v2 ,  to work,  we need a way to isolate the value of the first argument and add it to the sum of the rest argument.  Just we did in the sumf_v2 overloads.

The way to do it in the template function is to define it in a way that  gives the first argument a special name:

template <typename T, typename... RestOfTs>
double sumf_v3(T a , RestOfTs... ts)
{
	return a + sumf_v3(ts...);
}

In this implementation, the first argument gets a type T and a special name a.   The three dots after the ts argument  are called  parameter unpacking it tells the compiler to  pass the rest of the arguments  to the next function.  So in the function call sumf_v3(1, 4, 5.5, 7, 89).  The variable a will be  assigned the value 1 and the generated function implementation will look something like
return  a + sumf_v3(4, 5.5, 7, 89) ;
This is exactly what we wanted!

There is one more small roadblock between us and sumf bliss.  This code will not compile, just yet, giving an error  sumf_v3′: no matching overloaded function found
what?  didn’t we just define a function that will match any possilbe number of  argument ?  its true that    typename…  define  0 or more arguments,  but   our declaration is:

template <typename T, typename... RestOfTs>
double sumf_v3(T a , RestOfTs... ts);

That is one argument followed by a list of 0 or more other arguments. So there has to be at least one argument. Consider the implementation  generated  for sumf_v3(1,2):

return 2 + sumf_v3(3, )

You should read the weird function call  sumf_v3(3, )  as  sumf_v3(3).  I wanted to emphasize the empty list as the second argument . The   implementation for this function call  is :

return 3 + sumf_v3();

which not defined since there has to be at leat the first argument (T a),   The way to resolve this is to give the compiler a better choice when sumf gets called with only one argument :


template <typename T>
double sumf_v3(T a)
{
	return a;
}

When there is  only  one argument,  the compiler will  not try to recursively call a function with an empty list.   Instead , it will just return the received value.  That’s the recursion termination condition:

sumf_v3(1,2)   expands to
return 1 + sumf_v3(2)   expands to
return 1 + 2

so now we have a  pair  of templates

template <typename T>
double sumf_v3(T a)
{
	return a;
}

template <typename T, typename... RestOfTs>
double sumf_v3(T a , RestOfTs... ts)
{
	return a + sumf_v3(ts...);
}

That define a way to generate, on demand, a sum function accepting any number of arguments of any numerical type.  No additional coding needed!

Final notes

Like regular templates, variadic templates can also be used when defining classes and structures.  There are  several methods  in C++ your use to control  the generated code. For example, the template can examine  whether or not a type is a POD (Plain Old Data) and generate different code   for each case. this is called meta programming and will be the subject of a future post.

It’s important to understand that like any other  code generated from  templates, variadic or not,   any  decision  made  is  done in compile time.  By the time  the compiler finish it job all functions and types have defined static attributes in terms of  arguments number and types.

 

Leave a Reply

Your email address will not be published. Required fields are marked *