C++ Primer, Fifth Edition

Appearance

16.1. Defining a Template

Imagine that we want to write a function to compare two values and indicate whether the first is less than, equal to, or greater than the second. In practice, we’d want to define several such functions, each of which will compare values of a given type. Our first attempt might be to define several overloaded functions:

c++
// returns 0 if the values are equal, -1 if v1 is smaller, 1 if v2 is smaller
int compare(const string &v1, const string &v2)
{
    if (v1 < v2) return -1;
    if (v2 < v1) return 1;
    return 0;
}
int compare(const double &v1, const double &v2)
{
    if (v1 < v2) return -1;
    if (v2 < v1) return 1;
    return 0;
}

These functions are nearly identical: The only difference between them is the type of their parameters. The function body is the same in each function.

Having to repeat the body of the function for each type that we compare is tedious and error-prone. More importantly, we need to know when we write the program all the types that we might ever want to compare. This strategy cannot work if we want to be able to use the function on types that our users might supply.

16.1.1. Function Templates

Fundamental

Rather than defining a new function for each type, we can define a function template. A function template is a formula from which we can generate type-specific versions of that function. The template version of compare looks like

c++
template <typename T>
int compare(const T &v1, const T &v2)
{
    if (v1 < v2) return -1;
    if (v2 < v1) return 1;
    return 0;
}

A template definition starts with the keyword template followed by a template parameter list, which is a comma-separated list of one or more template parameters bracketed by the less-than (<) and greater-than (>) tokens.

INFO

In a template definition, the template parameter list cannot be empty.

The template parameter list acts much like a function parameter list. A function parameter list defines local variable(s) of a specified type but does not say how to initialize them. At run time, arguments are supplied that initialize the parameters.

Analogously, template parameters represent types or values used in the definition of a class or function. When we use a template, we specify—either implicitly or explicitly—template argument(s) to bind to the template parameter(s).

Our compare function declares one type parameter named T. Inside compare, we use the name T to refer to a type. Which actual typeT represents is determined at compile time based on how compare is used.

Instantiating a Function Template

When we call a function template, the compiler (ordinarily) uses the arguments of the call to deduce the template argument(s) for us. That is, when we call compare, the compiler uses the type of the arguments to determine what type to bind to the template parameter T. For example, in this call

c++
cout << compare(1, 0) << endl;       // T is int

the arguments have type int. The compiler will deduce int as the template argument and will bind that argument to the template parameter T.

The compiler uses the deduced template parameter(s) to instantiate a specific version of the function for us. When the compiler instantiates a template, it creates a new “instance” of the template using the actual template argument(s) in place of the corresponding template parameter(s). For example, given the calls

c++
// instantiates int compare(const int&, const int&)
cout << compare(1, 0) << endl;       // T is int
// instantiates int compare(const vector<int>&, const vector<int>&)
vector<int> vec1{1, 2, 3}, vec2{4, 5, 6};
cout << compare(vec1, vec2) << endl; // T is vector<int>

the compiler will instantiate two different versions of compare. For the first call, the compiler will write and compile a version of compare with T replaced by int:

c++
int compare(const int &v1, const int &v2)
{
    if (v1 < v2) return -1;
    if (v2 < v1) return 1;
    return 0;
}

For the second call, it will generate a version of compare with T replaced by vector<int>. These compiler-generated functions are generally referred to as an instantiation of the template.

Template Type Parameters

Our compare function has one template type parameter. In general, we can use a type parameter as a type specifier in the same way that we use a built-in or class type specifier. In particular, a type parameter can be used to name the return type or a function parameter type, and for variable declarations or casts inside the function body:

c++
// ok: same type used for the return type and parameter
template <typename T> T foo(T* p)
{
    T tmp = *p; // tmp will have the type to which p points
    // ...
    return tmp;
}

Each type parameter must be preceded by the keyword class or typename:

c++
// error: must precede U with either typename or class
template <typename T, U> T calc(const T&, const U&);

These keywords have the same meaning and can be used interchangeably inside a template parameter list. A template parameter list can use both keywords:

c++
// ok: no distinction between typename and class in a template parameter list
template <typename T, class U> calc (const T&, const U&);

It may seem more intuitive to use the keyword typename rather than class to designate a template type parameter. After all, we can use built-in (nonclass) types as a template type argument. Moreover, typename more clearly indicates that the name that follows is a type name. However, typename was added to C++ after templates were already in widespread use; some programmers continue to use class exclusively.

Nontype Template Parameters

In addition to defining type parameters, we can define templates that take nontype parameters. A nontype parameter represents a value rather than a type. Nontype parameters are specified by using a specific type name instead of the class or typename keyword.

When the template is instantiated, nontype parameters are replaced with a value supplied by the user or deduced by the compiler. These values must be constant expressions (§ 2.4.4, p. 65), which allows the compiler to instantiate the templates during compile time.

As an example, we can write a version of compare that will handle string literals. Such literals are arrays of const char. Because we cannot copy an array, we’ll define our parameters as references to an array (§ 6.2.4, p. 217). Because we’d like to be able to compare literals of different lengths, we’ll give our template two nontype parameters. The first template parameter will represent the size of the first array, and the second parameter will represent the size of the second array:

c++
template<unsigned N, unsigned M>
int compare(const char (&p1)[N], const char (&p2)[M])
{
    return strcmp(p1, p2);
}

When we call this version of compare:

c++
compare("hi", "mom")

the compiler will use the size of the literals to instantiate a version of the template with the sizes substituted for N and M. Remembering that the compiler inserts a null terminator at the end of a string literal (§ 2.1.3, p. 39), the compiler will instantiate

c++
int compare(const char (&p1)[3], const char (&p2)[4])

A nontype parameter may be an integral type, or a pointer or (lvalue) reference to an object or to a function type. An argument bound to a nontype integral parameter must be a constant expression. Arguments bound to a pointer or reference nontype parameter must have static lifetime (Chapter 12, p. 450). We may not use an ordinary (nonstatic) local object or a dynamic object as a template argument for reference or pointer nontype template parameters. A pointer parameter can also be instantiated by nullptr or a zero-valued constant expression.

A template nontype parameter is a constant value inside the template definition. A nontype parameter can be used when constant expressions are required, for example, to specify the size of an array.

INFO

Template arguments used for nontype template parameters must be constant expressions.

inline and constexpr Function Templates

