CODEWITHSUNDEEP
c++c++11recursionvariadic-templatesvariadic-functions
alexeykuzmin0
alexeykuzmin0

Reputation: 6440

How to write a variadic template recursive function?

I'm trying to write a variadic template constexpr function which calculates sum of the template parameters given. Here's my code:

template<int First, int... Rest>
constexpr int f()
{
    return First + f<Rest...>();
}

template<int First>
constexpr int f()
{
    return First;
}

int main()
{
    f<1, 2, 3>();
    return 0;
}

Unfortunately, it does not compile reporting an error message error C2668: 'f': ambiguous call to overloaded function while trying to resolve f<3,>() call.

I also tried to change my recursion base case to accept 0 template arguments instead of 1:

template<>
constexpr int f()
{
    return 0;
}

But this code also does not compile (message error C2912: explicit specialization 'int f(void)' is not a specialization of a function template).

I could extract first and second template arguments to make this compile and work, like this:

template<int First, int Second, int... Rest>
constexpr int f()
{
    return First + f<Second, Rest...>();
}

But this does not seem to be the best option. So, the question is: how to write this calculation in an elegant way?

UP: I also tried to write this as a single function:

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

And this also does not work: error C2672: 'f': no matching overloaded function found.

Upvotes: 22

Views: 22715

Answers (6)

Justin
Justin

Reputation: 25377

template<int First, int... Rest>
constexpr int f()
{
    return First + f<Rest...>();
}

template<int First>
constexpr int f()
{
    return First;
}

int main()
{
    f<1, 2, 3>();
    return 0;
}

You get this error:

error C2668: 'f': ambiguous call to overloaded function while trying to resolve f<3,>() call.

This is because a variadic parameter pack can be given 0 arguments, so f<3> could work with template<int First, int... Rest> by "expanding" to template<3, >. However, you also have the specialization of template<int First>, so the compiler does not know which one to choose.

Explicitly stating the first and second template arguments is a completely valid and good solution to this problem.

When you try to change the base case to:

template <>
constexpr int f()
{
    return 0;
}

You have a problem because functions cannot be specialized in that way. Classes and structs can be, but not functions.

Solution #1: C++17 fold expression with constexpr

template <typename... Is>
constexpr int sum(Is... values) {
    return (0 + ... + values);
}

Solution #2: Use a constexpr function

constexpr int sum() {
    return 0;
}

template <typename I, typename... Is>
constexpr int sum(I first, Is... rest) {
    return first + sum(rest...);
}

Solution #3: Use Template Metaprogramming

template <int... Is>
struct sum;

template <>
struct sum<>
    : std::integral_constant<int, 0>
{};

template <int First, int... Rest>
struct sum<First, Rest...>
    : std::integral_constant<int,
        First + sum_impl<Rest...>::value>
{};

Upvotes: 13

Steephen
Steephen

Reputation: 15844

It is quite similar to what @T.C suggested above:

#include<iostream>
#include<numeric>

template<int First, int... Rest>
constexpr int f()
{
    auto types = {Rest...};
    return std::accumulate(std::begin(types), std::end(types),0);   
}

int main()
{
    std::cout <<f<1, 2, 3>();
    return 0;
}

Upvotes: 0

Patryk
Patryk

Reputation: 24140

A more generic solution using std::initializer_list would be:

template <typename... V>                                                                                                                                                                                         
auto sum_all(V... v)
{
  using rettype = typename std::common_type_t<V...>;
  rettype result{};
  (void)std::initializer_list<int>{(result += v, 0)...};
  return result;
}

Upvotes: 3

example
example

Reputation: 3419

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...>();
}

Upvotes: 21

Barry
Barry

Reputation: 303890

I find it generally easier to move the code from template arguments to function arguments:

constexpr int sum() { return 0; }

template <class T, class... Ts>
constexpr int sum(T value, Ts... rest) {
    return value + sum(rest...);
}

If you really want them as template arguments, you can have your f just call sum by moving them down:

template <int... Is>
constexpr int f() {
    return sum(Is...);
}

It's constexpr, so just using ints is fine.

Upvotes: 10

T.C.
T.C.

Reputation: 137394

Just sum it up the usual way.

template<int... Args>
constexpr int f() {
   int sum = 0;
   for(int i : { Args... }) sum += i;
   return sum;
}

Upvotes: 7

Related Questions