Variadic Templates

The previous lesson measured specialization: Pack<bool> took the cost out of the slot and put it into a step at run time. This lesson also frees the number of template parameters. Can a function accept all of its arguments, however many are given? A variadic template makes that possible, but the expansion method changes how many bodies the compiler has to write. The question of the lesson is that number: how many bodies does expanding a pack produce?

Parameter Packs and sizeof…

The declaration typename... T with three dots defines a parameter pack: it gathers zero or more types under a single name. The function parameter T... x is the matching function parameter pack. The number of elements in the pack is known not at run time but at compile time, and is read with sizeof...(T). To use the pack, x... is written; this is called pack expansion: the compiler turns every element of the pack into a comma-separated list.

To pass a pack on to another function, std::forward is used. Whether an argument is an lvalue or an rvalue is preserved in a parameter of the form A&&; std::forward<A> passes that information on intact. The program below shows three things together.

// pack-operations.cpp — sizeof..., forwarding and a unary fold
#include <cstdio>
#include <utility>

template <typename... T>
constexpr int count_args(T...) { return static_cast<int>(sizeof...(T)); }

template <typename... T>
bool all_positive(T... x) { return (... && (x > 0)); }

static long sum3(long a, long b, long c) { return a + b + c; }

template <typename F, typename... A>
long forward_call(F f, A&&... a) { return f(std::forward<A>(a)...); }

int main() {
    std::printf("count %d %d %d\n", count_args(), count_args(1), count_args(1, 'a', 2.0));
    std::printf("all %d %d %d\n", all_positive(1, 2, 3) ? 1 : 0,
                all_positive(1, -2) ? 1 : 0, all_positive() ? 1 : 0);
    std::printf("forward %ld\n", forward_call(sum3, 1, 2L, 3));
    return 0;
}

count 0 1 3
all 1 0 1
forward 6

MT13. count_args gives zero for an empty pack and three for three arguments; the number is a constant at compile time. all_positive uses a fold expression: (... && (x > 0)) folds the pack into a single expression with the && operator. When the pack is empty, an && fold gives true. forward_call sends the arguments to sum3 without adding any copy; std::forward is needed only here, for forwarding.

Recursive Expansion and the Base Case

The classic way to expand a pack by hand has three steps: take the first argument, call the same function with the rest, and write a base case that stops when the pack runs out. Every call is made with a pack one element shorter, so every step is a separate template body.

We build the sum in two ways. sum_rec expands recursively; sum_fold gives the same sum with a single fold expression. Every body increments its own local static once, on the first call, so the counter counts the generated bodies.

// sum.hpp — recursive and fold sums, counting bodies
#ifndef SUM_HPP
#define SUM_HPP

inline int rec_bodies = 0;
inline int fold_bodies = 0;

inline long sum_rec() {
    static const bool registered = (++rec_bodies, true);
    (void)registered;
    return 0;
}

template <typename First, typename... Rest>
long sum_rec(First first, Rest... rest) {
    static const bool registered = (++rec_bodies, true);
    (void)registered;
    return first + sum_rec(rest...);
}

template <typename... T>
long sum_fold(T... x) {
    static const bool registered = (++fold_bodies, true);
    (void)registered;
    return (0L + ... + x);
}

#endif

// pack-expansion.cpp — the same sum, two expansion methods
#include <cstdio>

#include "sum.hpp"

int main() {
    long a = sum_rec(1, 2, 3);
    long b = sum_fold(1, 2, 3);
    std::printf("sum %ld %ld\n", a, b);
    std::printf("recursive %d fold %d\n", rec_bodies, fold_bodies);
    return 0;
}

sum 6 6
recursive 4 fold 1

MT14. Both methods give six, but their body counts are different. sum_rec(1, 2, 3) uses three template bodies (<int,int,int>, <int,int>, <int>) and one base function: four. sum_fold(1, 2, 3) gives the same sum with a single body. The recursive=4 fold=1 counts in the recursive pack expansion row of the core are this measurement. The cost falls under the compile kind: no decision step is left at run time, and the compiler writes a different amount of code for each expansion form.

Forms of the Fold Expression

A fold expression is written in four forms. A unary fold, (... + x) or (x + ...), carries only the pack; a binary fold, (0L + ... + x), adds an initial value. A left fold groups like ((x1 + x2) + x3), a right fold like (x1 + (x2 + x3)). A unary fold that carries no initial value is valid for an empty pack only with the &&, || and , operators: (... && ...) gives true on an empty pack, (... || ...) gives false, and a comma gives void(). A unary fold with + does not compile on an empty pack; this is why the 0L initial value is needed for the call sum_fold(). A fold expression works with a single body in every instantiation, because pack expansion is not a recursion but a single expression that the compiler generates.

The Expansion Pattern: The Right Side of the Three Dots

