Each language feature is designed to help with a problem or task that developers face when using that language. The purpose of templates is to help us avoid writing repetitive code that only differs slightly.

To exemplify this, let's take the classical example of a max function. Such a function takes two numerical arguments and returns the largest of the two. We can easily implement this as follows:

int max(int const a, int const b)
{
   return a > b ? a : b;
}

This works pretty well, but as you can see, it will only work for values of the type int (or those that are convertible to int). What if we need the same function but with arguments of the type double? Then, we can overload this function (create a function with the same name but a different number or type of arguments) for the double type:

double max(double const a, double const b)
{
   return a > b ? a : b;
}

However, int and double are not the only numeric types. There is char, short, long, long and their unsigned counterparts, unsigned char, unsigned short, unsigned long, and unsigned long. There are also the types float and long double. And other types, such as int8_t, int16_t, int32_t, and int64_t. And there could be other types that can be compared, such as bigint, Matrix, point2d, and any user-defined type that overloads operator>. How can a general-purpose library provide a general-purpose function such as max for all these types? It can overload the function for all the built-in types and perhaps other library types but cannot do so for any user-defined type.

An alternative to overloading functions with different parameters is to use void* to pass arguments of different types. Keep in mind this is a bad practice and the following example is shown only as a possible alternative in a world without templates. However, for the sake of discussion, we can design a sorting function that will run the quick sort algorithm on an array of elements of any possible type that provides a strict weak ordering. The details of the quicksort algorithm can be looked up online, such as on Wikipedia at https://en.wikipedia.org/wiki/Quicksort.

The quicksort algorithm needs to compare and swap any two elements. However, since we don't know their type, the implementation cannot do this directly. The solution is to rely on callbacks, which are functions passed as arguments that will be invoked when necessary. A possible implementation can be as follows:

using swap_fn = void(*)(void*, int const, int const);
using compare_fn = bool(*)(void*, int const, int const);
int partition(void* arr, int const low, int const high, 
              compare_fn fcomp, swap_fn fswap)
{
   int i = low - 1;
   for (int j = low; j <= high - 1; j++)
   {
      if (fcomp(arr, j, high))
      {
         i++;
         fswap(arr, i, j);
      }
   }
   fswap(arr, i + 1, high);
   return i + 1;
}
void quicksort(void* arr, int const low, int const high, 
               compare_fn fcomp, swap_fn fswap)
{
   if (low < high)
   {
      int const pi = partition(arr, low, high, fcomp, 
         fswap);
      quicksort(arr, low, pi - 1, fcomp, fswap);
      quicksort(arr, pi + 1, high, fcomp, fswap);
   }
}

In order to invoke the quicksort function, we need to provide implementations for these comparisons and swapping functions for each type of array that we pass to the function. The following are implementations for the int type:

void swap_int(void* arr, int const i, int const j)
{
   int* iarr = (int*)arr;
   int t = iarr[i];
   iarr[i] = iarr[j];
   iarr[j] = t;
}
bool less_int(void* arr, int const i, int const j)
{
   int* iarr = (int*)arr;
   return iarr[i] <= iarr[j];
}

With all these defined, we can write code that sorts arrays of integers as follows:

int main()
{
   int arr[] = { 13, 1, 8, 3, 5, 2, 1 };
   int n = sizeof(arr) / sizeof(arr[0]);
   quicksort(arr, 0, n - 1, less_int, swap_int);
}

These examples focused on functions but the same problem applies to classes. Consider that you want to write a class that models a collection of numerical values that has variable size and stores the elements contiguously in memory. You could provide the following implementation (only the declaration is sketched here) for storing integers:

struct int_vector
{
   int_vector();
   size_t size() const;
   size_t capacity() const;
   bool empty() const;
   void clear();
   void resize(size_t const size);
   void push_back(int value);
   void pop_back();
   int at(size_t const index) const;
   int operator[](size_t const index) const;
private:
   int* data_;
   size_t size_;
   size_t capacity_;
};

