Demystifying C++ Templates

October 28, 2022

Continuing on what seems to be a series on the odditied of C++, I would like to look at one of the most dreaded aspects of the language: Templates.

Much of the dread that has historically been associated with C++ templates is somewhat unwarranted with more modern versions of the language. In spite of improvements in usability, many difficulties remain with using this infamous feature. In this article I will attempt to walk through template concepts from beginner to advanced. This will not be an exhaustive list of the things you can do, fundamentally because even my relatively extensive knowledge on the subject is unlikely to cover all of what is possible in this area.

Starting things simple: Template Parameters

template<typename T>
T add(T a, T b) {
    return a + b;
}

Written above is the hello world of template functions. It takes two values of the same type and adds them together, provided the type T has the + operator implemented. To use the function we simply call it as if we would any other function:

int addedValue = add(10, 30);
assert(addedValue == 30);

Template Argument Deduction

In most cases when a template function is called, the compiler should be able to determine the type of the template parameter. In our example before, the code will be replaced with what the compiler determines is the correct type for that function call:

int addedValue = add<int>(10, 30);

This will also lead the compiler to generate an instance of the template function:

// Generated source is written for illustration purposes,
// in reality the compiler would hold the generated version of
// the function in its own format.
int add<int>(int a, int b) {
    return a + b;
}

Templates Vs. Generics

C++ templates are often compared to generics that are found in other languages such as Java, but there are some key differences in how they operate. In C++, each call to a template function using different template parameters will generate a new function symbol that will need to be linked into the final program. This differs from a generic function in Java where there is just the one function which is capable of being run regardless of the type that is provided to it. The major difference here is that when a generic type is used in Java, it is incapable of accessing any members that have not been defined in the constraint of the generic:

class Value {
  int run() {}
}

void performRun<T>(T runner) {
  runner.run() // invalid
}

In Java all objects implicitly inherit from the Object class so the generic provided above is constrained to allow any Object. But in using that constraint it also limits the use of the generic type to only using members that are found on the base Object class. This means that the above program will fail to compile as the run function as it is attempting to access a function on type Value. The same is not true of C++, if a member is available on the template type provided, the function can be generated and therefore used. This in practice means a template function has an implicit interface to which it expects template types to follow.

It is this implicit interface which has made dealing with templates in the past so frustrating. Where a template function has been nested several levels deep in other template functions, horrendous compiler error messages can result informing you that this type that you didn’t even think you created doesn’t have a particular member function that you’ve never heard of. This I would argue is the key reason why C++ templates get as much hate as they do. Luckily, those at the C++ standards committee have known about the hatred caused by this for some time and came up with a solution: Concepts.

The Concept of Concepts

With concepts, the age of putting a type into a template function and praying that you have the right implementation is, for the most part, behind us. Concepts allow us to constrain which types can be used within a template function at the time of instantiation.

template<typename T>
concept Runnable = requires (T a) {
  { a.run() }
}

template<typename T>
void performRunNoConcept(T a) {
  a.run();
}

template<Runnable T>
void performRun(T a) {
  a.run();
}

From the program’s point of view, performRunNoConcept and performRun are functionally identical and will allow all of the same types to instantiate them. The compiler error provided by performRun when instantiated with an invalid type however, is more specific about what exactly the issue is with the provided type versus performRunNoConcept:

Without Concepts

Concepts.cpp: In instantiation of ‘void performRunNoConcept(T) [with T = IsNotRunnable]’:
Concepts.cpp:40:36:   required from here
Concepts.cpp:28:7: error: ‘class IsNotRunnable’ has no member named ‘run’
   28 |     a.run();

With Concepts

Concepts.cpp:41:27: error: use of function ‘void performRun(T) [with T = IsNotRunnable]’ with unsatisfied constraints
   41 |     performRun(notRunnable);
      |                           ^
