How to write a variadic template recursive function?

Question

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.

Greengrocery

This is kind of redundant, isn't it? If it is a constexpr, the compiler is allowed to evaluate the expression at compiletime anyways, so why make it a template? why not define constexpr int f(int a, ...)? – Cameleer

@Cameleer Yes, for the sum such method works, but in my actual case the function is a bit more complicated and requires knowing the length of Rest... (something like convert to another base) which cannot be evaluated as a constexpr – Greengrocery

Answer 1

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

Cameleer

Answer 2

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>
{};

Forsythia

Thank you for the detailed explanation – Greengrocery

I've been trying to do this with strings, can't seem to constexpr succesfully using std::stringview, and also failing with the metaprogramming bit, am I being a dummy or is that just not possible like this? – Unlearn

Answer 3

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.

Grandiloquent

Yes, for the sum such method works, but my life is a bit more complicated. Closing as the question is formulated incorrectly. – Greengrocery

Answer 4

Just sum it up the usual way.

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

Airbrush

This was the first thing I tried. Unfortunately, my compiler (MSVC++ 2015) does not understand variables declarations in constexpr functions. – Greengrocery

@Greengrocery I see that you changed the C++14 tag. OK. – Airbrush

Yes, I just realised that lack of this feature means that my compiler has no full support of C++14 – Greengrocery

@Greengrocery changing the question requirements in such a way that it invalidates posted answers isn't generally regarded as polite, because it makes it look like the person who posted the answer did so incorrectly. – Erzurum

@Erzurum I understand this and am very sorry. But letting the question be formulated incorrectly would not help getting the right answer. – Greengrocery

If the original motivation of the original question is to accomplish large parts of the evaluation already at build time, this approach has the downside that dynamic code (an iterative for loop) is generated. The other examples expand to an explicit sum of the correct length that is processed without a dynamic iteration and loop checks/jumps. /// For toy examples like summing integers, this appears a bit like overshoot, but I guess this question is a simple model for real-life problems. – Sakmar

Answer 5

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;
}

Guanine

Answer 6

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;
}

Rendarender

This requires c++14, not 11 – Greengrocery

You cannot use this in a constant expression. Try with constexpr int v = f<1,2,3>();, it won't compile. – Horsemanship

And I find it begs the original question, like the answer of T.C. – Sakmar