This all looks good but the moment you need to store values of the type double, or std::string, or any user-defined type you'll have to write the same code, each time only changing the type of the elements. This is something nobody wants to do because it is repetitive work and because when something needs to change (such as adding a new feature or fixing a bug) you need to apply the same change in multiple places.

Lastly, a similar problem can be encountered, although less often, when you need to define variables. Let's consider the case of a variable that holds the new line character. You can declare it as follows:

constexpr char NewLine = '\n';

What if you need the same constant but for a different encoding, such as wide string literals, UTF-8, and so on? You can have multiple variables, having different names, such as in the following example:

constexpr wchar_t NewLineW = L'\n';
constexpr char8_t NewLineU8 = u8'\n';
constexpr char16_t NewLineU16 = u'\n';
constexpr char32_t NewLineU32 = U'\n';

Templates are a technique that allows developers to write blueprints that enable the compiler to generate all this repetitive code for us. In the following section, we will see how to transform the preceding snippets into C++ templates.

It is now time to see how templates are written in the C++ language. In this section, we will start with three simple examples, one for each of the snippets presented earlier.

A template version of the max function discussed previously would look as follows:

template <typename T>
T max(T const a, T const b)
{
   return a > b ? a : b;
}

You will notice here that the type name (such as int or double) has been replaced with T (which stands for type). T is called a type template parameter and is introduced with the syntax template<typename T> or typename<class T>. Keep in mind that T is a parameter, therefore it can have any name. We will learn more about template parameters in the next chapter.

At this point, this template that you put in the source code is only a blueprint. The compiler will generate code from it based on its use. More precisely, it will instantiate a function overload for each type the template is used with. Here is an example:

struct foo{};
int main()
{   
   foo f1, f2;
   max(1, 2);     // OK, compares ints
   max(1.0, 2.0); // OK, compares doubles
   max(f1, f2);   // Error, operator> not overloaded for 
                  // foo
}

In this snippet, we are first calling max with two integers, which is OK because operator> is available for the type int. This will generate an overload int max(int const a, int const b). Second, we are calling max with two doubles, which again is all right since operator> works for doubles. Therefore, the compiler will generate another overload, double max(double const a, double const b). However, the third call to max will generate a compiler error, because the foo type does not have the operator> overloaded.

Without getting into too many details at this point, it should be mentioned that the complete syntax for calling the max function is the following:

max<int>(1, 2);
max<double>(1.0, 2.0);
max<foo>(f1, f2);

The compiler is able to deduce the type of the template parameter, making it redundant to write it. There are cases, however, when that is not possible; in those situations, you need to specify the type explicitly, using this syntax.

The second example involving functions from the previous section, Understanding the need for templates, was the quicksort() implementation that dealt with void* arguments. The implementation can be easily transformed into a template version with very few changes. This is shown in the following snippet:

template <typename T>
void swap(T* a, T* b)
{
   T t = *a;
   *a = *b;
   *b = t;
}
template <typename T>
int partition(T arr[], int const low, int const high)
{
   T pivot = arr[high];
   int i = (low - 1);
   for (int j = low; j <= high - 1; j++)
   {
      if (arr[j] < pivot)
      {
         i++;
         swap(&arr[i], &arr[j]);
      }
   }
   swap(&arr[i + 1], &arr[high]);
   return i + 1;
}
template <typename T>
void quicksort(T arr[], int const low, int const high)
{
   if (low < high)
   {
      int const pi = partition(arr, low, high);
      quicksort(arr, low, pi - 1);
      quicksort(arr, pi + 1, high);
   }
}

The use of the quicksort function template is very similar to what we have seen earlier, except there is no need to pass pointers to callback functions:

int main()
{
   int arr[] = { 13, 1, 8, 3, 5, 2, 1 };
   int n = sizeof(arr) / sizeof(arr[0]);
   quicksort(arr, 0, n - 1);
}

The third example we looked at in the previous section was the vector class. A template version of it will look as follows:

template <typename T>
struct vector
{
   vector();
   size_t size() const;
   size_t capacity() const;
   bool empty() const;
   void clear();
   void resize(size_t const size);
   void push_back(T value);
   void pop_back();
   T at(size_t const index) const;
   T operator[](size_t const index) const;
private:
   T* data_;
   size_t size_;
   size_t capacity_;
};

