Template metaprogramming

A template can compute while it is being instantiated. A class template with a static constexpr member, a specialisation for the base case and a recursive reference to itself is a loop that runs at compile time, and the result is a constant the program can use without any run-time work.

Lesson 039 showed the specialisation mechanism and lesson 041 the folds. This lesson uses them for computation: numbers, types and index sequences, and the failure mode of a recursion that never stops.

A loop that runs at compile time

The factorial below is a class template with one static constexpr member. The general form multiplies N by factorial<N - 1>, and the specialisation for 0 stops the recursion with 1.

The program checks the value with static_assert and prints factorial<10>, which the compiler computed while compiling the call. No loop exists in the binary; the number is a constant.

The same recursion written as a constexpr function is shorter in C++14 and later, and lesson 122 prefers it. The class template is still the shape every library trait uses.

The specialisation is not optional: without factorial<0> the compiler keeps asking for factorial<-1>, and the error is the depth limit of the last section. Every compile-time recursion in this lesson has the same two parts, a general step and a stopping rule.

#include <iostream> template <int N> struct factorial { static constexpr long long value = N * factorial<N - 1>::value; }; template <> struct factorial<0> { static constexpr long long value = 1; }; int main() { static_assert(factorial<5>::value == 120); std::cout << factorial<10>::value << '\n'; }

g++ -std=c++23 -Wall -Wextra factorial.cpp -o factorial
./factorial

3628800

Choosing a type

std::conditional_t<Flag, A, B> is one of the simplest type computations: it is A when the flag is true and B otherwise. The program uses it to pick the larger of two types and prints the size of the result.

The choice happens at compile time, so the type that was not chosen does not appear in the program at all. That is how a library selects an implementation type from a trait.

The trait itself is a class template with two specialisations, as in lesson 042; std::conditional is the standard one, and this program only reads its result.

#include <iostream> #include <type_traits> template <bool PickFirst, typename First, typename Second> using pick = std::conditional_t<PickFirst, First, Second>; int main() { std::cout << sizeof(pick<true, int, double>) << ' ' << sizeof(pick<false, int, double>) << '\n'; static_assert(std::is_same_v<pick<true, int, double>, int>); }

g++ -std=c++23 -Wall -Wextra conditional.cpp -o conditional
./conditional

4 8

A list of types

A template can carry types instead of values. list<int, double, char> is a type that holds three types in its parameter pack, and a partial specialisation can unpack them again.

The program counts the types in the list at compile time and prints the answer. The same shape is how std::tuple knows its size, and how a library stores a set of types for later.

The count is a sizeof... expression inside a partial specialisation, which is why it costs nothing: the compiler writes the number into the program as a constant.

#include <iostream> template <typename... Ts> struct list { }; template <typename List> struct count; template <typename... Ts> struct count<list<Ts...>> { static constexpr int value = sizeof...(Ts); }; int main() { using types = list<int, double, char, bool>; std::cout << count<types>::value << '\n'; }

g++ -std=c++23 -Wall -Wextra typelist.cpp -o typelist
./typelist

4

An integer sequence

std::integer_sequence<int, 0, 1, 2> is a type that carries a pack of numbers. A function template can deduce the pack from the type, and a fold expression then uses every value.

The program passes std::make_index_sequence<5> to print_all and prints 0 to 4. The sequence was built by the compiler, and the fold expanded it into five output operations.

This is the mechanism behind std::apply and behind every library that turns a tuple into a function call: an index sequence gives the positions, and each position is used to get one element.

A sequence can also be built from a pack: std::index_sequence_for<Ts...> produces one index per type, which is how a variadic function visits every argument of a tuple by position.

#include <iostream> #include <utility> template <typename T, T... Values> void print_all(std::integer_sequence<T, Values...>) { ((std::cout << Values << ' '), ...); std::cout << '\n'; } int main() { print_all(std::make_index_sequence<5>{}); }

g++ -std=c++23 -Wall -Wextra sequence.cpp -o sequence
./sequence

0 1 2 3 4

A recursion with no base case