Concepts.cpp:32:6: note: declared here
   32 | void performRun(T a) {
      |      ^~~~~~~~~~
Concepts.cpp:32:6: note: constraints not satisfied
Concepts.cpp: In instantiation of ‘void performRun(T) [with T = IsNotRunnable]’:
Concepts.cpp:41:27:   required from here
Concepts.cpp:22:9:   required for the satisfaction of ‘Runnable<T>’ [with T = IsNotRunnable]
Concepts.cpp:22:20:   in requirements with ‘T a’ [with T = IsNotRunnable]
Concepts.cpp:23:12: note: the required expression ‘a.run()’ is invalid, because
   23 |     { a.run() };
      |       ~~~~~^~
Concepts.cpp:23:9: error: ‘class IsNotRunnable’ has no member named ‘run’
   23 |     { a.run() };
      |       ~~^~~

This is a relatively simple example so the use of concepts could be argued to be giving too much information. Where concepts really shine is when a specific expectation about a type hides deep in the implementation of a template function (especially variadic template functions). Using concepts to constrain the type helps to programmer to simply implement exactly what is being asked for in the concept, rather than attempting to unpick a deep compiler instantiation trace.

Concepts act as explicit interfaces for templates. If a type implements all the requirements of the concept, then it can be used in the template function that uses that concept. The C++ 20 standard library supplies several useful concepts beyond the custom ones you can create yourself: - std::derived_from : Only accepts types that are derived from another specified type. - std::invokable : Only accepts types that can be called with a specific set of parameters. - std::is_same_as : Only accepts types that are the same as the specified type (This can be used to perform different operations for certain template types in an if constexpr statement).

As it stands at the moment, much of the standard library still does not use concepts to help constrain its most commonly used structures, hopefully over time this will change and gradually make C++ a less aggravating experience for everyone.

The `auto` Keyword

The auto keyword is one of the most misunderstood in the language, largely due to the change in how it operates since it was first introduced into the language. The most well known usage for auto is as a way to define a variable while letting the compiler determine what the type is supposed to be:

int anInt = 10
auto alsoAnInt = 20
static_assert(std::is_same_v<int, decltype(alsoAnInt)>)

In the above example the compiler determines from the value that is assigned to it, that alsoAnInt is in fact an int. The third line also introduces some important concepts which will be used quite extensively in a few moments: - static_assert : Asserts that a compile time value is true at compile time, If the assertion fails, the program will fail to build. - std::is_same_v : a compile time Boolean value evaluating to true if the types provided match. - decltype : A compile time function that returns the type of the value provided to it.

I would like you to throw away the notion that the auto keyword is used to make the compiler determine the type for a variable, and approach it with this alternative view: The auto keyword does not simply determine what the type of alsoAnInt is, it actually turns alsoAnInt into a template variable which is taking the type of the value provided as input. When looked at in this light, it becomes more clear how auto works in other parts of our program:

template<typename T>
T increment(T a) {
  return a+1;
}

auto incrementAuto(auto a) -> decltype(a) {
  return a+1;
}

The above two functions are entirely equivalent template functions. The only difference is the second function is using the auto keyword to produce templates. The parameter a is a template parameter. This function is also using a trailing return type -> decltype(a) this is required in order to constrain the return type to be the same as the parameter a.

Note that we would not be able to specify the return type prior to the parameter definitions because the parameter identifiers would not have been defined yet. In truth I have yet to find any use cases where this auto approach to templating is any more helpful than traditional templates, and often it just makes programs look needlessly more confusing than they actually are.

Variadic Templates…

Variadic templates (or parameter packs) were introduced in C++11, which both vastly improved the capability of templates, and made it vastly more difficult to understand.

Let’s take a simple example. We want to create a template function which creates a tuple then returns it:

template<typename... Args>
std::tuple<Args...> constructTuple(Args... args) {
    return std::tuple<Args...>(args...);
}

The ellipsis is a parameter pack expansion, this will expand the parameters out into what is effectively a comma seperated list. An example generation function would look as follows:

std::tuple<double, int, std::string> constructTuple(double args1, int args2, std::string args3) {
    return std::tuple<double, int, std::string>(args1, args2, args3);
}

Parameter expansion is a process that brings a great deal of confusion to many people. The confusion comes from attempting to work out how exactly its going to expand the parameter pack.

The key rule to remember is this: > The expression containing the parameter pack argument to the left of the ellipsis is what is going to be repeated for each template parameter.

So in the most basic example:

args... -> arg1, arg2, arg3

If the parameter pack is contained within another expression it will repeat the entire expression for each of the arguments:

std::forward<Args>(args)... -> std::forward<Args1>(args1), std::forward<Args2>(args2), std::forward<Args3>(args3)

The mix up with the example above is that people often write the ellipsis next to the parameter pack:

std::forward <Args...  > (args...  )
              |expands|   |expands|

The ellipsis expands the expression to the left of it so this would actually expand as:

std::forward<Args1, Args2, Args3>(args1, args2, args3);

Moving forward onto `std::forward`

Our previous examples used a standard library function which is quite important when working with templates. To discuss it we will need to delve into the concept of forwarding references.

template<typename T>  
struct A {  
    static void call(const T& t){ std::cout << "Calling l-value" << std::endl; }  
    static void call(T&& t){ std::cout << "Calling r-value" << std::endl; }  
};  
  
template<typename T>  
void callA(T&& t) {  
    A<std::decay_t<T>>::call(std::forward<T>(t));  
}

In the example above we may be forgiven for believing that the createA function only takes r-values as an input parameter (if you do not know the difference between what an l-value and r-value reference is, I encourage you to look that up now, there are plenty of resources that can give a much better explanation than I can), however the following calls to createA would suggest otherwise:

int i = 10;

createA(i);
createA(30);

Produces:

Calling l-value
Calling r-value

This is because when && is used against a template type, it is actually denoting a forwarding reference rather than an r-value reference. A forwarding reference will take on the type of reference which the input parameter is using, generating a new version of the template function in the process. The purpose of the std::forward function is to pass on that reference type further into the function call. If we didn’t use it the result of our program would be different:

template<typename T>
void callA(T&& t) {
    A<std::decay_t<T>>::call(t);
}


int i = 10;

createA(i);
createA(30);

Produces:

Calling l-value
Calling l-value

Why does it lose the reference type in this case? After all, the reference type on t will be the same? The key to understanding this can be found in looking at a normal r-value reference:

void rValCreateA(int&& t) {
    A<int>::call(t);
}
rValCreateA(30);

Produces

Calling l-value

In this case an r-value is placed in the parameter variable t, however t itself is actually a variable and is therefore an l-value. In order to pass it on as an r-value we would need to use std::move:

void rValCreateA(int&& t) {
    A<int>::call(std::move(t));
}
rValCreateA(30);

Produces

Calling r-value

std::forward is similar to std::move, but rather than just converting t to an r-value, it instead converts it back to the original reference given for T, allowing it to fit the most appropriate member function for A.

Advanced Techniques

With the possible exception of the std::forward function. What has been covered so far has been relatively vanilla and should cover the vast majority of your templating needs. What follows is some serious nonsense: You have been warned.

Recursive Variadic Templates

There will come a point when using a variadic template while simply expanding the parameter pack is not going to cut it. Let’s say we want to create a function which prints the values of a varying list of types:

printValues("hello"s, 10, "worlds"s, 10.5);

Produces

hello, 10, worlds, 10.5

There does not seem to be a way to create such a function using a conventional parameter pack expansion (I know someone will pipe up and say there is, to which I say be quiet and let me keep my examples simple). This is where template recursion comes in:

template<typename T>  
void printValues(T x)  
{  
    std::cout << x << std::endl;  
}  
  
template<typename T, typename... Ts>  
void printValues(T x, Ts... xs)  
{  
    std::cout << x << ", ";  
    printValues(xs...);  
}

So how does this monstrosity work? Consider our example call:

printValues("hello"s, 10, "worlds"s, 10.5);

This will call the template printValues<std::string, int, std::string, double> which will expand as:

void printValues<std::string, int, std::string, double>(
    std::string firtsArg, int furtherArgs1, std::string furtherArgs2, double furtherArgs3) {
    std::cout << firstArg << ", ";
    printValues(furtherArgs1, furtherArgs2, furtherArgs3);
}

printValues<std::string, int, std::string, double> is in turn calling printValues but this time with only 3 parameters, int, std::string, double. This will be deduced to be the template fuction printValues<int, std::string, double> and as such that will also have to be generates:

void printValues<int, std::string, double>(
    int firstArg, std::string furtherArgs1, double furtherArgs2) {
    std::cout << firstArg << ", ";
    printValues(furtherArgs1, furtherArgs2);
}

This carries on until eventually there is a call to printValues with just one parameter, in which case it will match against the other printValues function with just the one template parameter, and thus print a new line.

The power of recursive templates is immense, allowing us to do things in C++ that other languages would never be capable of replicating, but it comes at a cost. Every level of recursion creates a brand new instantiation of the template. Where the use of recursion is extensive, so too is the compile time and program size, so consider wisely whether you really want to take advantage of this feature.

Explicit Template Instantiation

Explicit template instantiation is a feature which initially seems quite simple, but goes much deeper than you might expect. At its most basic, the idea is this: given a template class or function, a specific different instantiation can be created for when a template type is equal to the type specified:

template<typename T>
struct is_int_type {
    constexpr static bool value = false;
};

struct is_int_type<int> {
    constexpr static bool value = true;
};

In the above template, when is_int_type is instantiated with any other type than int, value will be false. int however has an explicit template instantiation setting value to true, thus allowing us to determine whether the type of T is an int or not.

As I have said, this is a relatively simple feature on the face of it, but we can get much more complicated from here. Lets say that we want to write a struct that can determine whether a type is a map. std::map is itself a template type and thus surely we cannot create an explicit template instantiation for it right? Perhaps not…we can create a template explicit template instantiation though:

template<typename T>
struct is_map_type {
    constexpr static bool value = false;
};

template<typename Key, typename Value>
struct is_map_type<std::map<Key, Value>> {
    constexpr static bool value = true;
};

In this case, any type that is a std::map will bind to the explicit template instantiation by generating the explicit instantiation required. This feature can be particularly handy for discovering additional information about a type that we don’t initially have access to.

Let’s say we wanted to create a function which converts a tuple to a variant with the following signature:

/**
 * @tparam Tuple            The tuple to convert from
 * @tparam tuplePosition    The position in the tuple to get 
 *                          the value of the variant
 */
template<typename Tuple, int tuplePosition>
auto createVariant(Tuple t);

For an input type Tuple = std::tuple<int, double> we will produce an output type std::variant<int, double>. The problem is that in order to create the output type we need to be able to access the template parameters that were used on the original tuple. Well it just so happens that explicit template instantiation has the perfect solution for this:

template<typename Tuple>
struct convertToVariant;

template<typename... Args>
struct convertToVariant<std::tuple<Args...>> {
    using type = std::variant<Args...>;
}

This expands the tuple to place its parameters in to the Args parameter pack, and then places it into the variant type. This allows us to write out the function as follows:

/**
 * @tparam Tuple            The tuple to convert from
 * @tparam tuplePosition    The position in the tuple to get 
 *                          the value of the variant
 */
template<typename Tuple, int tuplePosition>
typename convertToVariant<Tuple>::type createVariant(Tuple t) {
    return std::get<tuplePosition>(t);
}

So I assume you’re now thinking that this must be the most complicated that explicit template instantiation can get…Well fear not. It. Gets. WORSE.

Template Template Types

convertToVariant is quite a clever structure, but its not very generic. What if I wanted to convert a variant back to a tuple, or a tuple to some other variadic template structure? We need to find a way to specify what we want to convert to and from. We can specify a template type in another template by using a template template type (is template even a word at this point?)

template<template <typename> typename M, typename T>
M<T> constructTemplate(T value) {
    return M<T>(value);
}

std::optional<int> opt10 = constructTemplate<optional>(10);

This function allows us to construct any template which takes one template type. The syntax of the template template type follows the same pattern as a normal template: - template<typename> typename M specifies a template type which takes one template parameter. - template<typename, typename> typename M specifies a template type which takes two template parameters. - template<typename...> typename M means a template type which takes any number of template types. Note that this does not have to mean that the type must take a variadic template, just that the number of parameters for M is not specified:

template<template<typename...> typename M, typename... Args>
M<Args...> constructTemplate() {
    return {};
}

constructTemplate<std::map, int, std::string>();

The above is valid because Args... expands to just two arguments which is the number of arguments which is required for std::map.

With this in mind we can get to work on our conversion function. We start initially with the struct signature:

template<typename From>
struct convertType;

From is our original template type and we will have to specify an explicit template instantiation in order to get its template arguments. In order to match against any template type we use a template template parameter:

template<template<typename...> typename From, typename... Args>
struct convertType<From<Args...>> {
}

Finally we need to specify the type we are going to. We’ll do this using a template type alias:

template<template<typename...> typename From, typename... Args>
struct convertType<From<Args...>> {
    template<template<typename...> typename To>
    using to = To<Args...>;
}

And voila! We have a completely generic type converter:

static_assert(std::is_same_v<std::tuple<int, std::string>, convertType<std::variant<int, std::string>::to<std::tuple>>);

Other Key Concepts

`std::decay_t`

std::decay_t is quite a handy type modifier to use when making your own templates. Consider the following code:

template<typename T>
class Maybe
{
public:
	Maybe(std::optional<T> value)
		: value_{std::move(value)}
	{ }

private:
	std::optional<T> value_;
}

template<typename T>
Maybe<T> makeMaybe(T&& value)
{
	return Maybe(std::make_optional(std::forward<T>(value)));
}


int a = 10;
int& b = a;

auto box = makeMaybe(b);

What is the type of box here? One might hope that the type is Maybe<int> and that value is its own copy of the integer. This however is not the case. Templates bind to the most specific type it possibly can. In this case where the type of b is int&, the type of box becomes Maybe<int&>. If we want to ensure Maybe always takes a copy regardless of what has been passed in, we need to decay the type of T down to its most basic form:

template<typename T>
Maybe<std::decay_t<T>> makeMaybe(T&& value)
{
	return Maybe(std::make_optional(std::forward<T>(value)));
}

Where the type of T is int&, the type of std::decay_t<T> is int allowing value to be a copy of the passed in value. A full list of all the qualifiers that std::decay_t removes from a type can be found in the cppreference documentation for the modifier.

`std::in_place_type`

This is a rarely used, but very handy struct in the standard library. The idea behind this struct is to allow the programmer to explicitly specify a type for a template without explicitly specifying a template parameter.

This becomes important for allowing the type system to implicitly determine the template types for a template class when explicit instantiation is not possible. The most common example for this would be std::variant :

std::variant<std::string, int> value = std::string("Hello");

The above example contains a problem. In writing the string value to the variant we first need to construct a temporary r-value string and then move it onto the variant. In some cases we need to deal with types that cannot be moved, or we simply want to be more efficient with our object construction. It would be better if we were able to directly construct a string on the variant.

So how might we go about doing this on std::variant? We could for example have a constructor which takes the type we want as a template parameter alongside a parameter pack for the construction parameters:

template<typename... VArgs>
class variant
{
	template<typename T, typename... TArgs>
	variant(TArgs&&... args)
		: value_{new T(std::forward<TArgs>(args)...)}
	{}
};

This definition of the variant constructor has a fundamental flaw. The template T would need to be explicitly specified in order for the correct constructor to be generated. But constructors are special functions. They can only have implicitly instantiated template parameters. This is because the explicit template syntax is reserved for the type’s template parameters on constructors:

std::variant<std::string, int>("Hello");
//          |----------------|
//          ^ This refers to VArgs
//          T and TArgs cannot be explicitly defined, they
//          must be implicit.

To get around this restriction we provide a new in_place_type parameter at the front of the constructor:

template<typename T, typename... TArgs>
variant(std::in_place_type_t<T>, TArgs&&... args);

Now we can directly place the string onto a variant:

std::variant<std::string, int> value(std::in_place_type<std::string>, "Hello");

Here the in_place value allows the type system to deduce the type for T and therefore construct a string in place on the variant without a move. This feature becomes especially helpful when placing variant values into containers such as sets and maps. In cases where a map’s value is not default constructable, the only way to place into a map is using try_emplace which requires implicit template instantiation to construct these values properly:

std::map<int, std::variant<std::string, int>> m;
m.try_emplace(10, std::in_place<std::string>, "Hello");

Template Instantiation in Implementation Files

As powerful as templates are, one of the major drawbacks is the compile time complexity of generating them. This problem gets exacerbated by the fact that each compilation unit will perform its own template instantiation. So even if instantiation for a specific version of a template has already occurred, use of the same template in a different compilation unit will lead to the same template needlessly being generated twice. One approach to solving this is to forward declare a template:

template<typename T> T add(T a, T b);

int sum = add(10, 20);

Here, when a file uses the add function, it will not attempt to generate the add function, it will simply type check that how it has been used is valid to the given forward declaration. This will lead to the compilation time for that unit to be much faster. If we do want to use a forward declaration however, we must make sure that there is some other part of the program which does actually perform the instantiation for us:

template<typename T> T add (T a, T b) { return a + b; }

template int add(int a, int b);
template double add(double a, double b);

This will generate int and double versions of the add function and allow for forward declarations to be used in the rest of the program where these instantiations are used.

There are limitations to what we can do with this feature. Firstly, all required instantiations must be known in advance, if the template is designed to be some generic procedure for which any type could be expected to be used, explicitly defining a limited number of types is not going to work. Secondly, as is the case with any other forward declaration, if the piece of code relies on part of the implementation of the generated function/object, then it will not be able to compile the program:

template<typename T> Runner;

Runner<int> r;
r.run(); // Attempting to call run on incomplete type

Unfortunately as it stands at the moment, the best way to reduce the compilation times for templates is simply to not use them.

In my last post on C++ I spoke of my appreciation of C++’ no holes barred approach to openness for the developer. There is no greater example of C++’ expressive capability than it’s templating feature which is unrivalled by almost any other language’s meta-programming capabilities. As the feature matures with the introduction of concepts and potential improvements to build times using modules, it is my hope that this once dreaded aspect of the language gets the appreciation that it so desperately deserves.

Starting things simple: Template Parameters

Template Argument Deduction

Templates Vs. Generics

The Concept of Concepts

Without Concepts

With Concepts

The auto Keyword

Variadic Templates…

Moving forward onto std::forward

Advanced Techniques

Recursive Variadic Templates

Explicit Template Instantiation

Template Template Types

Other Key Concepts

std::decay_t

std::in_place_type

Template Instantiation in Implementation Files

The `auto` Keyword

Moving forward onto `std::forward`

`std::decay_t`

`std::in_place_type`