At a first look, the preceding implementation looks like recursion, because function add() calls itself, and in a way it is, but it is a compile-time recursion that does not incur any sort of runtime recursion and overhead. The compiler actually generates several functions with a different number of arguments, based on the variadic function template usage, so it is only function overloading that is involved and not any sort of recursion. However, implementation is done as if parameters would be processed in a recursive manner with an end condition.
In the preceding code we can identify the following key parts:
- Typename... Ts is a template parameter pack that indicates a variable number of template type arguments.
- Ts... rest is a function parameter pack that indicates a variable number of function arguments.
- Rest... is an expansion of the function parameter pack.
In the add(T head, Ts... rest) parameter, head is the first element of the list of arguments, and ...rest is a pack with the rest of the parameters in the list (this can be zero or more). In the body of the function, rest... is an expansion of the function parameter pack. This means the compiler replaces the parameter pack with its elements in their order. In the add() function, we basically add the first argument to the sum of the remaining arguments, which gives the impression of a recursive processing. This recursion ends when there is a single argument left, in which case the first add() overload (with a single argument) is called and returns the value of its argument.
This implementation of the function template add() enables us to write code, as shown here:
auto s1 = add(1, 2, 3, 4, 5);
// s1 = 15
auto s2 = add("hello"s, " "s, "world"s, "!"s);
// s2 = "hello world!"
When the compiler encounters add(1, 2, 3, 4, 5), it generates the following functions (arg1, arg2, and so on, are not the actual names the compiler generates) that show this is actually only calls to overloaded functions and not recursion:
int add(int head, int arg1, int arg2, int arg3, int arg4)
{return head + add(arg1, arg2, arg3, arg4);}
int add(int head, int arg1, int arg2, int arg3)
{return head + add(arg1, arg2, arg3);}
int add(int head, int arg1, int arg2)
{return head + add(arg1, arg2);}
int add(int head, int arg1)
{return head + add(arg1);}
int add(int value)
{return value;}
By adding a std::cout << __PRETTY_FUNCTION__ << std::endl at the beginning of the two functions we wrote, we get the following when running the code:
T add(T, Ts ...) [with T = int; Ts = {int, int, int, int}]
T add(T, Ts ...) [with T = int; Ts = {int, int, int}]
T add(T, Ts ...) [with T = int; Ts = {int, int}]
T add(T, Ts ...) [with T = int; Ts = {int}]
T add(T) [with T = int]
Since this is a function template, it can be used with any type that supports operator+. The other example, add("hello"s, " "s, "world"s, "!"s), produces the "hello world!" string. However, the std::basic_string type has different overloads for operator+, including one that can concatenate a string to a character, so we should be able to also write the following:
auto s3 = add("hello"s, ' ', "world"s, '!');
// s3 = "hello world!"
However, that will generate compiler errors as follows (note that I actually replaced std::basic_string<char, std::char_traits<char>, std::allocator<char> > with string "hello world" for simplicity):
In instantiation of 'T add(T, Ts ...) [with T = char; Ts = {string, char}]':
16:29: required from 'T add(T, Ts ...) [with T = string; Ts = {char, string, char}]'
22:46: required from here
16:29: error: cannot convert 'string' to 'char' in return
In function 'T add(T, Ts ...) [with T = char; Ts = {string, char}]':
17:1: warning: control reaches end of non-void function [-Wreturn-type]
What happens is that the compiler generates the code shown next where the return type is the same as the type of the first argument. However, the first argument is either a std::string or a char (again, std::basic_string<char, std::char_traits<char>, std::allocator<char> > was replaced with string for simplicity). In cases where char is the type of the first argument, the type of the return value head+add(...) that is an std::string does not match the function return type and does not have an implicit conversion to it:
string add(string head, char arg1, string arg2, char arg3)
{return head + add(arg1, arg2, arg3);}
char add(char head, string arg1, char arg2)
{return head + add(arg1, arg2);}
string add(string head, char arg1)
{return head + add(arg1);}
char add(char value)
{return value;}
We can fix this by modifying the variadic function template to have auto for the return type instead of T. In this case, the return type is always inferred from the return expression, and in our example, it will be std::string in all cases:
template <typename T, typename... Ts>
auto add(T head, Ts... rest)
{
return head + add(rest...);
}
It should be further added that a parameter pack can appear in a brace-initialization and its size can be determined using the sizeof... operator. Also, variadic function templates do not necessarily imply compile-time recursion as we have shown in this recipe. All these are shown in the following example where we define a function that creates a tuple with an even number of members. We first use sizeof...(a) to make sure that we have an even number of arguments and assert by generating a compiler error otherwise. The sizeof... operator can be used with both template parameter packs and function parameter packs. sizeof...(a) and sizeof...(T) would produce the same value. Then, we create and return a tuple. The template parameter pack T is expanded (with T...) into the type arguments of the std::tuple class template, and the function parameter pack a is expanded (with a...) into the values for the tuple members using brace initialization:
template<typename... T>
auto make_even_tuple(T... a)
{
static_assert(sizeof...(a) % 2 == 0,
"expected an even number of arguments");
std::tuple<T...> t { a... };
return t;
}
auto t1 = make_even_tuple(1, 2, 3, 4); // OK
// error: expected an even number of arguments
auto t2 = make_even_tuple(1, 2, 3);