As in the case of the max function, the changes are minimal. There is the template declaration on the line above the class and the type int of the elements has been replaced with the type template parameter T. This implementation can be used as follows:

int main()
{   
   vector<int> v;
   v.push_back(1);
   v.push_back(2);
}

One thing to notice here is that we have to specify the type of the elements when declaring the variable v, which is int in our snippet because the compiler would not be able to infer their type otherwise. There are cases when this is possible, in C++17, and this topic, called class template argument deduction, will be discussed in Chapter 4, Advanced Template Concepts.

The fourth and last example concerned the declaration of several variables when only the type was different. We could replace all those variables with a template, as shown in the following snippet:

template<typename T>
constexpr T NewLine = T('\n');

This template can be used as follows:

int main()
{
   std::wstring test = L"demo";
   test += NewLine<wchar_t>;
   std::wcout << test;
}

The examples in this section show that the syntax for declaring and using templates is the same whether they represent functions, classes, or variables. This leads us to the next section where we will discuss the types of templates and template terminology.

So far in this chapter, we have used the general term templates. However, there are four different terms describing the kind of templates we have written:

• Function template is the term used for a templated function. An example is the max template seen previously.
• Class template is the term used for a templated class (which can be defined either with the class, struct, or union keyword). An example is the vector class we wrote in the previous section.
• Variable template is the term used for templated variables, such as the NewLine template from the previous section.
• Alias template is the term used for templated type aliases. We will see examples for alias templates in the next chapter.

Templates are parameterized with one or more parameters (in the examples we have seen so far, there was a single parameter). These are called template parameters and can be of three categories:

• Type template parameters, such as in template<typename T>, where the parameter represents a type specified when the template is used.
• Non-type template parameters, such as in template<size_t N> or template<auto n>, where each parameter must have a structural type, which includes integral types, floating-point types (as for C++20), pointer types, enumeration types, lvalue reference types, and others.
• Template template parameters, such as in template<typename K, typename V, template<typename> typename C>, where the type of a parameter is another template.

Templates can be specialized by providing alternative implementations. These implementations can depend on the characteristics of the template parameters. The purpose of specialization is to enable optimizations or reduce code bloat. There are two forms of specialization:

• Partial specialization: This is an alternative implementation provided for only some of the template parameters.
• (Explicit) full specialization: This is a specialization of a template when all the template arguments are provided.

The process of generating code from a template by the compiler is called template instantiation. This happens by substituting the template arguments for the template parameters used in the definition of the template. For instance, in the example where we used vector<int>, the compiler substituted the int type in every place where T appeared.

Template instantiation can have two forms:

• Implicit instantiation: This occurs when the compiler instantiates a template due to its use in code. This happens only for those combinations or arguments that are in use. For instance, if the compiler encounters the use of vector<int> and vector<double>, it will instantiate the vector class template for the types int and double and nothing more.
• Explicit instantiation: This is a way to explicitly tell the compiler what instantiations of a template to create, even if those instantiations are not explicitly used in your code. This is useful, for instance, when creating library files, because uninstantiated templates are not put into object files. They also help reduce compile times and object sizes, in ways that we will see at a later time.

All the terms and topics mentioned in this section will be detailed in other chapters of the book. This section is intended as a short reference guide to template terminology. Keep in mind though that there are many other terms related to templates that will be introduced at the appropriate time.

Template metaprogramming is the C++ implementation of generic programming. This paradigm was first explored in the 1970s and the first major languages to support it were Ada and Eiffel in the first half of the 1980s. David Musser and Alexander Stepanov defined generic programming, in a paper called Generic Programming, in 1989, as follows:

Generic programming centers around the idea of abstracting from concrete, efficient algorithms to obtain generic algorithms that can be combined with different data representations to produce a wide variety of useful software.

This defines a paradigm of programming where algorithms are defined in terms of types that are specified later and instantiated based on their use.

