[History of C++] Templates: from C-style macros to concepts

Author: Chloé Lourseyre
Editor: Peter Fordham

Introduction: Parametrized types

Templates are the C++ feature (or group of features, as the word is used in several contexts) that implement parametrized types.

The notion of a parametrized type is very important in modern programming and consists of using a type as a parameter of a feature, which means you can use that feature with different types, the same way you use a feature with different values.

The most simple example is with std::vector. When you declare a vector as such: std::vector<int> foo;, the type int is parametrized. You could have put another type, like double, void* a user-defined class or even another list instead of int.

It is a way to achieve metaprogramming, a programming technique that aims to apply programs on other program data.

For the rest of the article I will use the word “template” to refer to either the notion of parametrized types or the C++ template implementation (unless I want to explicitly make the distinction).

Before Templates

Before the creation of template, in early C++, people still had to writer C-style macros to emulate templates.

One way of doing this is like that:

foobar.h

void foobar(FOOBAR_TYPE my_val);

foobar.cpp

void foobar(FOOBAR_TYPE my_val)
{
    // do stuff
}

main.cpp

#define FOOBAR_TYPE int
#include "foobar.h"
#include "foobar.cpp" // Only do this in a source file
#undef FOOBAR_TYPE

#define FOOBAR_TYPE double
#include "foobar.h"
#include "foobar.cpp" // Only do this in a source file
#undef FOOBAR_TYPE

int main()
{
    int toto = 42;
    double tata = 84;
    foobar(toto);
    foobar(tata);
}