A function template can be declared inline or constexpr in the same ways as nontemplate functions. The inline or constexpr specifier follows the template parameter list and precedes the return type:

c++
// ok: inline specifier follows the template parameter list
template <typename T> inline T min(const T&, const T&);
// error: incorrect placement of the inline specifier
inline template <typename T> T min(const T&, const T&);
Writing Type-Independent Code
Tricky

Simple though it is, our initial compare function illustrates two important principles for writing generic code:

  • The function parameters in the template are references to const.
  • The tests in the body use only < comparisons.

By making the function parameters references to const, we ensure that our function can be used on types that cannot be copied. Most types—including the built-in types and, except for unique_ptr and the IO types, all the library types we’ve used—do allow copying. However, there can be class types that do not allow copying. By making our parameters references to const, we ensure that such types can be used with our compare function. Moreover, if compare is called with large objects, then this design will also make the function run faster.

You might think it would be more natural for the comparisons to be done using both the < and > operators:

c++
// expected comparison
if (v1 < v2) return -1;
if (v1 > v2) return 1;
return 0;

However, by writing the code using only the < operator, we reduce the requirements on types that can be used with our compare function. Those types must support <, but they need not also support >.

In fact, if we were truly concerned about type independence and portability, we probably should have defined our function using the less (§ 14.8.2, p. 575):

c++
// version of compare that will be correct even if used on pointers; see § 14.8.2 (p. 575)
template <typename T> int compare(const T &v1, const T &v2)
{
    if (less<T>()(v1, v2)) return -1;
    if (less<T>()(v2, v1)) return 1;
    return 0;
}

The problem with our original version is that if a user calls it with two pointers and those pointers do not point to the same array, then our code is undefined.

TIP

Best Practices

Template programs should try to minimize the number of requirements placed on the argument types.

Template Compilation
Tricky

When the compiler sees the definition of a template, it does not generate code. It generates code only when we instantiate a specific instance of the template. The fact that code is generated only when we use a template (and not when we define it) affects how we organize our source code and when errors are detected.

Ordinarily, when we call a function, the compiler needs to see only a declaration for the function. Similarly, when we use objects of class type, the class definition must be available, but the definitions of the member functions need not be present. As a result, we put class definitions and function declarations in header files and definitions of ordinary and class-member functions in source files.

Templates are different: To generate an instantiation, the compiler needs to have the code that defines a function template or class template member function. As a result, unlike nontemplate code, headers for templates typically include definitions as well as declarations

INFO

Definitions of function templates and member functions of class templates are ordinarily put into header files.

INFO

Key Concept: Templates and Headers

Templates contain two kinds of names:

  • Those that do not depend on a template parameter
  • Those that do depend on a template parameter

It is up to the provider of a template to ensure that all names that do not depend on a template parameter are visible when the template is used. Moreover, the template provider must ensure that the definition of the template, including the definitions of the members of a class template, are visible when the template is instantiated.

It is up to users of a template to ensure that declarations for all functions, types, and operators associated with the types used to instantiate the template are visible.

Both of these requirements are easily satisfied by well-structured programs that make appropriate use of headers. Authors of templates should provide a header that contains the template definition along with declarations for all the names used in the class template or in the definitions of its members. Users of the template must include the header for the template and for any types used to instantiate that template.

Compilation Errors Are Mostly Reported during Instantiation

The fact that code is not generated until a template is instantiated affects when we learn about compilation errors in the code inside the template. In general, there are three stages during which the compiler might flag an error.

The first stage is when we compile the template itself. The compiler generally can’t find many errors at this stage. The compiler can detect syntax errors—such as forgetting a semicolon or misspelling a variable name—but not much else.

The second error-detection time is when the compiler sees a use of the template. At this stage, there is still not much the compiler can check. For a call to a function template, the compiler typically will check that the number of the arguments is appropriate. It can also detect whether two arguments that are supposed to have the same type do so. For a class template, the compiler can check that the right number of template arguments are provided but not much more.

The third time when errors are detected is during instantiation. It is only then that type-related errors can be found. Depending on how the compiler manages instantiation, these errors may be reported at link time.

When we write a template, the code may not be overtly type specific, but template code usually makes some assumptions about the types that will be used. For example, the code inside our original compare function:

c++
if (v1 < v2) return -1;  // requires < on objects of type T
if (v2 < v1) return 1;   // requires < on objects of type T
return 0;                // returns int; not dependent on T

assumes that the argument type has a < operator. When the compiler processes the body of this template, it cannot verify whether the conditions in the if statements are legal. If the arguments passed to compare have a < operation, then the code is fine, but not otherwise. For example,

c++
Sales_data data1, data2;
cout << compare(data1, data2) << endl; // error: no < on Sales_data

This call instantiates a version of compare with T replaced by Sales_data. The if conditions attempt to use < on Sales_data objects, but there is no such operator. This instantiation generates a version of the function that will not compile. However, errors such as this one cannot be detected until the compiler instantiates the definition of compare on type Sales_data.

WARNING

It is up to the caller to guarantee that the arguments passed to the template support any operations that template uses, and that those operations behave correctly in the context in which the template uses them.

INFO

Exercises Section 16.1.1

Exercise 16.1: Define instantiation.

Exercise 16.2: Write and test your own versions of the compare functions.

Exercise 16.3: Call your compare function on two Sales_data objects to see how your compiler handles errors during instantiation.

Exercise 16.4: Write a template that acts like the library find algorithm. The function will need two template type parameters, one to represent the function’s iterator parameters and the other for the type of the value. Use your function to find a given value in a vector<int> and in a list<string>.

Exercise 16.5: Write a template version of the print function from § 6.2.4 (p. 217) that takes a reference to an array and can handle arrays of any size and any element type.

Exercise 16.6: How do you think the library begin and end functions that take an array argument work? Define your own versions of these functions.

Exercise 16.7: Write a constexpr template that returns the size of a given array.

Exercise 16.8: In the “Key Concept” box on page 108, we noted that as a matter of habit C++ programmers prefer using != to using <. Explain the rationale for this habit.

16.1.2. Class Templates

Fundamental

A class template is a blueprint for generating classes. Class templates differ from function templates in that the compiler cannot deduce the template parameter type(s) for a class template. Instead, as we’ve seen many times, to use a class template we must supply additional information inside angle brackets following the template’s name (§ 3.3, p. 97). That extra information is the list of template arguments to use in place of the template parameters.

