How to Write a Variadic Template Recursive Function

How to write a variadic template recursive function?

Your base case was wrong. You need a case for the empty list, but as the compiler suggests, your second try was not a valid template specialization. One way to define a valid instantiation for zero arguments is to create an overload that accepts an empty list

template<class none = void>
constexpr int f()
{
return 0;
}
template<int First, int... Rest>
constexpr int f()
{
return First + f<Rest...>();
}
int main()
{
f<1, 2, 3>();
return 0;
}

EDIT: for completeness sake also my first answer, that @alexeykuzmin0 fixed by adding the conditional:

template<int First=0, int... Rest>
constexpr int f()
{
return sizeof...(Rest)==0 ? First : First + f<Rest...>();
}

Creating a base case for Variadic Template recursion with no template arguments

Here's another solution (without specialization), which uses a C++20 requires clause to resolve the ambiguity:

template <typename... Args> requires (sizeof...(Args) == 0)
constexpr int NumArguments() {
return 0;
}

template<typename FirstArg, typename... RemainingArgs>
constexpr int NumArguments() {
return 1 + NumArguments<RemainingArgs...>();
}

Example:

int main() {
std::cout << NumArguments<int>() << std::endl;
std::cout << NumArguments() << std::endl;
std::cout << NumArguments<float, int, double, char>() << std::endl;
return 0;
}
1
0
4

EDIT:
My old suggestion using concepts was incorrect. There's a good post here on using concepts and parameter packs.

How to create a variadic function that are recursive with the given pseudo code in C++?

We can forward the arguments in a tuple and decrement the index:

#include <cstddef>
#include <tuple>
#include <utility>

template <std::size_t I, typename Tuple>
void test_helper(Tuple&& tuple)
{
if constexpr (I != 0) {
test_helper<I - 1>(std::forward<Tuple>(tuple));
}

// for example
process(std::get<I>(std::forward<Tuple>(tuple)));
}

template <typename... Args>
void test(Args&&... args)
{
test_helper<sizeof...(Args) - 1>(std::forward_as_tuple(std::forward<Args>(args)...));
}

Example:

#include <cstddef>
#include <iostream>
#include <tuple>
#include <utility>

template <typename T>
void process(const T& arg)
{
std::cout << arg << '\n';
}

template <std::size_t I, typename Tuple>
void test_helper(Tuple&& tuple)
{
process(std::get<I>(std::forward<Tuple>(tuple)));

if constexpr (I != 0) {
test_helper<I - 1>(std::forward<Tuple>(tuple));
}
}

template <typename... Args>
void test(Args&&... args)
{
test_helper<sizeof...(Args) - 1>(std::forward_as_tuple(std::forward<Args>(args)...));
}

int main()
{
test(1, '2', "3", 4.0);
}

(live demo)


For now, prefer handling arguments from left to right, which is much simpler:

template <typename... Args>
void test(Args&&... args)
{
((void)process(std::forward<Args>(args)), ...);
}

Handling from right to left will get easier with P1858 Generalized pack declaration and usage, which unfortunately hasn't been adopted yet:

template <typename... Args>
void test(Args&&... args)
{
test(std::forward<Args>(args)...[:-1]...);

if constexpr (sizeof...(Args) != 0) {
process(std::forward<Args>(args)...[-1]);
}
}

recursion in variadic template function of different argument types

1 Problems with your approach

1.1 Missing return in foo<1>

Make sure you understand how a return from a nested call works. Your foo<1> calls foo<0> which returns its (foo<0>'s) first argument back to foo<1>. But your foo<1> does not care about foo<0>'s return because it called foo<0> like this:

else {
foo<i-1>(args...);// `i-1` becomes `0`
}

The compiler knows you have a problem here: Which value should foo<1> return after it got the return from foo<0> (which has been ignored)? It has to return a value of the same type as its first argument, but it never returns before reaching its closing }.

As pointed out in the comments, you should turn on compiler warnings to detect problems like these. In this case, -Wall (GCC documentation on warning options) is sufficient for GCC and clang to warn you (online demo), but there are more warnings available. If your filename reads main.cpp and the closing } is found line 23, column 1, the compiler warning could read

main.cpp: In function ‘Arg foo(Arg, Args ...) [with int INDEX = 1; Arg = int; Args = {double, const char*}]’:
main.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]

}
^

1.2 Return type must be known at compile time

You might attempt to fix your code by passing the return value from foo<0> up the stack:

else {
return foo<i-1>(args...);// NOTE: type of return value depends on `foo<i-1>`
}

However, that fails because foo<1> has been declared to return a value of the same type as its first argument:

template<int i, class Arg, class... Args>
Arg foo(Arg, Args... args) {// <--------- NOTE: must return a value of type `Arg`

2 Fix for your own recursive implementation

2.1 C++17 and above

With C++17 you can use auto as return type together with constexpr if to implement the recursion as follows:

template<size_t i, class T0, class... Ts>
auto foo(T0 v0, Ts... vs) {
static_assert(i < 1u + sizeof...(Ts));
if constexpr(0u == i) return v0;// <------ NOTE: must be `if constexpr` (C++17)
else return foo<i-1u>(vs...);
}

2.2 C++14 and above

With C++14 you can also use auto as return type, but constexpr if is not available. The workaround is a well-known idiom and uses specialization of a class templates that "implements" the recursion logic:

template<int i>
struct foo_impl {
static_assert(i > 0, "the case `i == 0` requires a specialization");

template<class T0, class... Ts>
static auto get(T0, Ts... vs) {
return foo_impl<i-1>::get(vs...);
}
};

template<>
struct foo_impl<0> {
template<class T0, class... Ts>
static auto get(T0 v0, Ts...) {
return v0;
}
};

template<int i, class... Ts>
auto foo(Ts... vs) {
static_assert(i >= 0 && i < sizeof...(Ts), "index range: [0, size)");
return foo_impl<i>::get(vs...);// forward to "implementation"
}

2.3 C++11 and above

With C++11 you would need to specify trailing return types which is a bit tedious. See max66's answer for details.

3 Final recommendations

  • Enable and analyze compiler warnings (-Wall is an absolute minimum).
  • Once you are familiar with these techniques, do not implement this yourself. Instead, learn and use standard solutions like std::tuple.
  • Use compile-time recursion with caution. It may significantly increase your compilation time.

recursive variadic template to print out the contents of a parameter pack

You need to use partial specialisation to end the recursion, but since you can't partially specialise free functions in C++, you need to create an implementation class with a static member function.

template <typename... Args>
struct Impl;

template <typename First, typename... Args>
struct Impl<First, Args...>
{
static std::string name()
{
return std::string(typeid(First).name()) + " " + Impl<Args...>::name();
}
};

template <>
struct Impl<>
{
static std::string name()
{
return "";
}
};

template <typename... Args>
std::string type_name()
{
return Impl<Args...>::name();
}

int main()
{
std::cout << type_name<int, bool, char, double>() << std::endl; // "i b c d"
return 0;
}

That first declaration of Impl is just a workaround for a shortcoming in g++ 4.6 (and below). It won't be necessary once it implements variadic templates correctly.

Check it out in action at ideone.com

How recursive variadic templates is work?

Is sum template function call once ?

Yes, it won't be called recursively. Instead, the expression is expanded for fold expression.

The instantiation of a fold expression expands the expression e as
follows:

...

2) Unary left fold (... op E) becomes (((E1 op
E2) op ...) op EN)

...

(where N is the number of elements in the pack expansion)

You might want to put ++count into the fold expression, e.g.

template<typename... T>
auto sum(T... args)
{
return (... + (++count, args));
}

As @Xatyrian pointed, its value is just same as the number of elements in the pack expansion, which could be taken by sizeof... too.

Recursive Variadic Template Function - No ambiguity?

Your code is problematic, but for a different reason. As noted in a answer to the related question Ambiguous call when recursively calling variadic template function overload, the second overload in your code is considered more specialized. However, it should appear before the routine with the parameter pack. Compiling your code with gcc 8.2.1 or clang 6.0.1 gives an error like

variadic.cpp: In instantiation of ‘std::__cxx11::string get_arg_types(Next, Rest ...) [with Next = int; Rest = {}; std::__cxx11::string = std::__cxx11::basic_string<char>]’:
variadic.cpp:7:67: recursively required from ‘std::__cxx11::string get_arg_types(Next, Rest ...) [with Next = double; Rest = {int}; std::__cxx11::string = std::__cxx11::basic_string<char>]’
variadic.cpp:7:67: required from ‘std::__cxx11::string get_arg_types(Next, Rest ...) [with Next = float; Rest = {double, int}; std::__cxx11::string = std::__cxx11::basic_string<char>]’
variadic.cpp:23:39: required from here
variadic.cpp:7:67: error: no matching function for call to ‘get_arg_types()’
return std::string(typeid(Next).name()) + "\n" + get_arg_types(rest...);
error: no matching function for call to ‘get_arg_types()

As you can see from the error, even when get_arg_types has a single parameter, the compiler picks up the first overload, which in turns call get_arg_types without arguments. A simple solution is to move the overload of get_arg_types with a single parameter before the routine with the template parameter pack, or add a declaration of the single-parameter get_arg_types before the general routine.

Alternatively, you could eliminate your specialization single-parameter of get_arg_types and add a specialization with 0 parameters:

std::string get_arg_types()
{
return std::string();
}

Again, such a specialization should be put (or at least declared) before the template routine. Notice that with this second solution the output is slightly changed.



Related Topics



Leave a reply



Submit