Don’t do this at home, though! This is not something we ought to do nowadays (especially the #include "foobar.cpp" part). Also note that that code takes advantage of function overloading and therefore does not compile in C.

With our modern eyes, this seems very limited and error-prone. But the interesting thing is that even before C++ templates were implemented in early C++ design teams could use the macro approach to gain experience with them.

Timing

Templates were introduced in Release 3.0 of the language, in October 1991. In The Design and Evolution of C++, Stroustrup reveals that it was a mistake to introduce this feature so late, and in retrospect it would have been better to do so in Release 2.0 (June, 1989) at the expense of less important features, like multiple inheritance:

Also, adding multiple inheritance in Release 2.0 was a mistake. Multiple inheritance belongs in C++, but is far less important than parameterized types — and to some people, parameterized types are again less important than exception handling.

Bjarne Stroustrup, The Design and Evolution of C++, chapter 12: Multiple Inheritance, §1 – Introduction

From today, it is clear that Stroustrup was right and that templates have impacted the scenery of C++ much, much more than multiple inheritance.

This addition came late because it was really time-consuming to explore the design and implementation issues.

Needs and goals

The original need for templates was to express parametrization of container classes. But to do that job, macros were too limited. They fail to obey scope and type rules and don’t interact well with tools (especially debuggers). Before C++ templates, it was very hard to maintain code that used parametrized types, you needed the lowest level of abstraction and you needed to add each parametrized type manually.

The first concerns regarding templates were whether templates would be easy to use and templated objects be as easy to use as hand-coded objects, whether the compilation and linking speed would be significantly impacted and whether they would be portable.

The build process of templates

Syntax

The angle brackets

Designing the syntax of a feature is not an easy job, and requires extensive discussion and refinement.

The choice of the brackets <...> for the template parameter was made because, even though parentheses would have been easier to parse, they are overused in C++ and brackets are (empirically) more pleasant for a human reader.

However, this causes a problem for nested brackets, such as:

List<List<int>> a;

In the code above, in earlier C++, you would get a compilation error. The closing >> are seen by the compiler as operator>> and not two closing brackets.

A lexical trick was added later in the language (in C++14¹) so that this was not seen as a syntax error anymore.

The template argument

Initially, the template argument would have been placed just after the object name:

class Foo<class T>
{
    // ...
};

However, that caused two major issues:

• It is a bit too hard to read for parsers and humans. Since the template syntax in nested within the syntax of the class, it is a bit tough to detect.
• In the case of function templates, the templated type can be used before it is declared. For instance, in this declaraction: T at<class T>(const std::vector<T>& v, size_t index) { return v[index]; }, since T is the return type it is parsed before we even know it is a template parameter.

Both issues are resolved if we put the template argument before the declaration, and this is what was done:

template<class T> class Foo
{
    // ...
};

template<class T> T at(const std::vector<T>& v, size_t index) { return v[index]; }

Constraints of template parameters

In C++, the constraints on template arguments are implicit².

The dilemma over if the constraints should be explicit in the template argument (like below) or if they should be deduced from the usage occurred. An example of such explicit constraint would be like this:

template < class T {
        int operator==(const T&, const T&); 
        T& operator=(const T&);
        bool operator<(const T&, int);
    };
>
class Foo {
    // ...
};

But this was judged to be way to verbose to be readable and it would require way more templates for the same number of features. Moreover, this kind of over-restricts the class you’re implementing, giving constraints that excludes some implementations that would have been perfectly fine and correct without them³.

However, having explicit constraints was not off the table, but it is just that function type is a too specific way to express this.

This could have been achieved through derivation: by specifying that your templated type must derive from another class, you can have explicit constraint on this type.

template <class T>
class TBase {
    int operator==(const T&, const T&); 
    T& operator=(const T&);
    bool operator<(const T&, int);
};

template <class T : TBase>
class Foo {
    // ...
};

However this generates more issues. The programmers are, because of that, encouraged to express constraints as classes, leading to an overuse of inheritance. There is a loss in expressivity and semantics, because “T must have be comparable to an int” become “T must inherit from TBase”. In addition to that, you could not express constraints on type that can’t have a base class, like ints and doubles.

This is mainly why we did not have explicit constraints on template parameters in C++⁴ for a long time.

However, the discussion on template constraints was revived in the late 2010s and a new notion made its appearance in C++20: Concepts (c.f. Modern evolutions – Concepts below).

Templated object generation

How templates are compiled is very simple: for every set of template parameters that is used on the templated object, the compiler will generate a implementation of this object using explicitly those parameters.

So, writting this:

template <class T> class Foo { /* ... do things with T ... */ };
template <class T, class U> class Bar { /* ... do things with T  and U... */ };

Foo<int> foo1;
Foo<double> foo2;
Bar<int, int> bar1;
Bar<int, double> bar2;
Bar<double, double> bar3;
Bar< Foo<int>, Foo<long> > bar4;

Is the same thing as writing this:

class Foo_int { /* ... do things with int ... */ };
class Foo_double { /* ... do things with double ... */ };
class Foo_long { /* ... do things with long ... */ };
class Bar_int_int { /* ... do things with int  and int... */ };
class Bar_int_double { /* ... do things with int  and double... */ };
class Bar_double_double { /* ... do things with double  and double... */ };
class Bar_Foo_int_Foo_long { /* ... do things with Foo_int  and Foo_long... */ };

Foo_int foo1;
Foo_double foo2;
Bar_int_int bar1;
Bar_int_double bar2;
Bar_double_double bar3;
Bar_Foo_int_Foo_long bar4;

… only it is more verbose (even more in real code) and less readable.

Class templates

Templates were imagined and designed primarily for classes, mostly to allow for the implementation of standard containers. They were designed to be as simple to use as standard classes and as efficient as macros. These two facts were decided so that low-level arrays could be abandoned when they were not specifically needed (in low-level programming) and that templatized containers would be preferred in the higher levels.

In addition to type argument, template can take non-type argument, like this:

template <class T, int Size>
class MyContainer {
    T m_collection[Size];
    int m_size;
public:
    MyContainer(): m_size(Size) {}
    // ...
};

This was introduced in order to allow for static sizing of containers. Carrying the size in the type information make the implementations more efficient, because you don’t have to track it separately and you don’t loose it through pointer decay as you do with C-style arrays.

class Foo;

int main()
{
    Foo[700] fooTable; // low-level container
    MyContainer<Foo, 700> fooCnt; // high-level container, as efficient as the previous one
}

Function templates

The idea of function templates comes from the need of having templated class methods and from the idea that function templates are in the logical extension of class templates.

Today, the most obvious examples we can provide are the STL algorithms (std::find(), std::find_first_of() , std::merge(), etc.). Though at its creation, the STL algorithms did not exist, it was these kind of functions that inspired function templates (the most symbolic being sort()).

The main issue with function templates was deducing the function template arguments and return type, so we don’t have to explicitly specify them at each function call-site.

In this context, it has been decided that template argument could be deduced (when possible) and specified (when needed). This was extremely useful to specify return values, because they can not always be deduced, such as in this example:

template <class TTo, class TFrom>
TTo convert(TFrom val)
{
    return val;
}

int main()
{
    int val = 4;
    convert(val); // Error: TTo is ambiguous
    convert<double, int>(val) // Correct: TTo is double; TFrom is int
    convert<double>(val) // Correct: TTo is double; TFrom is int; 
}

As you can see on line 12, the trailing template arguments can be omitted as can be trailing function arguments (when they have a default value).

The way templates are generated (see section Templated objects generation section above) works perfectly fine with function overloading. The only subtlety is when there are both non-templated and templated overloads of a function. Then, the non-templated overload is called if there is a perfect match, else it will be the templated overload that will be called if there is a perfect match possible, else we apply ordinary overload resolution.

Template instantiation

At the beginning, explicit template instantiation was not intended. It was because it would create hard issues in some specific circumstances, like if two unrelated parts of a program both request the same instantiation of a templated object, which would have to be done without code replication and without disturbing dynamic linking. This is why implicit templates instantiation was preferred at first.

The first automatic implementation for template instantiation was as follows: when the linker is run, it searches for missing template instantiations. If found, the compiler is invoked again to produce the missing code. This process is repeated until there are no more missing template instantiations.

However, this process had several problems, one of them being very poor compile and link performance.

It is to mitigate this that optional explicit template instantiation is allowed.

The development of the template instantiation process had many more issues, such as the point of instantiation (the “name problem”, i.e. pinpointing which declaration the names used in a template definition refer to), dependencies problems, solving ambiguities, etc. Discussing all of these would require a dedicated article.

Modern evolutions

Templates are a feature that continued to evolve even as we entered the Modern C++ era (beginning with C++11).

Variadic templates

Variadic templates are templates that have at least one parameter pack. In C++, a parameter pack is a way to say that a function or a template has a variable number of arguments.

For example, the following function declaration uses a parameter pack:

void foobar(int args...);

And can be called with any number of argument (greater than one).

foobar(1);
foobar(42, 666);
foobar(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16);

Variadic templates allows you to have a variable number of arguments, that can be of different types.

With that, we can write more generic functions. For instance:

#include <iostream>

struct MyLogger 
{
    static int log_counter;

    template<typename THead>
    static void log(const THead& h)
    {
        std::cout << "[" << (log_counter++) << "] " << h << std::endl;
    }

    template<typename THead, typename ...TTail>
    static void log(const THead& h, const TTail& ...t)
    {
        log(h);
        log(t...);
    }
};

int MyLogger::log_counter = 0;

int main()
{
    MyLogger::log(1,2,3,"FOO");
    MyLogger::log('f', 4.2);
}

This generates the following output:

[0] 1
[1] 2
[2] 3
[3] FOO
[4] f
[5] 4.2

It is safe to assume that a significant motivation for the addition variadic templates and parameter packs was to be able to allow the implementation more generic functions, even if it may lead to voluminous generated code (for instance, in the previous example, the MyLogger class has 8 instantiations of the function log⁵).

Full details are available here: Parameter pack(since C++11) – cppreference.com.

Concepts

Concepts are a C++20 feature that aims to give the developer a way to declare constraints over template parameters. This leads to clearer code (with a higher level of abstraction) and clearer error message (if any).

For instance, here is a concept declaration:

template<typename T_>
concept Addable = requires(T_ a, T_ b)
{
    a + b;
};

And here are example of its usage:

template<typename T_>
requires Addable<T_>
T_ foo(T_ a, T_ b);

template<typename T_>
T_ bar(T_ a, T_ b) requires Addable<T_>;

auto l = []<typename T_> requires Addable<T_> (T_ a, T_ b) {};

Before that, template-related error were barely readable. Concepts were a highly anticipated feature of C++20.

A good overview of concepts can be found on Oleksandr Koval’s blog: All C++20 core language features with examples | Oleksandr Koval’s blog (oleksandrkvl.github.io)

Deduction guides

Template deduction guides are a C++17 feature and are patterns associated with a templated object that tell the compiler how to translate a set of parameter (and their types) into template arguments.

For instance:

template<typename T_>
struct Foo
{
  T_ t;
};
 
Foo(const char *) -> Foo<std::string>;
 
Foo foo{"A String"};

In this code, the object foo is a Foo<std::string> and not a Foo<const char*>, and thus foo.t is a std::string. Thanks to the deduction guide, the compiler understand that3 when we use a const char*, we want to use the std::string instantiation of the template.

This is peculiarly useful for object such as vectors, which can have this kind of constructor:

template<typename Iterator> vector(Iterator b, Iterator e) -> vector<typename std::iterator_traits<Iterator>::value_type>;

This way, if we call the vector constructor with an iterator, the compiler will be able to deduce the templated parameter of the vector.

Substitution Failure Is Not An Error

Substitution Failure Is Not An Error, SFINAE for short, is a rule that applies during template overloaded function resolution.

It basically means that if the (deduced or explicitly specified) type for the template parameter fails, the specialization is discarded instead of causing a compile error.

For instance, take the following code:

struct Foo {};
struct Bar { Bar(Foo){} }; // Bar can be created from Foo
 
template <class T>
auto f(T a, T b) -> decltype(a+b); // 1st overload
 
Foo f(Bar, Bar);  // 2nd overload
 
Foo a, b;
Foo x3 = f(a, b);

Instinctively, we could think that this is the first overload that is called on the highlighted line (because the template instantiation using Foo as T is a better overload that the second one, which requires a conversion).

However, the expression (a+b) is ill-formed with Foo. Instead of generating an error, the overload auto f(Foo a, Foo b) -> decltype(a+b); is discarded. Thus, this is the other overload that is called, with an implicit conversion.

This kind of substitution occurs in all types used in the function type, all types used in the template parameter declarations. Since C++11, it also occurs in all expressions used in the function type and all expressions used in a template parameter declaration. Since C++20, it also occurs in all expressions used in the explicit specifier.

The full documentation about SFINAE can be found here: SFINAE – cppreference.com.

Other features in C++20

Templates continue to evolve. Here are a small list of the C++20 templates feature I couldn’t fit in this article:

• Template parameter list for generic lambdas. Sometimes generic lambdas are too generic. C++20 allows to use familiar template function syntax to introduce type names directly.
• Class template argument deduction for aggregates. In C++17 to use aggregates with class template argument deduction we need explicit deduction guides, that’s unnecessary now.
• Class types in non-type template parameters. Non-type template parameters now can be of literal class types.
• Generalized non-type template parameters. Non-type template parameters are generalized to so-called structural types.
• Class template argument deduction for alias templates. Class template argument deduction works with type aliases now.

Exceptions and templates: two sides of the same coin

I did not talk about exceptions in this article, but for Stroustrup, exceptions and templates are complementary features:

To my mind, templates and exceptions are two sides of the same coin: templates allow a reduction in the number of run-time errors by extending the range of problems handled by static type checking; exceptions provide a mechanism for dealing with the remaining run-time errors. Templates make exception handling manageable by reducing the need for run-time error handling to the essential cases. Exceptions make general template-based libraries manageable by providing a way for such libraries to report errors.

Bjarne Stroustrup, The Design and Evolution of C++, chapter 15: Templates, §1 – Introduction

So, by design, templates and exception are closely intermingled, in addition to raising the level of abstraction for error-handling.

However, exception and templates (especially templates) have evolved greatly since then, so I think this may not be true anymore.

Wrapping up

In my opinion, templates are the biggest fish in the C++ metaphorical pond. We will never talk enough about them, and I suspect they will continue to evolve for decades.

This is so because in modern C++ one of the key idea is to write intentions instead of actions. We want higher levels of abstraction and more metaprogramming. It is only normal that template are at the hearts of the modern evolutions of the language.

Author: Chloé Lourseyre
Editor: Peter Fordham

Addenda

Sources

• The Design and Evolution Of C++ (Bjarne Stroustrup), 1994
• Sibling Rivalry: C and C++ (Bjarne Stroustrup), 2002
• A History of C++: 1979−1991 (Bjarne Stroustrup), 1993
• cppreference.com
• All C++20 core language features with examples | Oleksandr Koval’s blog (oleksandrkvl.github.io)

Notes

1. I managed to locate this change in the GCC compiler at release 6 (https://godbolt.org/z/vndGdd7Wh), suggesting that this indeed occurred with C++14. I managed to see the same thing with the clang compiler at release 6 (https://godbolt.org/z/ssfxvb4cM), proving this right.

2. This is called duck-typing, from the saying if it looks like a duck, swims like a duck and it quacks like a duck then it probably is a duck.

3. I have no concrete example to provide and I’m pretty much paraphrasing Stroustrup in his retrospection, but the idea is that by having user-defined constraints, you close some doors that you didn’t even know existed and that others could have exploited. I’ve done and seen very interesting things using templates, and the fact that the only constraint we have is that the templated code makes sense with their given parameters opens up as many possibilities as we can imagine.

4. There were other tries to imagine a way to specify constraints, but to no avail. More details in section §15.4 of Stroustrup: The Design and Evolution of C++.

5. These instantiations are (and according to the assembly – Compiler Explorer (godbolt.org)):

• log(int);
• log(char[4]);
• log(char);
• log(double);
• log(int,int,int,char[4]);
• log(int,int,char[4]);
• log(int,char[4]);
• log(char,double);