Defining a Class Template

As an example, we’ll implement a template version of StrBlob (§ 12.1.1, p. 456). We’ll name our template Blob to indicate that it is no longer specific to strings. Like StrBlob, our template will provide shared (and checked) access to the elements it holds. Unlike that class, our template can be used on elements of pretty much any type. As with the library containers, our users will have to specify the element type when they use a Blob.

Like function templates, class templates begin with the keyword template followed by a template parameter list. In the definition of the class template (and its members), we use the template parameters as stand-ins for types or values that will be supplied when the template is used:

c++
template <typename T> class Blob {
public:
    typedef T value_type;
    typedef typename std::vector<T>::size_type size_type;
    // constructors
    Blob();
    Blob(std::initializer_list<T> il);
    // number of elements in the Blob
    size_type size() const { return data->size(); }
    bool empty() const { return data->empty(); }
    // add and remove elements
    void push_back(const T &t) {data->push_back(t);}
    // move version; see § 13.6.3 (p. 548)
    void push_back(T &&t) { data->push_back(std::move(t)); }
    void pop_back();
    // element access
    T& back();
    T& operator[](size_type i); // defined in § 14.5 (p. 566)
private:
    std::shared_ptr<std::vector<T>> data;
    // throws msg if data[i] isn't valid
    void check(size_type i, const std::string &msg) const;
};

Our Blob template has one template type parameter, named T. We use the type parameter anywhere we refer to the element type that the Blob holds. For example, we define the return type of the operations that provide access to the elements in the Blob as T&. When a user instantiates a Blob, these uses of T will be replaced by the specified template argument type.

With the exception of the template parameter list, and the use of T instead of string, this class is the same as the version we defined in § 12.1.1 (p. 456) and updated in § 12.1.6 (p. 475) and in Chapters 13 and 14.

Instantiating a Class Template

As we’ve seen many times, when we use a class template, we must supply extra information. We can now see that that extra information is a list of explicit template arguments that are bound to the template’s parameters. The compiler uses these template arguments to instantiate a specific class from the template.

For example, to define a type from our Blob template, we must provide the element type:

c++
Blob<int> ia;                // empty Blob<int>
Blob<int> ia2 = {0,1,2,3,4}; // Blob<int> with five elements

Both ia and ia2 use the same type-specific version of Blob (i.e., Blob<int>). From these definitions, the compiler will instantiate a class that is equivalent to

c++
template <> class Blob<int> {
    typedef typename std::vector<int>::size_type size_type;
    Blob();
    Blob(std::initializer_list<int> il);
    // ...
    int& operator[](size_type i);
private:
    std::shared_ptr<std::vector<int>> data;
    void check(size_type i, const std::string &msg) const;
};

When the compiler instantiates a class from our Blob template, it rewrites the Blob template, replacing each instance of the template parameter T by the given template argument, which in this case is int.

The compiler generates a different class for each element type we specify:

c++
// these definitions instantiate two distinct Blob types
Blob<string> names; // Blob that holds strings
Blob<double> prices;// different element type

These definitions would trigger instantiations of two distinct classes: The definition of names creates a Blob class in which each occurrence of T is replaced by string. The definition of prices generates a Blob with T replaced by double.

INFO

Each instantiation of a class template constitutes an independent class. The type Blob<string> has no relationship to, or any special access to, the members of any other Blob type.

References to a Template Type in the Scope of the Template
Tricky

In order to read template class code, it can be helpful to remember that the name of a class template is not the name of a type (§ 3.3, p. 97). A class template is used to instantiate a type, and an instantiated type always includes template argument(s).

What can be confusing is that code in a class template generally doesn’t use the name of an actual type (or value) as a template argument. Instead, we often use the template’s own parameter(s) as the template argument(s). For example, our data member uses two templates, vector and shared_ptr. Whenever we use a template, we must supply template arguments. In this case, the template argument we supply is the same type that is used to instantiate the Blob. Therefore, the definition of data

c++
std::shared_ptr<std::vector<T>> data;

uses Blob’s type parameter to say that data is the instantiation of shared_ptr that points to the instantiation of vector that holds objects of type T. When we instantiate a particular kind of Blob, such as Blob<string>, then data will be

c++
shared_ptr<vector<string>>

If we instantiate Blob<int>, then data will be shared_ptr<vector<int>>, and so on.

Member Functions of Class Templates

As with any class, we can define the member functions of a class template either inside or outside of the class body. As with any other class, members defined inside the class body are implicitly inline.

A class template member function is itself an ordinary function. However, each instantiation of the class template has its own version of each member. As a result, a member function of a class template has the same template parameters as the class itself. Therefore, a member function defined outside the class template body starts with the keyword template followed by the class’ template parameter list.

As usual, when we define a member outside its class, we must say to which class the member belongs. Also as usual, the name of a class generated from a template includes its template arguments. When we define a member, the template argument(s) are the same as the template parameter(s). That is, for a given member function of StrBlob that was defined as

c++
ret-type StrBlob::member-name(parm-list)

the corresponding Blob member will look like

c++
template <typename T>
ret-type Blob<T>::member-name(parm-list)
The check and Element Access Members

We’ll start by defining the check member, which verifies a given index:

c++
template <typename T>
void Blob<T>::check(size_type i, const std::string &msg) const
{
    if (i >= data->size())
        throw std::out_of_range(msg);
}

Aside from the differences in the class name and the use of the template parameter list, this function is identical to the original StrBlob member.

The subscript operator and back function use the template parameter to specify the return type but are otherwise unchanged:

c++
template <typename T>
T& Blob<T>::back()
{
    check(0, "back on empty Blob");
    return data->back();
}
template <typename T>
T& Blob<T>::operator[](size_type i)
{
    // if i is too big, check will throw, preventing access to a nonexistent element
    check(i, "subscript out of range");
    return (*data)[i];
}

In our original StrBlob class these operators returned string&. The template versions will return a reference to whatever type is used to instantiate Blob.

The pop_back function is nearly identical to our original StrBlob member:

c++
template <typename T> void Blob<T>::pop_back()
{
    check(0, "pop_back on empty Blob");
    data->pop_back();
}

The subscript operator and back members are overloaded on const. We leave the definition of these members, and of the front members, as an exercise.

Blob Constructors

As with any other member defined outside a class template, a constructor starts by declaring the template parameters for the class template of which it is a member:

