ICS 46 Spring 2022, Notes and Examples: Templates

Background

In C++, the demands of the static type system sometimes seem to warrant copying and pasting functions or classes whose only differences are the types of their arguments, member functions, or member variables. Consider, for example, a simple three-line swap function that swaps a pair of integers.

void myswap(int& a, int& b) noexcept
{
    int temp = a;
    a = b;
    b = temp;
}

This function works wonderfully for two integers, but doesn't work at all for values of any other type. But when you consider what you'd have to do to swap two doubles or two strings or two whatevers, you realize that it could be done with exactly the same code, with only the word int changed to something else in each place where it occurs. For example, a version of myswap that swaps two doubles instead of two ints might look like this.

void myswap(double& a, double& b) noexcept
{
    double temp = a;
    a = b;
    b = temp;
}

Because C++ allows function overloading (i.e., two functions with the same name, differentiated by the types of its arguments and/or return value), it will be legal to have both of these functions in the same program, and the compiler will dutifully follow its overload resolution rules to determine which version to call in which circumstance. In fact, you could have ten, twenty, or a hundred of these functions that coexist, all with the same names and differing only in the types of their arguments and temporary variable.

But why should we have to write the same function over and over again? Wouldn't it be better if we could just write the function once, then tell the compiler how to convert it from one version to another based on the types in use?

That's what function templates let you do. They let you define the blueprint for an infinite set of possible functions, where you specify the ways that the different functions in the set would differ from each other. In our case, we might like to write a function template that demonstrates how to generate myswap implementations for each possible type of value I might want to swap.

Similarly, we might have a set of similar classes that differ from each other only with respect to one or more types used throughout the class. Data structure implementations like std::vector are a good example of this; C++ doesn't have a (particularly usable) notion of "Any type can go here," so a vector containing strings is a different type from a vector containing ints. But rather than requiring a separate implementation of std::vector for every different type of element we might like to store in one, std::vector is instead a class template, which is a blueprint for an infinite set of possible classes, in which we describe how the classes in the set differ from one another.

The devil, as they say, lies in the details, but the idea is a simple one and the need is clear. Let's talk about how to do this properly in C++.

Function templates

Writing a function template

Writing a function template is actually quite simple. Whenever we want to write a template, we begin with the word template, followed by a set of template parameters (which are usually, but not always, types). After this, we write a function in just the same way we always write them, except that we use the names of the template parameters to indicate the ways that different functions generated from our template are different.

So, for example, if we wanted to write our myswap function as a function template, we would write this:

template <typename T>
void myswap(T& t1, T& t2)
{
    T temp = t1;
    t1 = t2;
    t2 = temp;
}

The word template here, preceding what otherwise looks like a function definition, means that we've written a function template. There isn't one myswap function; there is a potentially infinite set of them, which differ in terms of the template's parameters. In this case, there is one parameter: the type of values being swapped. The keyword typename establishes that the first parameter is a type — as opposed to something else, like an int constant — and T, in this case, is a name used throughout the function to describe that type.

