How to write a variadic template recursive function?
Solution 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...>();
}
Solution 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>
{};
Solution 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 int
s is fine.
Solution 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;
}
Solution 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;
}
alexeykuzmin0
I'm a professional C++ developer with background in machine learning and classical algorithms and data structures. Experienced in developing high-performance trading systems. I'm currently working in Google UK. I graduated from Computational Mathematics and Cybernetics department of Lomonosov Moscow State University. I have some experience in Java, Matlab, C#, Python, Haskell and other languages (who doesn't?), but C++ is my primary language.
Updated on June 03, 2022Comments
-
alexeykuzmin0 almost 2 years
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 resolvef<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
.