c++
template <typename T>
Blob<T>::Blob(): data(std::make_shared<std::vector<T>>()) { }

Here we are defining the member named Blob in the scope of Blob<T>. Like our StrBlob default constructor (§ 12.1.1, p. 456), this constructor allocates an empty vector and stores the pointer to that vector in data. As we’ve seen, we use the class’ own type parameter as the template argument of the vector we allocate.

Similarly, the constructor that takes an initializer_list uses its type parameter T as the element type for its initializer_list parameter:

c++
template <typename T>
Blob<T>::Blob(std::initializer_list<T> il):
              data(std::make_shared<std::vector<T>>(il)) { }

Like the default constructor, this constructor allocates a new vector. In this case, we initialize that vector from the parameter, il.

To use this constructor, we must pass an initializer_list in which the elements are compatible with the element type of the Blob:

c++
Blob<string> articles = {"a", "an", "the"};

The parameter in this constructor has type initializer_list<string>. Each string literal in the list is implicitly converted to string.

Instantiation of Class-Template Member Functions

By default, a member function of a class template is instantiated only if the program uses that member function. For example, this code

c++
// instantiates Blob<int> and the initializer_list<int> constructor
Blob<int> squares = {0,1,2,3,4,5,6,7,8,9};
// instantiates Blob<int>::size() const
for (size_t i = 0; i != squares.size(); ++i)
    squares[i] = i*i; // instantiates Blob<int>::operator[](size_t)

instantiates the Blob<int> class and three of its member functions: operator[], size, and the initializer_list<int> constructor.

If a member function isn’t used, it is not instantiated. The fact that members are instantiated only if we use them lets us instantiate a class with a type that may not meet the requirements for some of the template’s operations (§ 9.2, p. 329).

INFO

By default, a member of an instantiated class template is instantiated only if the member is used.

Simplifying Use of a Template Class Name inside Class Code

There is one exception to the rule that we must supply template arguments when we use a class template type. Inside the scope of the class template itself, we may use the name of the template without arguments:

c++
// BlobPtr throws an exception on attempts to access a nonexistent element
template <typename T> class BlobPtr
public:
    BlobPtr(): curr(0) { }
    BlobPtr(Blob<T> &a, size_t sz = 0):
            wptr(a.data), curr(sz) { }
    T& operator*() const
    { auto p = check(curr, "dereference past end");
      return (*p)[curr];  // (*p) is the vector to which this object points
    }
    // increment and decrement
    BlobPtr& operator++();        // prefix operators
    BlobPtr& operator--();
private:
    // check returns a shared_ptr to the vector if the check succeeds
    std::shared_ptr<std::vector<T>>
        check(std::size_t, const std::string&) const;
    // store a weak_ptr, which means the underlying vector might be destroyed
    std::weak_ptr<std::vector<T>> wptr;
    std::size_t curr;      // current position within the array
};

Careful readers will have noted that the prefix increment and decrement members of BlobPtr return BlobPtr&, not BlobPtr<T>&. When we are inside the scope of a class template, the compiler treats references to the template itself as if we had supplied template arguments matching the template’s own parameters. That is, it is as if we had written:

c++
BlobPtr<T>& operator++();
BlobPtr<T>& operator--();
Using a Class Template Name outside the Class Template Body

When we define members outside the body of a class template, we must remember that we are not in the scope of the class until the class name is seen (§ 7.4, p. 282):

c++
// postfix: increment/decrement the object but return the unchanged value
template <typename T>
BlobPtr<T> BlobPtr<T>::operator++(int)
{
    // no check needed here; the call to prefix increment will do the check
    BlobPtr ret = *this;  // save the current value
    ++*this;    // advance one element; prefix ++ checks the increment
    return ret;  // return the saved state
}

Because the return type appears outside the scope of the class, we must specify that the return type returns a BlobPtr instantiated with the same type as the class. Inside the function body, we are in the scope of the class so do not need to repeat the template argument when we define ret. When we do not supply template arguments, the compiler assumes that we are using the same type as the member’s instantiation. Hence, the definition of ret is as if we had written:

c++
BlobPtr<T> ret = *this;

INFO

Inside the scope of a class template, we may refer to the template without specifying template argument(s).

Class Templates and Friends

When a class contains a friend declaration (§ 7.2.1, p. 269), the class and the friend can independently be templates or not. A class template that has a nontemplate friend grants that friend access to all the instantiations of the template. When the friend is itself a template, the class granting friendship controls whether friendship includes all instantiations of the template or only specific instantiation(s).

One-to-One Friendship

The most common form of friendship from a class template to another template (class or function) establishes friendship between corresponding instantiations of the class and its friend. For example, our Blob class should declare the BlobPtr class and a template version of the Blob equality operator (originally defined for StrBlob in the exercises in § 14.3.1 (p. 562)) as friends.

In order to refer to a specific instantiation of a template (class or function) we must first declare the template itself. A template declaration includes the template’s template parameter list:

c++
// forward declarations needed for friend declarations in Blob
template <typename> class BlobPtr;
template <typename> class Blob; // needed for parameters in operator==
template <typename T>
    bool operator==(const Blob<T>&, const Blob<T>&);
template <typename T> class Blob {
    // each instantiation of Blob grants access to the version of
    // BlobPtr and the equality operator instantiated with the same type
    friend class BlobPtr<T>;
    friend bool operator==<T>
           (const Blob<T>&, const Blob<T>&);
    // other members as in § 12.1.1 (p. 456)
};

We start by declaring that Blob, BlobPtr, and operator== are templates. These declarations are needed for the parameter declaration in the operator== function and the friend declarations in Blob.

The friend declarations use Blob’s template parameter as their own template argument. Thus, the friendship is restricted to those instantiations of BlobPtr and the equality operator that are instantiated with the same type:

c++
Blob<char> ca; // BlobPtr<char> and operator==<char> are friends
Blob<int> ia;  // BlobPtr<int> and operator==<int> are friends

The members of BlobPtr<char> may access the nonpublic parts of ca (or any other Blob<char> object), but ca has no special access to ia (or any other Blob<int>) or to any other instantiation of Blob.

General and Specific Template Friendship

A class can also make every instantiation of another template its friend, or it may limit friendship to a specific instantiation:

c++
// forward declaration necessary to befriend a specific instantiation of a template
template <typename T> class Pal;
class C {  //  C is an ordinary, nontemplate class
    friend class Pal<C>;  // Pal instantiated with class C is a friend to C
    // all instances of Pal2 are friends to C;
    // no forward declaration required when we befriend all instantiations
    template <typename T> friend class Pal2;
};
template <typename T> class C2 { // C2 is itself a class template
    // each instantiation of C2 has the same instance of Pal as a friend
    friend class Pal<T>;  // a template declaration for Pal must be in scope
    // all instances of Pal2 are friends of each instance of C2, prior declaration needed
    template <typename X> friend class Pal2;
    // Pal3 is a nontemplate class that is a friend of every instance of C2
    friend class Pal3;    // prior declaration for Pal3 not needed
};

To allow all instantiations as friends, the friend declaration must use template parameter(s) that differ from those used by the class itself.

Befriending the Template’s Own Type Parameter
C++11

Under the new standard, we can make a template type parameter a friend:

c++
template <typename Type> class Bar {
friend Type; // grants access to the type used to instantiate Bar
    //  ...
};

Here we say that whatever type is used to instantiate Bar is a friend. Thus, for some type named Foo, Foo would be a friend of Bar<Foo>, Sales_data a friend of Bar<Sales_data>, and so on.

It is worth noting that even though a friend ordinarily must be a class or a function, it is okay for Bar to be instantiated with a built-in type. Such friendship is allowed so that we can instantiate classes such as Bar with built-in types.

Template Type Aliases

An instantiation of a class template defines a class type, and as with any other class type, we can define a typedef (§ 2.5.1, p. 67) that refers to that instantiated class:

c++
typedef Blob<string> StrBlob;

This typedef will let us run the code we wrote in § 12.1.1 (p. 456) using our template version of Blob instantiated with string. Because a template is not a type, we cannot define a typedef that refers to a template. That is, there is no way to define a typedef that refers to Blob<T>.

C++11

However, the new standard lets us define a type alias for a class template:

c++
template<typename T> using twin = pair<T, T>;
twin<string> authors; // authors is a pair<string, string>

Here we’ve defined twin as a synonym for pairs in which the members have the same type. Users of twin need to specify that type only once.

A template type alias is a synonym for a family of classes:

c++
twin<int> win_loss;  // win_loss is a pair<int, int>
twin<double> area;   // area is a pair<double, double>

Just as we do when we use a class template, when we use twin, we specify which particular kind of twin we want.

When we define a template type alias, we can fix one or more of the template parameters:

c++
template <typename T> using partNo = pair<T, unsigned>;
partNo<string> books;  // books is a pair<string, unsigned>
partNo<Vehicle> cars;  // cars is a pair<Vehicle, unsigned>
partNo<Student> kids;  // kids is a pair<Student, unsigned>

Here we’ve defined partNo as a synonym for the family of types that are pairs in which the second member is an unsigned. Users of partNo specify a type for the first member of the pair but have no choice about second.

static Members of Class Templates

Like any other class, a class template can declare static members (§ 7.6, p. 300):

c++
template <typename T> class Foo {
public:
   static std::size_t count() { return ctr; }
   // other interface members
private:
   static std::size_t ctr;
   // other implementation members
};

Here Foo is a class template that has a public static member function named count and a private static data member named ctr. Each instantiation of Foo has its own instance of the static members. That is, for any given type X, there is one Foo<X>::ctr and one Foo<X>::count member. All objects of type Foo<X> share the same ctr object and count function. For example,

c++
// instantiates static members Foo<string>::ctr and Foo<string>::count
Foo<string> fs;
// all three objects share the same Foo<int>::ctr and Foo<int>::count members
Foo<int> fi, fi2, fi3;

As with any other static data member, there must be exactly one definition of each static data member of a template class. However, there is a distinct object for each instantiation of a class template. As a result, we define a static data member as a template similarly to how we define the member functions of that template:

c++
template <typename T>
size_t Foo<T>::ctr = 0; // define and initialize ctr

As with any other member of a class template, we start by defining the template parameter list, followed by the type of the member we are defining and the member’s name. As usual, a member’s name includes the member’s class name, which for a class generated from a template includes its template arguments. Thus, when Foo is instantiated for a particular template argument type, a separate ctr will be instantiated for that class type and initialized to 0.

As with static members of nontemplate classes, we can access a static member of a class template through an object of the class type or by using the scope operator to access the member directly. Of course, to use a static member through the class, we must refer to a specific instantiation:

c++
Foo<int> fi;                 // instantiates Foo<int> class
                             // and the static data member ctr
auto ct = Foo<int>::count(); // instantiates Foo<int>::count
ct = fi.count();             // uses Foo<int>::count
ct = Foo::count();           // error: which template instantiation?

Like any other member function, a static member function is instantiated only if it is used in a program.

INFO

Exercises Section 16.1.2

Exercise 16.9: What is a function template? What is a class template?

Exercise 16.10: What happens when a class template is instantiated?

Exercise 16.11: The following definition of List is incorrect. How would you fix it?

c++
template <typename elemType> class ListItem;
template <typename elemType> class List {
public:
    List<elemType>();
    List<elemType>(const List<elemType> &);
    List<elemType>& operator=(const List<elemType> &);
    ~List();
    void insert(ListItem *ptr, elemType value);
private:
    ListItem *front, *end;
};

Exercise 16.12: Write your own version of the Blob and BlobPtr templates. including the various const members that were not shown in the text.

Exercise 16.13: Explain which kind of friendship you chose for the equality and relational operators for BlobPtr.

Exercise 16.14: Write a Screen class template that uses nontype parameters to define the height and width of the Screen.

Exercise 16.15: Implement input and output operators for your Screen template. Which, if any, friends are necessary in class Screen to make the input and output operators work? Explain why each friend declaration, if any, was needed.

Exercise 16.16: Rewrite the StrVec class (§ 13.5, p. 526) as a template named Vec.

16.1.3. Template Parameters

Fundamental

Like the names of function parameters, a template parameter name has no intrinsic meaning. We ordinarily name type parameters T, but we can use any name:

c++
template <typename Foo> Foo calc(const Foo& a, const Foo& b)
{
    Foo tmp = a; // tmp has the same type as the parameters and return type
    // ...
    return tmp;  // return type and parameters have the same type
}
Template Parameters and Scope

Template parameters follow normal scoping rules. The name of a template parameter can be used after it has been declared and until the end of the template declaration or definition. As with any other name, a template parameter hides any declaration of that name in an outer scope. Unlike most other contexts, however, a name used as a template parameter may not be reused within the template:

c++
typedef double A;
template <typename A, typename B> void f(A a, B b)
{
    A tmp = a; // tmp has same type as the template parameter A, not double
    double B;  // error: redeclares template parameter B
}

Normal name hiding says that the typedef of A is hidden by the type parameter named A. Thus, tmp is not a double; it has whatever type gets bound to the template parameter A when calc is used. Because we cannot reuse names of template parameters, the declaration of the variable named B is an error.

Because a parameter name cannot be reused, the name of a template parameter can appear only once with in a given template parameter list:

c++
// error: illegal reuse of template parameter name V
template <typename V, typename V> // ...
Template Declarations

A template declaration must include the template parameters :

c++
// declares but does not define compare and Blob
template <typename T> int compare(const T&, const T&);
template <typename T> class Blob;

As with function parameters, the names of a template parameter need not be the same across the declaration(s) and the definition of the same template:

c++
// all three uses of calc refer to the same function template
template <typename T> T calc(const T&, const T&); // declaration
template <typename U> U calc(const U&, const U&); // declaration
// definition of the template
template <typename Type>
Type calc(const Type& a, const Type& b) { /* . . . */ }

Of course, every declaration and the definition of a given template must have the same number and kind (i.e., type or nontype) of parameters.

TIP

Best Practices

For reasons we’ll explain in § 16.3 (p. 698), declarations for all the templates needed by a given file usually should appear together at the beginning of a file before any code that uses those names.

Using Class Members That Are Types

Recall that we use the scope operator (::) to access both static members and type members (§ 7.4, p. 282, and § 7.6, p. 301). In ordinary (nontemplate) code, the compiler has access to the class defintion. As a result, it knows whether a name accessed through the scope operator is a type or a static member. For example, when we write string::size_type, the compiler has the definition of string and can see that size_type is a type.

Assuming T is a template type parameter, When the compiler sees code such as T::mem it won’t know until instantiation time whether mem is a type or a static data member. However, in order to process the template, the compiler must know whether a name represents a type. For example, assuming T is the name of a type parameter, when the compiler sees a statement of the following form:

c++
T::size_type * p;

it needs to know whether we’re defining a variable named p or are multiplying a static data member named size_type by a variable named p.

By default, the language assumes that a name accessed through the scope operator is not a type. As a result, if we want to use a type member of a template type parameter, we must explicitly tell the compiler that the name is a type. We do so by using the keyword typename:

c++
template <typename T>
typename T::value_type top(const T& c)
{
    if (!c.empty())
        return c.back();
    else
        return typename T::value_type();
}

Our top function expects a container as its argument and uses typename to specify its return type and to generate a value initialized element (§ 7.5.3, p. 293) to return if c has no elements.

INFO

When we want to inform the compiler that a name represents a type, we must use the keyword typename, not class.

Default Template Arguments

Just as we can supply default arguments to function parameters (§ 6.5.1, p. 236), we can also supply default template arguments. Under the new standard, we can supply default arguments for both function and class templates. Earlier versions of the language, allowed default arguments only with class templates.

C++11

As an example, we’ll rewrite compare to use the library less function-object template (§ 14.8.2, p. 574) by default:

c++
// compare has a default template argument, less<T>
// and a default function argument, F()
template <typename T, typename F = less<T>>
int compare(const T &v1, const T &v2, F f = F())
{
    if (f(v1, v2)) return -1;
    if (f(v2, v1)) return 1;
    return 0;
}

Here we’ve given our template a second type parameter, named F, that represents the type of a callable object (§ 10.3.2, p. 388) and defined a new function parameter, f, that will be bound to a callable object.

We’ve also provided defaults for this template parameter and its corresponding function parameter. The default template argument specifies that compare will use the library less function-object class, instantiated with the same type parameter as compare. The default function argument says that f will be a default-initialized object of type F.

When users call this version of compare, they may supply their own comparison operation but are not required to do so:

c++
bool i = compare(0, 42); // uses less; i is -1
// result depends on the isbns in item1 and item2
Sales_data item1(cin), item2(cin);
bool j = compare(item1, item2, compareIsbn);

The first call uses the default function argument, which is a default-initialized object of type less<T>. In this call, T is int so that object has type less<int>. This instantiation of compare will use less<int> to do its comparisons.

In the second call, we pass compareIsbn (§ 11.2.2, p. 425) and two objects of type Sales_data. When compare is called with three arguments, the type of the third argument must be a callable object that returns a type that is convertible to bool and takes arguments of a type compatible with the types of the first two arguments. As usual, the types of the template parameters are deduced from their corresponding function arguments. In this call, the type of T is deduced as Sales_data and F is deduced as the type of compareIsbn.

As with function default arguments, a template parameter may have a default argument only if all of the parameters to its right also have default arguments.

Template Default Arguments and Class Templates

Whenever we use a class template, we must always follow the template’s name with brackets. The brackets indicate that a class must be instantiated from a template. In particular, if a class template provides default arguments for all of its template parameters, and we want to use those defaults, we must put an empty bracket pair following the template’s name:

c++
template <class T = int> class Numbers {   // by default T is int
public:
    Numbers(T v = 0): val(v) { }
    // various operations on numbers
private:
    T val;
};
Numbers<long double> lots_of_precision;
Numbers<> average_precision; // empty <> says we want the default type

Here we instantiate two versions of Numbers: average_precision instantiates Numbers with T replaced by int; lots_of_precision instantiates Numbers with T replaced by long double.

INFO

Exercises Section 16.1.3

Exercise 16.17: What, if any, are the differences between a type parameter that is declared as a typename and one that is declared as a class? When must typename be used?

Exercise 16.18: Explain each of the following function template declarations and identify whether any are illegal. Correct each error that you find.

c++
(a) template <typename T, U, typename V> void f1(T, U, V);
(b) template <typename T> T f2(int &T);
(c) inline template <typename T> T foo(T, unsigned int*);
(d) template <typename T> f4(T, T);
(e) typedef char Ctype;
    template <typename Ctype> Ctype f5(Ctype a);

Exercise 16.19: Write a function that takes a reference to a container and prints the elements in that container. Use the container’s size_type and size members to control the loop that prints the elements.

Exercise 16.20: Rewrite the function from the previous exercise to use iterators returned from begin and end to control the loop.

