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
How to Place a MACro in a Namespace in C++
How to Use Clang++ with -Std=C++11 -Weverything -Werror
What's the Point of Std::Unique_Ptr::Get
Intel Avx: 256-Bits Version of Dot Product for Double Precision Floating Point Variables
Any Way Faster Than Pow() to Compute an Integer Power of 10 in C++
Why Does Initializing an Extern Variable Inside a Function Give an Error
Is Std::Vector<T> a 'User-Defined Type'
Is There a Shorter Way to Write Compound 'If' Conditions
How to Embed a Http Server in a Google Chrome Extension
Simple 3X3 Matrix Inverse Code (C++)
How to Choose Heap Allocation VS. Stack Allocation in C++
When Do You Prefer Using Std::List<T> Instead of Std::Vector<T>
Why Can't I Static_Cast Between Char * and Unsigned Char *
How to Execute Two Threads Asynchronously Using Boost
Llvm Get Constant Integer Back from Value*