The meaning of the three dots depends on the expression to their left. x... expands only x; but (x * 2)... writes the whole pattern once for each element. If there is more than one pack in the pattern, they must all have the same length and are expanded together, element by element. The place of expansion matters too: a pack can be expanded in a function call argument list, in a brace initializer, in a template argument list, or in a fold expression. The program below shows two of these, the brace initializer and the fold expression.

// pattern.cpp — pattern expansion and the same-type query
#include <cstdio>
#include <type_traits>

template <typename... T>
int doubled(T... x) {
    int d[] = {static_cast<int>(x * 2)..., 0};
    int t = 0;
    for (int v : d) {
        t += v;
    }
    return t;
}

template <typename First, typename... T>
constexpr bool all_same_v = (std::is_same_v<First, T> && ...);

template <typename... T>
void print_all(T... x) {
    int index = 0;
    (std::printf("%s%d", index++ ? "," : "", static_cast<int>(x)), ...);
    std::printf("\n");
}

int main() {
    std::printf("doubled %d\n", doubled(1, 2, 3));
    std::printf("same %d %d\n", all_same_v<int, int, int>,
                all_same_v<int, int, long>);
    print_all(7, 8L, 'a');
    return 0;
}

doubled 12
same 1 0
7,8,97

MT15. doubled(1, 2, 3) writes the pattern three times: the set {2, 4, 6, 0} adds up to twelve. The trailing zero provides a valid set in place of {} for an empty pack. all_same_v is a type query, and the fold expression collects all the matches with &&. print_all is folded with the comma operator; in a comma fold the elements are evaluated from left to right, which the standard guarantees, and the order in the output shows it (97 is the code of the character a).

The Forwarding Constructor: Packs and std::forward

The most common use of a pack is to pass arguments to a constructor as they are when building an object. Parameters of the form A&&... make up a forwarding reference pack, and std::forward<A>(a)... preserves whether each element is an lvalue or an rvalue. To see this, let us write a type whose copies and moves we count.

// forwarding.cpp — forwarding constructor, copy and move counts
#include <cstdio>
#include <utility>

struct Trace {
    static inline int copies = 0;
    static inline int moves = 0;
    int value;
    explicit Trace(int v) : value(v) {}
    Trace(const Trace& o) : value(o.value) { ++copies; }
    Trace(Trace&& o) noexcept : value(o.value) { ++moves; }
};

struct Wrapper {
    Trace a;
    Trace b;
    template <typename A, typename B>
    Wrapper(A&& x, B&& y) : a(std::forward<A>(x)), b(std::forward<B>(y)) {}
};

template <typename T, typename... A>
T create(A&&... a) {
    return T(std::forward<A>(a)...);
}

int main() {
    Trace lvalue(1);
    Wrapper s1 = create<Wrapper>(lvalue, Trace(2));
    std::printf("copies=%d moves=%d\n", Trace::copies, Trace::moves);
    Wrapper s2 = create<Wrapper>(Trace(3), Trace(4));
    std::printf("copies=%d moves=%d\n", Trace::copies, Trace::moves);
    std::printf("values %d %d %d %d\n", s1.a.value, s1.b.value, s2.a.value, s2.b.value);
    return 0;
}

copies=1 moves=1
copies=1 moves=3
values 1 2 3 4

MT16. In the first construction, lvalue is an lvalue and std::forward<Trace&> copies it; the temporary Trace(2) is an rvalue and is moved. In the second construction both temporaries are moved. Without std::forward, every argument would go to the constructor as a named lvalue and would be copied each time. The counters are cumulative, so the second line includes both moves of the second construction; these are product counts, not a claim about time. This forwarding chain also makes the compiler write a separate create body for each combination of argument types, so the cost is again in the compile kind.

Packs and Class Templates

A pack is found not only in functions but also in class templates. std::tuple<int, double, char> is an example. We can write an empty class that carries our own type list and ask for the number of elements with sizeof...; the class itself holds no value, it only names the types.

// list.cpp — a class template that carries a type list
#include <cstdio>
#include <type_traits>

template <typename... T>
struct TypeList {
    static constexpr int size = static_cast<int>(sizeof...(T));
};

template <typename L>
struct SizeOf;

template <typename... T>
struct SizeOf<TypeList<T...>> {
    static constexpr int value = sizeof...(T);
};

static_assert(TypeList<int, char>::size == 2);
static_assert(SizeOf<TypeList<>>::value == 0);

int main() {
    using L = TypeList<int, double, char>;
    std::printf("size %d %d\n", L::size, SizeOf<L>::value);
    std::printf("empty %d\n", TypeList<>::size);
    return 0;
}

size 3 3
empty 0