16.1.4. Member Templates

A class—either an ordinary class or a class template—may have a member function that is itself a template. Such members are referred to as member templates. Member templates may not be virtual.

Member Templates of Ordianary (Nontemplate) Classes

As an example of an ordinary class that has a member template, we’ll define a class that is similar to the default deleter type used by unique_ptr (§ 12.1.5, p. 471). Like the default deleter, our class will have an overloaded function-call operator (§ 14.8, p. 571) that will take a pointer and execute delete on the given pointer. Unlike the default deleter, our class will also print a message whenever the deleter is executed. Because we want to use our deleter with any type, we’ll make the call operator a template:

c++
// function-object class that calls delete on a given pointer
class DebugDelete {
public:
    DebugDelete(std::ostream &s = std::cerr): os(s) { }
    // as with any function template, the type of T is deduced by the compiler
    template <typename T> void operator()(T *p) const
      { os << "deleting unique_ptr" << std::endl; delete p; }
private:
    std::ostream &os;
};

Like any other template, a member template starts with its own template parameter list. Each DebugDelete object has an ostream member on which to write, and a member function that is itself a template. We can use this class as a replacement for delete:

c++
double* p = new double;
DebugDelete d;    // an object that can act like a delete expression
d(p); // calls DebugDelete::operator()(double*), which deletes p
int* ip = new int;
// calls operator()(int*) on a temporary DebugDelete object
DebugDelete()(ip);

Because calling a DebugDelete object deletes its given pointer, we can also use DebugDelete as the deleter of a unique_ptr. To override the deleter of a unique_ptr, we supply the type of the deleter inside brackets and supply an object of the deleter type to the constructor (§ 12.1.5, p. 471):

c++
// destroying the the object to which p points
// instantiates DebugDelete::operator()<int>(int *)
unique_ptr<int, DebugDelete> p(new int, DebugDelete());
// destroying the the object to which sp points
// instantiates DebugDelete::operator()<string>(string*)
unique_ptr<string, DebugDelete> sp(new string, DebugDelete());

Here, we’ve said that p’s deleter will have type DebugDelete, and we have supplied an unnamed object of that type in p’s constructor.

The unique_ptr destructor calls the DebugDelete’s call operator. Thus, whenever unique_ptr’s destructor is instantiated, DebugDelete’s call operator will also be instantiated: Thus, the definitions above will instantiate:

c++
// sample instantiations for member templates of DebugDelete
void DebugDelete::operator()(int *p) const { delete p; }
void DebugDelete::operator()(string *p) const { delete p; }
Member Templates of Class Templates

We can also define a member template of a class template. In this case, both the class and the member have their own, independent, template parameters.

As an example, we’ll give our Blob class a constructor that will take two iterators denoting a range of elements to copy. Because we’d like to support iterators into varying kinds of sequences, we’ll make this constructor a template:

c++
template <typename T> class Blob {
    template <typename It> Blob(It b, It e);
    // ...
};

This constructor has its own template type parameter, It, which it uses for the type of its two function parameters.

Unlike ordinary function members of class templates, member templates are function templates. When we define a member template outside the body of a class template, we must provide the template parameter list for the class template and for the function template. The parameter list for the class template comes first, followed by the member’s own template parameter list:

c++
template <typename T>     // type parameter for the class
template <typename It>    // type parameter for the constructor
    Blob<T>::Blob(It b, It e):
              data(std::make_shared<std::vector<T>>(b, e)) { }

Here we are defining a member of a class template that has one template type parameter, which we have named T. The member itself is a function template that has a type parameter named It.

Instantiation and Member Templates

To instantiate a member template of a class template, we must supply arguments for the template parameters for both the class and the function templates. As usual, argument(s) for the class template parameter(s) are determined by the type of the object through which we call the member template. Also as usual, the compiler typically deduces template argument(s) for the member template’s own parameter(s) from the arguments passed in the call (§ 16.1.1, p. 653):

c++
int ia[] = {0,1,2,3,4,5,6,7,8,9};
vector<long> vi = {0,1,2,3,4,5,6,7,8,9};
list<const char*> w = {"now", "is", "the", "time"};
// instantiates the Blob<int> class
// and the Blob<int> constructor that has two int* parameters
Blob<int> a1(begin(ia), end(ia));
// instantiates the Blob<int> constructor that has
// two vector<long>::iterator parameters
Blob<int> a2(vi.begin(), vi.end());
// instantiates the Blob<string> class and the Blob<string>
// constructor that has two (list<const char*>::iterator parameters
Blob<string> a3(w.begin(), w.end());

When we define a1, we explicitly specify that the compiler should instantiate a version of Blob with the template parameter bound to int. The type parameter for the constructor’s own parameters will be deduced from the type of begin(ia) and end(ia). That type is int*. Thus, the definition of a1 instantiates:

c++
Blob<int>::Blob(int*, int*);

The definition of a2 uses the already instantiated Blob<int> class, and instantiates the constructor with It replaced by vector<short>::iterator. The definition of a3 (explicitly) instantiates the Blob with its template parameter bound to string and (implicitly) instantiates the member template constructor of that class with its parameter bound to list<const char*>.

INFO

Exercises Section 16.1.4

Exercise 16.21: Write your own version of DebugDelete.

Exercise 16.22: Revise your TextQuery programs from § 12.3 (p. 484) so that the shared_ptr members use a DebugDelete as their deleter (§ 12.1.4, p. 468).

Exercise 16.23: Predict when the call operator will be executed in your main query program. If your expectations and what happens differ, be sure you understand why.

Exercise 16.24: Add a constructor that takes two iterators to your Blob template.

16.1.5. Controlling Instantiations

Advanced

The fact that instantiations are generated when a template is used (§ 16.1.1, p. 656) means that the same instantiation may appear in multiple object files. When two or more separately compiled source files use the same template with the same template arguments, there is an instantiation of that template in each of those files.

C++11

In large systems, the overhead of instantiating the same template in multiple files can become significant. Under the new standard, we can avoid this overhead through an explicit instantiation. An explicit instantiation has the form

c++
extern template declaration; // instantiation declaration
template declaration;        // instantiation definition

where declaration is a class or function declaration in which all the template parameters are replaced by the template arguments. For example,

c++
// instantion declaration and definition
extern template class Blob<string>;             // declaration
template int compare(const int&, const int&);   // definition