A recursive template needs a specialisation that stops it, exactly like a recursive function. Without one the compiler keeps instantiating and eventually gives up with a depth limit.

The program asks for forever<0>::value, and the template references forever<1>, forever<2> and so on. The message reports that the instantiation depth exceeds the maximum and shows the last few instantiations.

The depth limit is a compiler safety valve, not a language rule: the standard only guarantees a few levels. A recursion that needs hundreds of steps should be a fold or a constexpr function instead.

template <int N> struct forever { static constexpr int value = forever<N + 1>::value; }; int main() { return forever<0>::value; }

g++ -std=c++23 -Wall -Wextra forever.cpp -o forever

forever.cpp: In instantiation of 'constexpr const int forever<899>::value':
forever.cpp:4:50: recursively required from 'constexpr const int forever<1>::value'
4 | static constexpr int value = forever<N + 1>::value;
| ^~~~~
forever.cpp:4:50: required from 'constexpr const int forever<0>::value'
forever.cpp:9:24: required from here
9 | return forever<0>::value;
| ^~~~~
forever.cpp:4:50: fatal error: template instantiation depth exceeds maximum of 900 (use '-ftemplate-depth=' to increase the maximum)
4 | static constexpr int value = forever<N + 1>::value;
| ^~~~~
compilation terminated.

Exercises

  1. Write power as a class template with a specialisation for exponent 0.
  2. Add a second type list and a trait that answers whether a type is in the list.
  3. Print the sum of an index sequence of length 10 with a fold expression.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What runs the loop in a template metaprogram?

    Answer

    The compiler, while instantiating the template

    Each instantiation computes a constant, and the chain stops at the specialisation.

  2. What stops a recursive template?

    Answer

    A specialisation for the base case

    The specialisation matches the last value and returns without instantiating itself again.

  3. What does std::conditional_t<true, A, B> give?

    Answer

    A

    The trait selects one of the two types according to the condition.

  4. What is std::index_sequence for?

    Answer

    Passing a list of indices to expand a pack

    The compile-time sequence gives each element of a tuple or pack an index.

  5. What does this program print? #include <iostream> template <int N> struct factorial { static constexpr int value = N * factorial<N - 1>::value; }; template <> struct factorial<0> { static constexpr int value = 1; }; int main() { std::cout << factorial<10>::value; }

    Answer

    3628800

    The ten instantiations multiply down to the base case, and the constant is printed.

  6. What does this program print? #include <iostream> #include <type_traits> template <typename T> struct pick { using type = std::conditional_t<(sizeof(T) <= 4), int, double>; }; int main() { std::cout << sizeof(typename pick<char>::type) << ' ' << sizeof(typename pick<double>::type); }

    Answer

    4 8

    The trait chooses int for the small type and double for the other, and their sizes are four and eight.

  7. What does this program print? #include <iostream> template <typename... Ts> struct count; template <> struct count<> { static constexpr int value = 0; }; template <typename T, typename... Rest> struct count<T, Rest...> { static constexpr int value = 1 + count<Rest...>::value; }; int main() { std::cout << count<int, double, char>::value; }

    Answer

    3

    Each instantiation adds one and the empty list stops at zero, so the list of three types gives three.

  8. What does this program print? #include <iostream> #include <utility> template <typename T, T... Values> void show(std::integer_sequence<T, Values...>) { ((std::cout << Values << ' '), ...); } int main() { show(std::make_index_sequence<5>{}); }

    Answer

    0 1 2 3 4

    The sequence holds the five indices, and the fold prints each one.

  9. What does the compiler report for this template? template <int N> struct forever { static constexpr int value = forever<N + 1>::value; }; int main() { return forever<0>::value; }

    Answer

    template instantiation depth exceeds maximum

    There is no base case, so the compiler keeps instantiating until its depth limit stops it.

  10. Why is a template metaprogram limited by the compiler?

    Answer

    The compiler has a maximum instantiation depth

    The depth limit is what turns a missing base case into a diagnostic instead of a hang.

The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.

Article author: Arthur Isaev