You may have noticed that I left the noexcept specifier out of our function template's signature, even though I included it in my original two examples of implementing myswap functions for integers and doubles. This was not an accident. Depending on the type of T, myswap<T> might not be able to guarantee that it doesn't throw an exception. For example, it T is int or double, it will never throw; if T is std::string (which can perform dynamic allocation when you create one or copy one), it might. So if we're going to say definitively whether our function template is either noexcept or not, it's clearly not. (If we're willing to say it more carefully, we can get the best of both words; more on that in a little while.)

Instantiating a function template

When you call a function template in a source file, the C++ compiler stops to decide whether it's seen that use of the function template before. For example, imagine this source file:

void foo()
{
    int i = 3;
    int j = 4;
    myswap(i, j);
}

At the point where myswap has been called, the compiler realizes that this particular call to myswap would only make sense if the type T in the template was int, because the parameters being passed are both of type int. (Standard C++ overloading rules apply, so exact matches are favored over inexact ones, while the fact that the parameters are passed by reference dramatically reduces the set of possibilities.) If the compiler can't make a concrete determination, we would have to specify the template argument ourselves, but this turns out to be unnecessary for many function templates:

void foo()
{
    int i = 3;
    int j = 4;
    myswap<int>(i, j);   // legal, but unnecessary in many cases
}

So we now need the compiler to instantiate the template, which is to say that we need it to generate an actual function from it, where T = int. A function template describes a potentially infinite set of functions, but none of those functions exists until we instantiate the template (i.e., we call the function with a particular set of template parameters for the first time).

So, at this point, we need the compiler to actually compile the myswap function template with T = int. That means the entire body of the myswap function template — not just its declaration, but its definition — needs to be available to the compiler. For that reason, we generally implement function templates in header files as opposed to source files — except when we want to write a function template that is "local" to a particular source file.

Note that this means that there may ultimately be multiple definitions of the same function template in separate source files (e.g., if two source files make calls to myswap<int>). Fortunately, C++ linkers allow this for templates and are able to handle it for us, which is necessary for the template feature in C++ to actually work.

Constraints on template parameters

As written, the only explicit constraint on the type parameter T in myswap is that it's some type. However, there are constraints on what T is allowed to be, implicitly arising from the things we do with T's inside of the function. As we look at the function, we can see that we do the following things with T's:

The line T temp = t1; invokes T's copy constructor.
The lines t1 = t2; and t2 = temp; invoke T's assignment operator.
Since temp is statically-allocated, T's destructor will be called on temp when the function ends.

It may sound strange, but there are types in C++ that disallow some or all of these features. For example, we could declare the following class X with neither a copy constructor nor an assignment operator.

class X
{
public:
    X();
    X(const X& x) = delete;
    X& operator=(const X& x) = delete;
};

It would now be impossible to call myswap and pass it two X's, because swapping them requires both a copy constructor and an assignment operator.

The power of conditional noexcept

We saw previously that you can declare the noexcept specifier on a function conditionally, by writing an expression that can be evaluated at compile time to determine whether or not a function is noexcept. We also saw the noexcept operator, which can evaluate whether or not an expression is noexcept (i.e., whether or not it's true that it is declared not to throw an exception). Putting these features together, we can specify precisely when our myswap function template will be noexcept.

First of all, we need to understand what we're trying to say. Under what conditions will a particular instantiation of our myswap function template be noexcept? Take a look at what the function does.

The first line of the body copy-constructs a T object. This would need to be something that would be guaranteed not to throw.
The second and third lines of the body assign one T object to another. This would also need to be something that would be guaranteed not to throw.

The noexcept operator will let you ask whether something cannot throw an exception without actually performing the operation at run-time. Used in a function's signature, we can even use the function's parameters if needed, because we're really just asking questions about potential uses of them; we need not worry about whether there would be side effects of the expressions, because the expressions won't be executed at run time, anyway. Given that, we could write our function template this way:

template <typename T>
void myswap(T& t1, T& t2)
    noexcept(noexcept(T{t1}) && noexcept(t1 = t2))
{
    T temp = t1;
    t1 = t2;
    t2 = temp;
}

The reason we're saying noexcept inside of noexcept is because there are two different uses of this keyword:

The outermost noexcept is being used as the noexcept specifier; we're saying "These are the conditions under which this function template cannot throw an exception."
The two inner noexcept occurrences are the noexcept operator; in those cases, we're saying to the compiler, "Figure out whether it's true that these two expressions cannot throw."

So, all in all, we've said "The myswap function template is guaranteed not to throw an exception when it is guaranteed that copy-constructing a T object from t1 will not throw and when it is guaranteed that assigning t2 into t1 will not throw."

On the one hand, you might react to this with disdain: It seems a complicated thing to have to say. And, in truth, you wouldn't likely find yourself writing this kind of thing in the upper levels of application software. Particularly when you're writing libraries, though — and this is something we're focused on in this course, in the sense that data structures are foundational things that we build programs on top of — this is the kind of thing where focusing your energies benefits everyone. The implementers of the C++ Standard Library, for example, have gone to a lot of trouble in recent years to nail down noexcept specifiers throughout, but that's because the benefit is that everyone who uses the C++ Standard Library is better off: The code says what it means and means what it says, and (perhaps even more importantly) large-scale performance optimizations become available that wouldn't be otherwise.

Note, too, that the C++ Standard Library also provides compact, readable ways to say what we just said, as well. For example, if you include a header called <type_traits>, which provides tools for asking questions about types, you could instead write the function's signature like this:

template <typename T>
void myswap(T& t1, T& t2)
    noexcept(std::is_nothrow_copy_constructible_v<T> &&
             std::is_nothrow_assignable_v<T>)

Class templates

Consider again what classes are in C++. They are a blueprint for a kind of object, specifying what information objects of that class store and how objects of that class behave. As you've no doubt seen previously, C++ has an aggressive static type system, requiring classes to be pretty specific about the types of data their objects work with. This is with good reason: C++ compilers, given a class declaration, need to make decisions about things like object layout and the sizes of the parameters being passed to functions, all of which require knowing the specifics of the types involved.

It doesn't take much thinking to realize that classes might benefit from templates the same way that functions do. C++ provides us the ability to write class templates, which are a solution to a similar kind of problem. A class template is a blueprint for a set of classes, each of which becomes a distinct, separate type. The instantiations of a class template are similar in the sense that they all contain the same code (with uses of template parameters replaced by something concrete), but they aren't related by inheritance — or in any other way, unless you explicitly set them up that way — and are fundamentally incompatible with each other.

Like function templates, class templates take a set of template parameters that describe the things that make one instantiation of the template different from another. Most of the time, these are types, though, once in a while, constant values (such as ints) are used instead. Data structure implementations are a common example where you see class templates used, because how a data structure works is often quite separate from the kinds of objects stored within it. std::vector in the C++ Standard Library is a class template for exactly this reason; a vector doesn't behave differently if it stores int objects than it does if it stores std::string objects or Person objects or even pointers. But it does allocate a different amount of memory for each cell in its underlying array, each kind of vector allows only correctly-typed values to be added into it, and so on. So std::vector is a class template, with a template parameter that specifies what type of value will be stored in the vector. A std::vector<int> is a vector that stores integers; a std::vector<std::string> is a vector that stores strings; and so on. And while they're similar, they're not compatible; you can't assign a std::vector<std::string> into a std::vector<int>, or pass one as a parameter to a function expecting the other.

Writing a class template

We write class templates in the same way that we write function templates: We begin with the word template, followed by the template's parameters listed between angle brackets and separated by commas. So, for example, a class like the std::vector class in the standard library might look something like this:

template <typename ElementType>
class Vector
{
    ...
};

where ElementType is a parameter used to describe the type of element being stored in a particular Vector. Within the class declaration, we would use ElementType whenever we want to specify "The type of element being stored in this Vector," rather than using something specific like int or std::string.

Instantiating a class template

Every time the compiler sees a new use of a class template — with a set of template parameters that hasn't been used before in that source file — it generates a new class on the fly, including only the member functions that are actually being used on an object of that class (which saves code size and also offers some flexibility, as we'll see later). As with function templates, all of the code needs to be generated by the compiler when used, so we typically implement class templates, including definitions of member functions, in header files, so all of the code will be available to the compiler at the point where the class template is instantiated.

As with function templates, there is no way to explicitly limit what the type ElementType is allowed to be, though there is an implicit limitation brought about by the things you do to ElementType objects inside the class. For example, if we wrote this code in a member function in our Vector class:

ElementType e;
e.foo();

then we'd be introducing three constraints on ElementType:

It must be possible to default-construct an ElementType (i.e., ElementType has a constructor that takes no parameters).
ElementType has a destructor — a necessity because the statically-allocated variable e will be destroyed when it falls out of scope.
ElementType must have a member function foo that takes no parameters, though there is no limitation on what its return type is (since we're not doing anything with the return value).

This particular code example

This code example demonstrates how to write a class template, and how to write function templates that implement member functions of a class template. The example is of a classs template called Point, which represents a point in a three-dimensional space. A point is made up of three coordinates (x, y, and z), but the types of these coordinates is flexible; any given point can have coordinates of different types (e.g., double, int, etc.). So Point is a class template with one parameter, CoordinateType, which specifies the type of each coordinate.