When the compiler sees an extern template declaration, it will not generate code for that instantiation in that file. Declaring an instantiation as extern is a promise that there will be a nonextern use of that instantiation elsewhere in the program. There may be several extern declarations for a given instantiation but there must be exactly one definition for that instantiation.

Because the compiler automatically instantiates a template when we use it, the extern declaration must appear before any code that uses that instantiation:

c++
// Application.cc
// these template types must be instantiated elsewhere in the program
extern template class Blob<string>;
extern template int compare(const int&, const int&);
Blob<string> sa1, sa2; // instantiation will appear elsewhere
// Blob<int> and its initializer_list constructor instantiated in this file
Blob<int> a1 = {0,1,2,3,4,5,6,7,8,9};
Blob<int> a2(a1);  // copy constructor instantiated in this file
int i = compare(a1[0], a2[0]); // instantiation will appear elsewhere

The file Application.o will contain instantiations for Blob<int>, along with the initializer_list and copy constructors for that class. The compare<int> function and Blob<string> class will not be instantiated in that file. There must be definitions of these templates in some other file in the program:

c++
// templateBuild.cc
// instantiation file must provide a (nonextern) definition for every
// type and function that other files declare as extern
template int compare(const int&, const int&);
template class Blob<string>; // instantiates all members of the class template

When the compiler sees an instantiation definition (as opposed to a declaration), it generates code. Thus, the file templateBuild.o will contain the definitions for compare instantiated with int and for the Blob<string> class. When we build the application, we must link templateBuild.o with the Application.o files.

WARNING

There must be an explicit instantiation definition somewhere in the program for every instantiation declaration.

Instantiation Definitions Instantiate All Members

An instantiation definition for a class template instantiates all the members of that template including inline member functions. When the compiler sees an instantiation definition it cannot know which member functions the program uses. Hence, unlike the way it handles ordinary class template instantiations, the compiler instantiates all the members of that class. Even if we do not use a member, that member will be instantiated. Consequently, we can use explicit instantiation only for types that can be used with all the members of that template.

INFO

An instantiation definition can be used only for types that can be used with every member function of a class template.

16.1.6. Efficiency and Flexibility

Advanced

The library smart pointer types (§ 12.1, p. 450) offer a good illustration of design choices faced by designers of templates.

The obvious difference between shared_ptr and unique_ptr is the strategy they use in managing the pointer they hold—one class gives us shared ownership; the other owns the pointer that it holds. This difference is essential to what these classes do.

These classes also differ in how they let users override their default deleter. We can easily override the deleter of a shared_ptr by passing a callable object when we create or reset the pointer. In contrast, the type of the deleter is part of the type of a unique_ptr object. Users must supply that type as an explicit template argument when they define a unique_ptr. As a result, it is more complicated for users of unique_ptr to provide their own deleter.

INFO

Exercises Section 16.1.5

Exercise 16.25: Explain the meaning of these declarations:

c++
extern template class vector<string>;
template class vector<Sales_data>;

Exercise 16.26: Assuming NoDefault is a class that does not have a default constructor, can we explicitly instantiate vector<NoDefault>? If not, why not?

Exercise 16.27: For each labeled statement explain what, if any, instantiations happen. If a template is instantiated, explain why; if not, explain why not.

c++
template <typename T> class Stack { };
void f1(Stack<char>);                   // (a)
class Exercise {
    Stack<double> &rsd;                 // (b)
    Stack<int>    si;                   // (c)
};
int main() {
    Stack<char> *sc;                    // (d)
    f1(*sc);                            // (e)
    int iObj = sizeof(Stack< string >); // (f)
}

The difference in how the deleter is handled is incidental to the functionality of these classes. However, as we’ll see, this difference in implementation strategy may have important performance impacts.

Binding the Deleter at Run Time

Although we don’t know how the library types are implemented, we can infer that shared_ptr must access its deleter indirectly. That is the deleter must be stored as a pointer or as a class (such as function (§ 14.8.3, p. 577)) that encapsulates a pointer.

We can be certain that shared_ptr does not hold the deleter as a direct member, because the type of the deleter isn’t known until run time. Indeed, we can change the type of the deleter in a given shared_ptr during that shared_ptr’s lifetime. We can construct a shared_ptr using a deleter of one type, and subsequently use reset to give that same shared_ptr a different type of deleter. In general, we cannot have a member whose type changes at run time. Hence, the deleter must be stored indirectly.

To think about how the deleter must work, let’s assume that shared_ptr stores the pointer it manages in a member named p, and that the deleter is accessed through a member named del. The shared_ptr destructor must include a statement such as

c++
// value of del known only at run time; call through a pointer
del ? del(p) : delete p; // del(p) requires run-time jump to del's location

Because the deleter is stored indirectly, the call del(p) requires a run-time jump to the location stored in del to execute the code to which del points.

Binding the Deleter at Compile Time

Now, let’s think about how unique_ptr might work. In this class, the type of the deleter is part of the type of the unique_ptr. That is, unique_ptr has two template parameters, one that represents the pointer that the unique_ptr manages and the other that represents the type of the deleter. Because the type of the deleter is part of the type of a unique_ptr, the type of the deleter member is known at compile time. The deleter can be stored directly in each unique_ptr object.

The unique_ptr destructor operates similarly to its shared_ptr counterpart in that it calls a user-supplied deleter or executes delete on its stored pointer:

c++
// del bound at compile time; direct call to the deleter is instantiated
del(p);   // no run-time overhead

The type of del is either the default deleter type or a user-supplied type. It doesn’t matter; either way the code that will be executed is known at compile time. Indeed, if the deleter is something like our DebugDelete class (§ 16.1.4, p. 672) this call might even be inlined at compile time.

By binding the deleter at compile time, unique_ptr avoids the run-time cost of an indirect call to its deleter. By binding the deleter at run time, shared_ptr makes it easier for users to override the deleter.

INFO

Exercises Section 16.1.6

Exercise 16.28: Write your own versions of shared_ptr and unique_ptr.

Exercise 16.29: Revise your Blob class to use your version of shared_ptr rather than the library version.

Exercise 16.30: Rerun some of your programs to verify your shared_ptr and revised Blob classes. (Note: Implementing the weak_ptr type is beyond the scope of this Primer, so you will not be able to use the BlobPtr class with your revised Blob.)

Exercise 16.31: Explain how the compiler might inline the call to the deleter if we used DebugDelete with unique_ptr.