Templates were not part of the initial C with Classes language developed by Bjarne Stroustrup. Stroustrup's first papers describing templates in C++ appeared in 1986, one year after the publication of his book, The C++ Programming Language, First Edition. Templates became available in the C++ language in 1990, before the ANSI and ISO C++ committees for standardization were founded.

In the early 1990s, Alexander Stepanov, David Musser, and Meng Lee experimented with the implementation in C++ of various generic concepts. This led to the first implementation of the Standard Template Library (STL). When the ANSI/ISO committee became aware of the library in 1994, it quickly added it to the drafted specifications. STL was standardized along with the C++ language in 1998 in what became known as C++98.

Newer versions of the C++ standard, collectively referred to as modern C++, have introduced various improvements to template metaprogramming. The following table lists them briefly:

Table 1.1

All these features, along with other aspects of template metaprogramming, will make the sole subject of this book and will be presented in detail in the following chapters. For now, let's see what the advantages and disadvantages are of using templates.

Before you start using templates, it's important to understand the benefits of using them as well as the disadvantages they may incur.

Let's start by pointing out the advantages:

• Templates help us avoid writing repetitive code.
• Templates foster the creation of generic libraries providing algorithms and types, such as the standard C++ library (sometimes incorrectly referred to as the STL), which can be used in many applications, regardless of their type.
• The use of templates can result in less and better code. For instance, using algorithms from the standard library can help write less code that is likely easier to understand and maintain and also probably more robust because of the effort put into the development and testing of these algorithms.

When it comes to disadvantages, the following are worth mentioning:

• The syntax is considered complex and cumbersome, although with a little practice this should not really pose a real hurdle in the development and use of templates.
• Compiler errors related to template code can often be long and cryptic, making it very hard to identify their cause. Newer versions of the C++ compilers have made progress in simplifying these kinds of errors, although they generally remain an important issue. The inclusion of concepts in the C++20 standard has been seen as an attempt, among others, to help provide better diagnostics for compiling errors.
• They increase the compilation times because they are implemented entirely in headers. Whenever a change to a template is made, all the translation units in which that header is included must be recompiled.
• Template libraries are provided as a collection of one or more headers that must be compiled together with the code that uses them.
• Another disadvantage that results from the implementation of templates in headers is that there is no information hiding. The entire template code is available in headers for anyone to read. Library developers often resort to the use of namespaces with names such as detail or details to contain code that is supposed to be internal for a library and should not be called directly by those using the library.
• They could be harder to validate since code that is not used is not instantiated by the compiler. It is, therefore, important that when writing unit tests, good code coverage must be ensured. This is especially the case for libraries.

Although the list of disadvantages may seem longer, the use of templates is not a bad thing or something to be avoided. On the contrary, templates are a powerful feature of the C++ language. Templates are not always properly understood and sometimes are misused or overused. However, the judicious use of templates has unquestionable advantages. This book will try to provide a better understanding of templates and their use.

This chapter introduced the concept of templates in the C++ programming language.

We started by learning about the problems for which the solution is the use of templates. We then saw how templates look with simple examples of function templates, class templates, and variable templates. We introduced the basic terminology for templates, which we will discuss more in the forthcoming chapters. Toward the end of the chapter, we saw a brief history of templates in the C++ programming language. We ended the chapter with a discussion on the advantages and disadvantages of using templates. All these topics will lead us to understand the next chapters better.

In the next chapter, we will explore the fundamentals of templates in C++.

1. Why do we need templates? What advantages do they provide?
2. How do you call a function that is a template? What about a class that is a template?
3. How many kinds of template parameters exist and what are they?
4. What is partial specialization? What about full specialization?
5. What are the main disadvantages of using templates?

• Generic Programming, David Musser, Alexander Stepanov, http://stepanovpapers.com/genprog.pdf
• A History of C++: 1979−1991, Bjarne Stroustrup, https://www.stroustrup.com/hopl2.pdf
• History of C++, https://en.cppreference.com/w/cpp/language/history
• Templates in C++ - Pros and Cons, Sergey Chepurin, https://www.codeproject.com/Articles/275063/Templates-in-Cplusplus-Pros-and-Cons