MT17. TypeList<> is an empty pack and is valid; sizeof... gives zero. The SizeOf partial specialization collects the pack back with the TypeList<T...> pattern: the partial specialization of the previous lesson, this time with a pack. There is no run-time cost, because the two static_asserts and the members are fixed at compile time.

Storing a Pack: tuple, apply and index_sequence

A pack cannot be stored directly; it cannot be assigned to a variable or put in a container. To store it, the standard library gives std::tuple: it gathers elements of different types into a single value. std::apply expands the elements of a tuple as the arguments of a function, which builds a bridge between a tuple and a pack. If the elements need to be reached by index, std::index_sequence<I...> produces the sequence 0, 1, 2, ... at compile time as a pack. These three tools process the elements of a pack together with their positions without writing a recursion.

// tuple.cpp — tuple, apply and index_sequence
#include <cstdio>
#include <tuple>
#include <type_traits>
#include <utility>

template <typename T, std::size_t... I>
long weighted(const T& t, std::index_sequence<I...>) {
    return (((static_cast<long>(I) + 1) * std::get<I>(t)) + ...);
}

template <typename... A>
long weighted_sum(A... a) {
    auto t = std::make_tuple(a...);
    return weighted(t, std::index_sequence_for<A...>{});
}

int main() {
    auto t = std::make_tuple(2, 3, 4);
    long plain = std::apply([](auto... e) { return (0L + ... + e); }, t);
    std::printf("apply %ld\n", plain);
    std::printf("weighted %ld\n", weighted_sum(2, 3, 4));
    using second = std::tuple_element_t<1, std::tuple<int, double, char>>;
    std::printf("type %d\n", std::is_same_v<second, double>);
    return 0;
}

apply 9
weighted 20
type 1

MT18. std::apply expands the tuple, and the fold expression gives the sum 2 + 3 + 4. weighted multiplies each element by its position number: 1*2 + 2*3 + 3*4. index_sequence_for<A...> produces a sequence of the same length as the pack, and I... is expanded together with A... using this sequence. In the third line, tuple_element_t<1, ...> selects the second type from the pack; it is expected to be double, and the query confirms it. All of it is resolved at compile time and makes the compiler write a separate body for every different element count, so it is again in the compile kind.

A pack has limits too. An empty std::tuple<> is valid, but an empty pack has no position such as [0]. Pack expansion can be done only inside a pattern; a bare x... is not an expression on its own. In a class template, the pack parameter must be the last parameter. In a function template a parameter may follow the pack, but that parameter must be deducible or carry a default argument; an order such as template <typename... A, typename B> cannot be used if B cannot be deduced. That the pack is written together with a first element (First, Rest...) in recursive expansion rests on a different reason: separating the first element and recursing on the rest.

The Bounding Measurement

The number of bodies depends not on the number of calls but on the type list. A second call with the same type list uses the existing bodies; a call with different types produces new ones.

// pack-reuse.cpp — the same type list reuses bodies
#include <cstdio>

#include "sum.hpp"

int main() {
    sum_rec(1, 2, 3);
    sum_fold(1, 2, 3);
    std::printf("first      recursive %d fold %d\n", rec_bodies, fold_bodies);

    sum_rec(4, 5, 6);
    sum_fold(4, 5, 6);
    std::printf("second     recursive %d fold %d\n", rec_bodies, fold_bodies);

    sum_rec(1, 2, 3L);
    sum_fold(1, 2, 3L);
    std::printf("new types  recursive %d fold %d\n", rec_bodies, fold_bodies);
    return 0;
}

first      recursive 4 fold 1
second     recursive 4 fold 1
new types  recursive 7 fold 2

MT19. The (4, 5, 6) calls are also an int, int, int list: the body counts do not change, four to four. (1, 2, 3L) is a new type list: <int,int,long>, <int,long> and <long> produce three new recursive bodies, taking the count from four to seven; the base function stays the same. On the fold side too, the new list adds one new body. For this reason the number is not the measurement itself; it is the evidence that shows which kind the cost is written to: recursive expansion makes the compiler write new bodies as type variety grows, and this cost stays in the compile kind.

Summary

• The mechanism measured in this lesson moves the cost to the compile kind: expanding a pack produces a different number of bodies depending on the expansion method.
• typename... T is a parameter pack; sizeof...(T) gives the element count at compile time, and x... expands the pack.
• Recursive expansion needs a separate template body at every step and a base case (recursive=4); a fold expression needs a single body for the same job (fold=1).
• A unary fold accepts an empty pack only with &&, || and ,; a binary fold carries an initial value.
• The same type list reuses bodies (4 to 4); a new type list produces new bodies (4 to 7).

Next Step

In this lesson pack expansion made the compiler write bodies according to the type list, and the cost stayed at compile time. The next lesson covers the tools that put questions to a type itself, type traits: when a choice is made inside a template with if constexpr, how many queries does it leave at run time?