Chapter 16. Templates and Generic Programming

CONTENTS

Section 16.1 Template Definitions 624

Section 16.2 Instantiation 636

Section 16.3 Template Compilation Models 643

Section 16.4 Class Template Members 647

Section 16.5 A Generic Handle Class 666

Section 16.6 Template Specializations 671

Section 16.7 Overloading and Function Templates 679

Chapter Summary 683

Defined Terms 683

Generic programming involves writing code in a way that is independent of any particular type. When we use a generic program we supply the type(s) or value(s) on which that instance of the program will operate. The library containers, iterators, and algorithms described in Part II are examples of generic programming. There is a single definition of each container, such as vector, but we can define many different kinds of vectors that differ by the element type that the vector contains.

Templates are the foundation of generic programming. We can, and have, used templates without understanding how they are defined. In this chapter we’ll see how we can define our own template classes and functions.

Generic programming, like object-oriented programming, relies on a form of polymorphism. The polymorphism in OOP applies at run time to classes related by inheritance. We can write code that uses such classes in ways that ignore the type differences among the base and derived classes. As long as we use references or pointers to the base type, we can use the same code on objects of the base type or a type derived from that type.

Generic programming lets us write classes and functions that are polymorphic across unrelated types at compile time. A single class or function can be used to manipulate objects of a variety of types. The standard library containers, iterators, and algorithms are good examples of generic programming. The library defines each of the containers, iterators, and algorithms in a type-independent manner. We can use library classes and functions on most any kind of type. For example, we can define a vector of Sales_item objects even though the designers of vector could have had no knowledge of our application-specific class.

In C++, templates are the foundation for generic programming. A template is a blueprint or formula for creating a class or a function. For example, the standard library defines a single class template that defines what it means to be a vector. That template is used to generate any number of type-specific vector classes—for example, vector<int> or vector<string>. Part II showed how to use generic types and functions; this chapter shows how we can define our own templates.

16.1 Template Definitions

Let’s 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 could compare values of a given type. Our first attempt might be to define several overloaded functions:

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 in advance 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 we don’t know about.

16.1.1 Defining a Function Template

Rather than defining a new function for each type, we can define a single function template. A function template is a type-independent function that is used as a formula for generating a type-specific version of the function. For example, we might write a function template named compare, which would tell the compiler how to generate specific versions of compare for the types that we want to compare.

The following is a template version of compare:

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.

Template Parameter List

The template parameter list acts much like a function parameter list. A function parameter list defines local variable(s) of a specified type but leaves those variables uninitialized. At run time, arguments are supplied that initialize the parameters.

Analogously, template parameters represent types or values we can use in the definition of a class or function. For example, our compare function declares one type parameter named T. Inside compare, we can use the name T to refer to a type. Which actual type T represents is determined by the compiler based on how the function is used.

A template parameter can be a type parameter, which represents a type, or a nontype parameter, which represents a constant expression. A nontype parameter is declared following a type specifier. We’ll see more about nontype parameters in Section 16.1.5 (p. 632). A type parameter is defined following the keyword class or typename. For example, class T is a type parameter named T. There is no difference between class and typename in this context.

Using a Function Template

When we use a function template, the compiler infers what template argument(s) to bind to the template parameter(s). Once the compiler determines the actual template argument(s), it instantiates an instance of the function template for us. Essentially, the compiler figures out what type to use in place of each type parameter and what value to use in place of each nontype parameter. Having deduced the actual template arguments, it generates and compiles a version of the function using those arguments in place of the corresponding template parameters. The compiler takes on the tedium of (re)writing the function for each type we use.

Given the calls

the compiler will instantiate two different versions of compare. The compiler will create one version that replaces T by int and a second version that uses string in place of T.

inline Function Templates

A function template can be declared inline in the same way as a nontemplate function. The specifier is placed following the template parameter list and before the return type. It is not placed in front of the template keyword.

16.1.2 Defining a Class Template

Just as we can define function templates, we can also define class templates.

Our Queue must be able to hold objects of different types, so we’ll define it as a class template. The operations our Queue will support are a subset of the interface of the standard queue:

• push to add an item to the back of the queue

• pop to remove the item at the head of the queue

• front to return a reference to the element at the head of the queue

• empty to indicate whether there are any elements in the queue

We’ll look at how we might implement our Queue in Section 16.4 (p. 647), but we can start by defining its interface:

A class template is a template, so it must begin with the keyword template followed by a template parameter list. Our Queue template takes a single template type parameter named Type.

With the exception of the template parameter list, the definition of a class template looks like any other class. A class template may define data, function, and type members; it may use access labels to control access to those members; it defines constructors and destructors; and so on. In the definition of the class and its members, we can use the template parameters as stand-ins for types or values that will be supplied when the class is used.

For example, our Queue template has one template type parameter. We can use that parameter anywhere a type name can be used. In this template definition, we use Type to name the return type from the overloaded front operations and as the parameter type for the push operation.

Using a Class Template

In contrast to calling a function template, when we use a class template, we must explicitly specify arguments for the template parameters:

The compiler uses the arguments to instantiate a type-specific version of the class. Essentially, the compiler rewrites our Queue class replacing Type by the specified actual type provided by the user. In this case, the compiler will instantiate three classes: a version of Queue with Type replaced by int, a second Queue class that uses vector<double> in place of Type, and a third that replaces Type by string.

16.1.3 Template Parameters

As with a function parameter, the name chosen by the programmer for a template parameter has no intrinsic meaning. In our example, we named compare’s template type parameter T, but we could have named it anything:

This code defines the same compare template as before.

The only meaning we can ascribe to a template parameter is to distinguish whether the parameter is a type parameter or a nontype parameter. If it is a type parameter, then we know that the parameter represents an as yet unknown type. If it is a nontype parameter, we know it is an as yet unknown value.

When we wish to use the type or value that a template parameter represents, we use the same name as the corresponding template parameter. For example, all references to Glorp in the compare function template will be resolved to the same type when the function is instantiated.

Template Parameter Scope

The name of a template parameter can be used after it has been declared as a template parameter and until the end of the template declaration or definition.

Template parameters follow normal name-hiding rules. A template parameter with the same name as an object, function, or type declared in global scope hides the global name:

The global typedef that defines T as double is hidden by the type parameter named T. Thus, tmp is not a double. Instead, the type of tmp is whatever type gets bound to the template parameter T.

Restrictions on the Use of a Template Parameter Name

A name used as a template parameter may not be reused within the template:

This restriction also means that the name of a template parameter can be used only once within the same template parameter list:

     // error: illegal reuse of template parameter name V
     template <class V, class V> V calc(const V&, const V&) ;

Of course, just as we can reuse function parameter names, the name of a template parameter can be reused across different templates:

     // ok: reuses parameter type name across different templates
     template <class T> T calc (const T&, const T&) ;
     template <class T> int compare(const T&, const T&) ;

Template Declarations

As with any other function or class, we can declare a template without defining it. A declaration must indicate that the function or class is a template:

     // declares compare but does not define it
     template <class T> int compare(const T&, const T&) ;

The names of the template parameters need not be the same across declarations and the definition of the same template:

Each template type parameter must be preceded either by the keyword class or typename; each nontype parameter must be preceded by a type name. It is an error to omit the keyword or a type specifier:

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

16.1.4 Template Type Parameters

Type parameters consist of the keyword class or the keyword typename followed by an identifier. In a template parameter list, these keywords have the same meaning: They indicate that the name that follows represents a type.

A template type parameter can be used as a type specifier anywhere in the template, in exactly the same way as a built-in or class type specifier. In particular, it can be used to name the return type or a function parameter type, and for variable declarations or casts inside the function body:

Distinction Between typename and class

In a function template parameter list, the keywords typename and class have the same meaning and can be used interchangeably. Both keywords can be used in the same template parameter list:

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

It may seem more intuitive to use the keyword typename instead of the keyword class to designate a template type parameter; after all, we can use built-in (nonclass types) types as the actual type parameter. Moreover, typename more clearly indicates that the name that follows is a type name. However, the keyword typename was added to C++ as part of Standard C++, so older programs are more likely to use the keyword class exclusively.

Designating Types inside the Template Definition

In addition to defining data or function members, a class may define type members. For example, the library container classes define various types, such as size_type, that allow us to use the containers in a machine-independent way. When we want to use such types inside a function template, we must tell the compiler that the name we are using refers to a type. We must be explicit because the compiler (and a reader of our program) cannot tell by inspection when a name defined by a type parameter is a type or a value. As an example, consider the following function:

We know that size_type must be a member of the type bound to Parm, but we do not know whether size_type is the name of a type or a data member. By default, the compiler assumes that such names name data members, not types.

If we want the compiler to treat size_type as a type, then we must explicitly tell the compiler to do so:

We tell the compiler to treat a member as a type by prefixing uses of the member name with the keyword typename. By writing typename Parm::size_type we say that member size_type of the type bound to Parm is the name of a type. Of course, this declaration puts an obligation on the types used to instantiate fcn: Those types must have a member named size_type that is a type.

16.1.5 Nontype Template Parameters

A template parameter need not be a type. In this section we’ll look at nontype parameters as used by function templates. We’ll look at nontype parameters for class templates in Section 16.4.2 (p. 655) after we’ve seen more about how class templates are implemented.

Nontype parameters are replaced by values when the function is called. The type of that value is specified in the template parameter list. For example, the following function template declares array_init as a function template with one type and one nontype template parameter. The function itself takes a single parameter, which is a reference to an array (Section 7.2.4, p. 240):

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, as we do here—to specify the size of an array.

When array_init is called, the compiler figures out the value of the nontype parameter from the array argument:

The compiler will instantiate a separate version of array_init for each kind of array used in a call to array_init. For the program above, the compiler instantiates two versions of array_init: The first instance has its parameter bound to int[42], and in the other, that parameter is bound to double[10].

Type Equivalence and Nontype Parameters

Expressions that evaluate to the same value are considered equivalent template arguments for a template nontype parameter. The following calls to array_init both refer to the same instantiation, array_init<int, 42>:

16.1.6 Writing Generic Programs

When we write a template, the code may not be overtly type-specific, but template code always makes some assumptions about the types that will be used. For example, although our compare function is technically valid for any type, in practice the instantiated version might be illegal.

Whether the generated program is legal depends on the operations used in the function and the operations supported by the type or types used. Our compare function has has three statements:

The first two statements contain code that implicitly depends on the parameter type. The if tests use the < operator on the parameters. The type of those parameters isn’t known until the compiler sees a call to compare and T is bound to an actual type. Which < operator is used depends entirely on the argument type.

If we call compare on an object that does not support the < operator, then the call will be invalid:

     Sales_item item1, item2;
     // error: no < on Sales_item
     cout << compare(item1, item2) << endl;

The program is in error. The Sales_item type does not define the < operator, so the program won’t compile.

Writing Type-Independent Code

The art of writing good generic code is beyond the scope of this language primer. However, there is one overall guideline that is worth noting.

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

• The parameters to the template are const references.

• The tests in the body use only < comparisons.

By making the parameters const references, we allow types that do not allow copying. Most types—including the built-in types and, except for 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 const references, 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.

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

However, by writing the code as

we reduce the requirements on types that can be used with our compare function. Those types must support <, but they need not also support >.

16.2 Instantiation

A template is a blueprint; it is not itself a class or a function. The compiler uses the template to generate type-specific versions of the specified class or function. The process of generatng a type-specific instance of a template is known as instantiation. The term reflects the notion that a new “instance” of the template type or function is created.

A template is instantiated when we use it. A class template is instantiated when we refer to the an actual template class type, and a function template is instantiated when we call it or use it to initialize or assign to a pointer to function.

Instantiating a Class

When we write

     Queue<int> qi;

the compiler automatially creates a class named Queue<int>. In effect, the compiler creates the Queue<int> class by rewriting the Queue template, replacing every occurrence of the template parameter Type by the type int. The instantiated class is as if we had written:

To create a Queue class for objects of type string, we’d write:

     Queue<string> qs;

In this case, each occurrence of Type would be replaced by string.

Class Template Arguments Are Required

When we want to use a class template, we must always specify the template arguments explicitly.

A class template does not define a type; only a specific instantiation defines a type. We define a specific instantiation by providing a template argument to match each template parameter. Template arguments are specified in a comma-separated list and bracketed by the (<) and (>) tokens:

The type defined by a template class always includes the template argument(s). For example, Queue is not a type; Queue<int> or Queue<string> are.

Function-Template Instantiation

When we use a function template, the compiler will usually infer the template arguments for us:

This program instantiates two versions of compare: one where T is replaced by int and the other where it is replaced by double. The compiler essentially writes for us these two instances of compare:

16.2.1 Template Argument Deduction

To determine which functions to instantiate, the compiler looks at each argument. If the corresponding parameter was declared with a type that is a type parameter, then the compiler infers the type of the parameter from the type of the argument. In the case of compare, both arguments have the same template type: they were each declared using the type parameter T.

In the first call, compare(1, 0), those arguments are type int; in the second, compare(3.14, 2.7), they have type double. The process of determining the types and values of the template arguments from the type of the function arguments is called template argument deduction.

Multiple Type Parameter Arguments Must Match Exactly

A template type parameter may be used as the type of more than one function parameter. In such cases, template type deduction must generate the same template argument type for each corresponding function argument. If the deduced types do not match, then the call is an error:

This call is in error because the arguments to compare don’t have the same type. The template argument deduced from the first argument is short; the one for the second is int. These types don’t match, so template argument deduction fails.

If the designer of compare wants to allow normal conversions on the arguments, then the function must be defined with two type parameters:

Now the user may supply arguments of different types:

However, a < operator must exist that can compare values of those types.

Limited Conversions on Type Parameter Arguments

Consider the following calls to compare:

The first call generates an instance of compare with T bound to int. A new instance is created for the second call, binding T to short.

Had compare(int, int) been an ordinary nontemplate function, then the second call would match that function. The short arguments would be promoted (Section 5.12.2, p. 180) to int. Because compare is a template, a new function is instantiated with the type parameter bound to short.

In general, arguments are not converted to match an existing instantiation; instead, a new instance is generated. There are only two kinds of conversions that the compiler will perform rather than generating a new instantiation:

• const conversions: A function that takes a reference or pointer to a const can be called with a reference or pointer to nonconst object, respectively, without generating a new instantiation. If the function takes a nonreference type, then const is ignored on either the parameter type or the argument. That is, the same instantiation will be used whether we pass a const or nonconst object to a function defined to take a nonreference type.

• array or function to pointer conversions: If the template parameter is not a reference type, then the normal pointer conversion will be applied to arguments of array or function type. An array argument will be treated as a pointer to its first element, and a function argument will be treated as a pointer to the function’s type.

As examples, consider calls to the functions fobj and fref. The fobj function copies its parameters, whereas fref’s parameters are references:

In the first case, we pass a string and a const string as arguments. Even though these types do not match exactly, both calls are legal. In the call to fobj, the arguments are copied, so whether the original object is const doesn’t matter. In the call to fref, the parameter type is a reference to const. Conversion to const for a reference parameter is one of the acceptable conversions, so this call is also okay.

In the next case, we pass array arguments in which the arrays are different sizes. In the call to fobj, the fact that the arrays are different doesn’t matter. Both arrays are converted to pointers. The template parameter type in fobj is int*. The call to fref, however, is illegal. When the parameter is a reference (Section 7.2.4, p. 240), the arrays are not converted to pointers. The types of a and b don’t match, so the call is in error.

Normal Conversions Apply for Nontemplate Arguments

Normal conversions (Section 7.1.2, p. 229) are allowed for parameters defined using ordinary types. The following function template sum has two parameters:

The first parameter, op1, has a template parameter type. Its actual type cannot be known until the function is used. The type of the second parameter, op2, is known: It’s int.

Because the type of op2 is fixed, normal conversions can be applied to arguments passed to op2 when sum is called:

In the first two calls, the type of the second argument d is not the same as the type of the corresponding function parameter. However, these calls are okay: There is a conversion from double to int. Because the type of the second parameter does not depend on a template parameter, the compiler will implicitly convert d. The first call causes the function sum(int, int) to be instantiated; sum(double, int) is instantiated by the second call.

The third call is an error. There is no conversion from string to int. Using a string argument to match an int parameter is, as usual, illegal.

Template Argument Deduction and Function Pointers

We can use a function template to initialize or assign to a function pointer (Section 7.9, p. 276). When we do so, the compiler uses the type of the pointer to instantiate a version of the template with the appropriate template argument(s).

As an example, assume we have a function pointer that points to a function returning an int that takes two parameters, each of which is a reference to a const int. We could use that pointer to point to an instantiation of compare:

     template <typename T> int compare(const T&, const T&);
     // pf1 points to the instantiation int compare (const int&, const int&)
     int (*pf1) (const int&, const int&) = compare;

The type of pf1 is “pointer to function returning an int taking two parameters of type const int&.” The type of the parameters in pf1 determines the type of the template argument for T. The template argument for T is int. The pointer pf1 refers to the instantiation with T bound to int.

It is an error if the template arguments cannot be determined from the function pointer type. For example, assume we have two functions named func. Each function takes a pointer to function argument. The first version of func takes a pointer to a function that has two const string reference parameters and returns a string. The second version of func takes a pointer to a function taking two const int reference parameters and returning an int. We cannot use compare as an argument to func:

The problem is that by looking at the type of func’s parameter, it is not possible to determine a unique type for the template argument. The call to func could instantiate either of the following functions:

     compare(const string&, const string&)
     compare(const int&, const int&)

Because it is not possible to identify a unique instantiation for the argument to func, this call is a compile-time (or link-time) error.

16.2.2 Function-Template Explicit Arguments

In some situations, it is not possible to deduce the types of the template arguments. This problem arises most often when a function return type must be a type that differs from any used in the parameter list. In such situations, it is necessary to override the template argument deduction mechanism and explicitly specify the types or values to be used for the template parameters.

Specifying an Explicit Template Argument

Consider the following problem. We wish to define a function template called sum that takes arguments of two different types. We’d like the return type to be large enough to contain the sum of two values of any two types passed in any order. How can we do that? How should we specify sum’s return type?

     // T or U as the returntype?
     template <class T, class U> ??? sum(T, U);

In this case, the answer is that neither parameter works all the time. Using either parameter is bound to fail at some point:

One approach to solving this problem would be to force callers of sum to cast (Section 5.12.4, p. 183) the smaller type to the type we wish to use as the result:

Using a Type Parameter for the Return Type

An alternative way to specify the return type is to introduce a third template parameter that must be explicitly specified by our caller:

This version adds a template parameter to specify the return type. There is only one catch: There is no argument whose type can be used to infer the type of T1. Instead, the caller must explicitly provide an argument for this parameter on each call to sum.

We supply an explicit template argument to a call in much the same way that we define an instance of a class template. Explicit template arguments are specified in a comma-separated list, bracketed by the less-than (<) and greater-than (>) tokens. The list of explicit template types appears after the function name and before the argument list:

This call explicitly specifies the type for T1. The compiler deduces the types for T2 and T3 from the arguments passed in the call.

Explicit template argument(s) are matched to corresponding template parameter(s) from left to right; the first template argument is matched to the first template parameter, the second argument to the second parameter, and so on. An explicit template argument may be omitted only for the trailing (rightmost) parameters, assuming these can be deduced from the function parameters. If our sum function had been written as

then we would always have to specify arguments for all three parameters:

Explicit Arguments and Pointers to Function Templates

Another example where explicit template arguments would be useful is the ambiguous program from page 641. We could disambiguate that case by using explicit template argument:

As before, we want to pass an instantiation of compare in the call to the overloaded function named func. It is not possible to select which instantiation of compare to pass by looking at the parameter lists for the different versions of func. Two different instantiations of compare could satisfy the call. The explicit template argument indicates which instantiation of compare should be used and which func function is called.

16.3 Template Compilation Models

When the compiler sees a template definition, it does not generate code immediately. The compiler produces type-specific instances of the template only when it sees a use of the template, such as when a function template is called or an object of a class template is defined.

Ordinarily, when we call a function, the compiler needs to see only a declaration for the function. Similarly, when we define an object 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 must have access to the source code that defines the template. When we call a function template or a member function of a class template, the compiler needs the function definition. It needs the code we normally put in the source files.

Standard C++ defines two models for compiling template code. In each of these models, we structure our programs in largely the same way: Class definitions and function declarations go in header files, and function and member definitions go in source files. The two models differ in how the definitions from the source files are made available to the compiler. As of this writing, all compilers support the first model, known as the “inclusion” model; only some compilers support the second, “separate compilation” model.

Inclusion Compilation Model

In the inclusion compilation model, the compiler must see the definition for any template that is used. Typically, we make the definitions available by adding a #include directive to the headers that declare function or class templates. That #include brings in the source file(s) that contain the associated definitions:

This strategy lets us maintain the separation of header files and implementation files but ensures that the compiler will see both files when compiling code that uses the templates.

Some, especially older, compilers that use the inclusion model may generate multiple instantiations. If two or more separately compiled source files use the same template, these compilers will generate an instantiation for the template in each file. Ordinarily, this approach implies that a given template will be instantiated more than once. At link time, or during a prelink phase, the compiler selects one instantiation, discarding the others. In such cases, compile-time performance can be significantly degraded if there are a lot of files that instantiate the same template. This compile-time degradation is unlikely to be a problem on modern computers for many applications. However, in the context of large systems, the compile-time hit may become important.

Such compilers often support mechanisms that avoid the compile-time overhead implicit in multiple instantiations of the same template. The way compilers optimize compile-time performance varies from one compiler to the next. If compile time for programs using templates is too burdensome, consult your compiler’s user’s guide to see what support your compiler offers to avoid redundant instantiations.

Separate Compilation Model

In the separate compilation model, the compiler keeps track of the associated template definitions for us. However, we must tell the compiler to remember a given template definition. We use the export keyword to do so.

The export keyword indicates that a given definition might be needed to generate instantiations in other files. A template may be defined as exported only once in a program. The compiler figures out how to locate the template definition when it needs to generate these instantiations. The export keyword need not appear on the template declaration.

Ordinarily, we indicate that a function template is exported as part of its definition. We do so by including the keyword export before the template keyword:

The declaration for this function template, should, as usual, be put in a header. The declaration must not specify export.

Using export on a class template is a bit more complicated. As usual, the class declaration must go in a header file. The class body in the header should not use the export keyword. If we used export in the header, then that header could be used by only one source file in the program.

Instead, we export the class in the class implementation file:

The members of an exported class are automatically declared as exported. It is also possible to declare individual members of a class template as exported. In this case, the keyword export is not specified on the class template itself. It is specified only on the specific member definitions to be exported. The definition of exported member functions need not be visible when the member is used. The definitions of any nonexported member must be treated as in the inclusion model: The definition should be placed inside the header that defines the class template.

16.4 Class Template Members

So far we have seen only how to declare the interface members of our Queue class template. In this section, we’ll look at how we might implement the class.

Queue Implementation Strategy

Our implementation, shown in Figure 16.1 on the next page, uses two classes:

Figure 16.1. Queue Implementation

1. Class QueueItem will represent a node in Queue’s linked list. This class has two data members: item and next:

   • item holds the value of the element in the Queue; its type varies with each instance of Queue.

   • next is a pointer to the next QueueItem object in the queue.

   Each element in the Queue is stored in a QueueItem object.

2. Class Queue will provide the interface functions described in Section 16.1.2 (p. 627). The Queue class will also have two data members: head and tail. These members are pointers to QueueItem.

As do the standard containers, our Queue class will copy the values it’s given.

The QueueItem Class

We’ll start our implementation by writing the QueueItem class:

As it stands, this class is already complete: It holds two data elements, which its constructor initializes. Like Queue, QueueItem is a class template. The class uses its template parameter to name the type of its item member. The value of each element in the Queue will be stored in item.

Each time we instantiate a Queue class, the same version of QueueItem will be instantiated as well. For example, if we create Queue<int>, then a companion class, QueueItem<int>, will be instantiated.

Class QueueItem is a private class—it has no public interface. We intend this class to be used to implement Queue and have not built it for general use. Hence, it has no public members. We’ll need to make class Queue a friend of QueueItem so that its members can access the members of QueueItem. We’ll see how to do so in Section 16.4.4 (p. 658).

The Queue Class

We can now flesh out our Queue class:

In addition to the interface members, we have added the three copy-control members (Chapter 13) and associated utility functions used by those members. The private utility functions destroy and copy_elems will do the work of freeing the elements in the Queue and copying elements from another Queue into this one. The copy-control members are needed to manage the data members, head and tail, which are pointers to the first and last elements in the Queue. These elements are values of type QueueItem<Type>.

The class implements several of its member functions:

• The default constructor sets both head and tail pointers to zero, indicating that the Queue is currently empty.

• The copy constructor initializes head and tail, and calls copy_elems to copy the elements from its initializer.

• The front functions return the value at the head of the Queue. These functions do no checking: As with the analogous operations in the standard queue, users may not run front on an empty Queue.

• The empty function returns the result of comparing head with zero. If head is zero, the Queue is empty; otherwise, it is not.

References to a Template Type in the Scope of the Template

For the most part, this class definition should be familiar. It differs little from other classes that we have defined. What is new is the use (or lack thereof) of the template type parameter in references to the Queue and QueueItem types.

Ordinarily, when we use the name of a class template, we must specify the template parameters. There is one exception to this rule: Inside the scope of the class itself, we may use the unqualified name of the class template. For example, in the declarations of the default and copy constructor the name Queue is a shorthand notation that stands for Queue<Type>. Essentially the compiler infers that when we refer to the name of the class, we are referring to the same version. Hence, the copy constructor definition is really equivalent to writing:

The compiler performs no such inference for the template parameter(s) for other templates used within the class. Hence, we must specify the type parameter when declaring pointers to the companion QueueItem class:

These declarations say that for a given instantiation of class Queue, head and tail point to an object of type QueueItem instantiated for the same template parameter. That is, the type of head and tail inside the Queue<int> instantiation is QueueItem<int>*. It would be an error to omit the template parameter in the definition of the head and tail members:

16.4.1 Class-Template Member Functions

The definition of a member function of a class template has the following form:

• It must start with the keyword template followed by the template parameter list for the class.

• It must indicate the class of which it is a member.

• The class name must include its template parameters.

From these rules, we can see that a member function of class Queue defined outside the class will start as

     template <class T> ret-type Queue<T>::member-name

The destroy Function

To illustrate a class template member function defined outside its class, let’s look at the destroy function:

This definition can be read from left to right as:

• Defining a function template with a single type parameter named Type

• that returns void,

• which is in the scope of the Queue<Type> class template.

The use of Queue<Type> preceding the scope operator (::) names the class to which the member function belongs.

Following the member-function name is the function definition. In the case of destroy, the function body looks very much like an ordinary nontemplate function definition. Its job is to walk the list of entries in this Queue, calling pop to remove each item.

The pop Function

The pop member removes the value at the front of the Queue:

The pop function assumes that users do not call pop on an empty Queue. The job of pop is to remove the element at the start of the Queue. We must reset the head pointer to point to the next element in the Queue, and then delete the element that had been at the head. The only tricky part is remembering to keep a separate pointer to that element so we can delete it after resetting the head pointer.

The push Function

The push member places a new item at the back of the queue:

This function starts by allocating a new QueueItem, which is initialized from the value we were passed. There’s actually a surprising bit of work going on in this statement:

1. The QueueItem constructor copies its argument into the QueueItem’s item member. As do the standard containers, our Queue class stores copies of the elements it is given.
2. If item is a class type, the initialization of item uses the copy constructor of whatever type item has.
3. The QueueItem constructor also initializes the next pointer to 0 to indicate that this element points to no other QueueItem.

Because we’re adding the element at the end of the Queue, setting next to 0 is eactly what we want.

Having created and initialized a new element, we must next hook it into the Queue. If the Queue is empty, then both head and tail should point to this new element. If there are already other elements in the Queue, then we make the current tail element point to this new element. The old tail is no longer the last element, which we indicate by making tail point to the newly constructed element as well.

The copy Function

Aside from the assignment operator, which we leave as an exercise, the only remaining function to write is copy_elems. This function is designed to be used by the assignment operator and copy constructor. Its job is to copy the elements from its parameter into this Queue:

We copy the elements in a for loop that starts by setting pt equal to the parameter’s head pointer. The for continues until pt is 0, which happens after we get to the element that is the last one in orig. For each element in orig, we push a copy of value in that element onto this Queue and advance pt to point to the next element in orig.

Instantiation of Class-Template Member Functions

Member functions of class templates are themselves function templates. Like any other function template, a member function of a class template is used to generate instantiations of that member. Unlike other function templates, the compiler does not perform template-argument deduction when instantiating class template member functions. Instead, the template parameters of a class template member function are determined by the type of the object on which the call is made. For example, when we call the push member of an object of type Queue<int>, the push function that is instantiated is

     void Queue<int>::push(const int &val)

The fact that member-function template parameters are fixed by the template arguments of the object means that calling a class template member function is more flexible than comparable calls to function templates. Normal conversions are allowed on arguments to function parameters that were defined using the template parameter:

When Classes and Members Are Instantiated

Member functions of a class template are instantiated only for functions that are used by the program. If a function is never used, then that member function is never instantiated. This behavior implies that types used to instantiate a template need to meet only the requirements of the operations that are actually used. As an example, recall the sequential container constructor (Section 9.1.1, p. 309) that takes only a size parameter. That constructor uses the default constructor for the element type. If we have a type that does not define the default constructor, we may still define a container to hold this type. However, we may not use the constructor that takes only a size.

When we define an object of a template type, that definition causes the class template to be instantiated. Defining an object also instantiates whichever constructor was used to initialize the object, along with any members called by that constructor:

The first statement instantiates the Queue<string> class and its default constructor. The next statement instantiates the push member function.

The instantiation of the push member:

in turn instantiates the companion QueueItem<string> class and its constructor.

The QueueItem members in Queue are pointers. Defining a pointer to a class template doesn’t instantiate the class; the class is instantiated only when we use such a pointer. Thus, QueueItem is not instantiated when we create a Queue object. Instead, the QueueItem class is instanatiated when a Queue member such as front, push, or pop is used.

16.4.2 Template Arguments for Nontype Parameters

Now that we’ve seen more about how class templates are implemented, we can look at nontype parameters for class templates. We’ll do so by defining a new version of the Screen class first introduced in Chapter 12. In this case, we’ll redefine Screen to be a template, parameterized by its height and width:

This template has two parameters, both of which are nontype parameters. When users define Screen objects, they must provide a constant expression to use for each of these parameters. The class uses these parameters in the default constructor to set the size of the default Screen.

As with any class template, the parameter values must be explicitly stated whenever we use the Screen type:

     Screen<24,80> hp2621; // screen 24 lines by 80 characters

The object hp2621 uses the template instantiation Screen<24, 80>. The template argument for hi is 24, and the argument for wid is 80. In both cases, the template argument is a constant expression.

16.4.3 Friend Declarations in Class Templates

There are three kinds of friend declarations that may appear in a class template. Each kind of declaration declares friendship to one or more entities:

1. A friend declaration for an ordinary nontemplate class or function, which grants friendship to the specific named class or function.
2. A friend declaration for a class template or function template, which grants access to all instances of the friend.
3. A friend declaration that grants access only to a specific instance of a class or function template.

Ordinary Friends

A nontemplate class or function can be a friend to a class template:

This declaration says that the members of FooBar and the function fcn may access the private and protected members of any instantiation of class Bar.

General Template Friendship

A friend can be a class or function template:

These friend declarations use a different type parameter than does the class itself. That type parameter refers to the type parameter of Foo1 and templ_fcn1. In both these cases, an unlimited number of classes and functions are made friends to Bar. The friend declaration for Foo1 says that any instance of Foo1 may access the private elements of any instance of Bar. Similarly, any instance of templ_fcn1 may access any instance of Bar.

This friend declaration establishes a one-to-many mapping between each instantiation of Bar and its friends, Foo1 and templ_fcn1. For each instantiation of Bar, all instantiations of Foo1 or templ_fcn1 are friends.

Specific Template Friendship

Rather than making all instances of a template a friend, a class can grant access to only a specific instance:

Even though Foo2 itself is a class template, friendship is extended only to the specific instance of Foo2 that is parameterized by char*. Similarly, the friend declaration for templ_fcn2 says that only the instance of that function parameterized by char* is a friend to class Bar. The specific instantiations of Foo2 and templ_fcn2 parameterized by char* can access every instantiation of Bar.

More common are friend declarations of the following form:

These friends define friendship between a particular instantiation of Bar and the instantiation of Foo3 or templ_fcn3 that uses the same template argument. Each instantiation of Bar has a single associated Foo3 and templ_fcn3 friend:

     Bar<int> bi;    // Foo3<int> and templ_fcn3<int> are friends
     Bar<string> bs; // Foo3<string>, templ_fcn3<string> are friends

Only those versions of Foo3 or templ_fcn3 that have the same template argument as a given instantiation of Bar are friends. Thus, Foo3<int> may access the private parts of Bar<int> but not of Bar<string> or any other instantiation of Bar.

Declaration Dependencies

When we grant access to all instances of a given template, there need not be a declaration for that class or function template in scope. Essentially, the compiler treats the friend declaration as a declaration of the class or function as well.

When we want to restrict friendship to a specific instantiation, then the class or function must have been declared before it can be used in a friend declaration:

If we have not previously told the compiler that the friend is a template, then the compiler will infer that the friend is an ordinary nontemplate class or function.

16.4.4 Queue and QueueItem Friend Declarations

Our QueueItem class is not intended to be used by the general program: All its members are private. In order for Queue to use QueueItem, QueueItem must make Queue a friend.

Making a Class Template a Friend

As we have just seen, when making a class template a friend, the class designer must decide how wide to make that friendship. In the case of QueueItem, we need to decide whether QueueItem should grant friendship to all Queue instances or only to a specific instance.

Making every Queue a friend of each QueueItem is too broad. It makes no sense to allow a Queue instantiated with the type string to access members of a QueueItem instantiated with type double. The Queue<string> instantiation should be a friend only to the instantiation of the QueueItem for strings. That is, we want a one-to-one mapping between a Queue and QueueItem for each type of Queue that is instantiated:

This declaration establishes the desired one-to-one mapping; only the Queue class that is instantiated with the same type as QueueItem is made a friend.

The Queue Output Operator

One operation that might be useful to add to our Queue interface is the ability to print the contents of a Queue object. We’ll do so by providing an overloaded instance of the output operator. This operator will walk the list of elements in the Queue and print the value in each element. We’ll print the elements inside a pair of brackets.

Because we want to be able to print the contents of Queues of any type, we need to make the output operator a template as well:

If a Queue of type int contains the values 3, 5, 8, and 13, the output of this Queue displays as follows:

     <3 5 8 13 >

If the Queue is empty, the for loop body is never executed. The effect will be to print an empty pair of brackets if the Queue is empty.

Making a Function Template a Friend

The output operator needs to be a friend of both the Queue and QueueItem classes. It uses the head member of class Queue and the next and item members of class QueueItem. Our classes grant friendship to the specific instance of the output operator instantiated with the same type:

Each friend declaration grants access to the corresponding instantiation of the operator<<. That is, the output operator that prints a Queue<int> is a friend to class Queue<int> (and QueueItem<int>). It is not a friend to any other Queue type.

Type Dependencies and the Output Operator

The Queue output operator<< relies on the operator<< of item to actually print each element:

     os << p->item << " ";

When we use p->item as an operand of the << operator, we are using the << defined for whatever type item has.

This code is an example of a type dependency between Queue and the element type that Queue holds. In effect, each type bound to Queue that uses the Queue output operator must itself have an output operator. There is no language mechanism to specify or enforce that dependency in the definition of Queue itself. It is legal to create a Queue for a class that does not define the output operator but it is a compile-time (or link-time) error to print a Queue holding such a type.

16.4.5 Member Templates

Any class (template or otherwise) may have a member that is itself a class or function template. Such members are referred to as member templates. Member templates may not be virtual.

One example of a member template is the assign (Section 9.3.8, p. 328) member of the standard containers. The version assign that takes two iterators uses a template parameter to represent the type of its iterator parameters. Another member template example is the container constructor that takes two iterators (Section 9.1.1, p. 307). This constructor and the assign member allow containers to be built from sequences of different but compatible element types and/or different container types. Having implemented our own Queue class, we now can understand the design of these standard container members a bit better.

Consider the Queue copy constructor: It takes a single parameter that is a reference to a Queue<Type>. If we wanted to create a Queue by copying elements from a vector, we could not do so; there is no conversion from vector to Queue. Similarly, if we wanted to copy elements from a Queue<short> into a Queue<int>, we could not do so. Again, even though we can convert a short to an int, there is no conversion from Queue<short> to Queue<int>. The same logic applies to the Queue assignment operator, which also takes a parameter of type Queue<Type>&.

The problem is that the copy constructor and assignment operator fix both the container and element type. We’d like to define a constructor and an assign member that allow both the container and element type to vary. When we need a parameter type to vary, we need to define a function template. In this case, we’ll define the constructor and assign member to take a pair of iterators that denote a range in some other sequence. These functions will have a single template type parameter that represents an iterator type.

Defining a Member Template

A template member declaration looks like the declaration of any template:

The member declaration starts with its own template parameter list. The constructor and assign member each have a single template type parameter. These functions use that type parameter as the type for their function parameters, which are iterators denoting a range of elements to copy.

Defining a Member Template Outside the Class

Like nontemplate members, a member template can be defined inside or outside of its enclosing class or class template definition. We have defined the constructor inside the class body. Its job is to copy the elements from the iterator range formed by its iterator arguments. It does so by calling the iterator version of copy_elems to do the actual copy.

When we define a member template outside the scope of a class template, we must include both template parameter lists:

When a member template is a member of a class template, then its definition must include the class-template parameters as well as its own template parameters. The class-template parameter list comes first, followed by the member’s own template parameter list. The definition of assign starts with

     template <class T> template <class Iter>

The first template parameter list— template<class T>—is that of the class template. The second template parameter list— template<class Iter>—is that of the member template.

The actions of our assign function are quite simple: It first calls destroy, which, as we’ve seen, frees the existing members of this Queue. The assign member then calls a new utility function named copy_elems to do the work of copying elements from the input range. That function is also a member template:

The iterator version of copy_elems walks through an input range denoted by a pair of iterators. It calls push on each element in that range, which actually adds the element to the Queue.

Member Templates Obey Normal Access Control

A member template follows the same access rules as any other class members. If the member template is private, then only member functions and friends of the class can use that member template. Because the function member template assign is a public member, it can be used by the entire program; copy_elems is private, so it can be accessed only by the friends and members of Queue.

Member Templates and Instantiation

Like any other member, a member template is instantiated only when it is used in a program. The instantiation of member templates of class templates is a bit more complicated than the instantiation of plain member functions of class templates. Member templates have two kinds of template parameters: Those that are defined by the class and those defined by the member template itself. The class template parameters are fixed by the type of the object through which the function is called. The template parameters defined by the member act like parameters of ordinary function templates. These parameters are resolved through normal template argument deduction (Section 16.2.1, p. 637).

To understand how instantiation works, let’s look at uses of these members to copy and assign elements from an array of shorts or a vector<int>:

Because we are constructing an object of type Queue<int>, we know that the compiler will instantiate the iterator-based constructor for Queue<int>. The type of the constructor’s own template parameter is deduced by the compiler from the type of a and a +4. That type is pointer to short. Thus, the definition of qi instantiates

     void Queue<int>::Queue(short *, short *);

The effect of this constructor is to copy the elements of type short from the array named a into qi.

The call to assign instantiates a member of qi, which has type Queue<int>. Thus, this call instantiates the Queue<int> member named assign. That function is itself a function template. As with any other function template, the compiler deduces the template argument for assign from the arguments to the call. The type deduced is vector<int>::iterator, meaning that this call instantiates

16.4.6 The Complete Queue Class

For completeness, here is the final definition of our Queue class:

Members that are not defined in the class itself can be found in earlier sections of this chapter; the comment following such members indicates the page on which the definition can be found.

16.4.7 static Members of Class Templates

A class template can declare static members (Section 12.6, p. 467) in the same way as any other class:

defines a class template named Foo that among other members has a public static member function named count and a private static data member named ctr.

Each instantiation of class Foo has its own static member:

     // Each object shares the same Foo<int>::ctrand Foo<int>::count members
     Foo<int> fi, fi2, fi3;
     // has static members Foo<string>::ctrand Foo<string>::count
     Foo<string> fs;

Each instantiation represents a distinct type, so there is one static shared among the objects of any given instantiation. Hence, any objects of type Foo<int> share the same static member ctr. Objects of type Foo<string> share a different ctr member.

Using a static Member of a Class Template

As usual, 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, when we attempt to use the static member through the class, we must refer to an actual instantiation:

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

Defining a static Member

As with any other static data member, there must be a definition for the data member that appears outside the class. In the case of a class template static, the member definition must indicate that it is for a class template:

     template <class T>
     size_t Foo<T>::ctr = 0; // define and initialize ctr

A static data member is defined like any other member of a class template that is defined outside the class. It begins with the keyword template followed by the class template parameter list and the class name. In this case, the name of the static data member is prefixed by Foo<T>::, which indicates that the member belongs to the class template Foo.

16.5 A Generic Handle Class

In Chapter 15 we defined two handle classes: the Sales_item (Section 15.8, p. 598) class and the Query (Section 15.9, p. 607) class. These classes managed pointers to objects in an inheritance hierarchy. Users of the handle did not have to manage the pointers to those objects. User code was written in terms of the handle class. The handle dynamically allocated and freed objects of the related inheritance classes and forwarded all “real” work back to the classes in the underlying inheritance hierarchy.

These handles were similar to but different from each other: They were similar in that each defined use-counted copy control to manage a pointer to an object of a type in an inheritance hierarchy. They differed with respect to the interface they provided to users of the inheritance hierarchy.

The use-counting implementation was the same in both classes. This kind of problem is well suited to generic programming: We could define a class template to manage a pointer and do the use-counting. Our otherwise unrelated Sales_item and Query types could be simplified by using that template to do the common use-counting work. The handles would remain different as to whether they reveal or hide the underlying inheritance hierarchy.

In this section, we’ll implement a generic handle class to provide the operations that manage the use count and the underlying objects. Then we’ll rewrite the Sales_item class, showing how it could use the generic handle rather than defining its own use-counting operations.

16.5.1 Defining the Handle Class

Our Handle class will behave like a pointer: Copying a Handle will not copy the underlying object. After the copy, both Handles will refer to the same underlying object. To create a Handle, a user will be expected to pass the address of a dynamically allocated object of the type (or a type derived from that type) managed by the Handle. From that point on, the Handle will “own” the given object. In particular, the Handle class will assume responsibility for deleting that object once there are no longer any Handles attached to it.

Given this design, here is an implementation of our generic Handle:

This class looks like our other handles, as does the assignment operator.

The only other members our class will define are the dereference and member access operators. These operators will be used to access the underlying object. We’ll provide a measure of safety by having these operations check that the Handle is actually bound to an object. If not, an attempt to access the object will throw an exception.

The nonconst versions of these operators look like:

The const versions would be similar and are left as an exercise.

16.5.2 Using the Handle

We intend this class to be used by other classes in their internal implementations. However, as an aid to understanding how the Handle class works, we’ll look at a simpler example first. This example illustrates the behavior of the Handle by allocating an int and binding a Handle to that newly allocated object:

Even though the user of Handle allocates the int, the Handle destructor will delete it. In this code, the int is deleted at the end of the outer block when the last Handle goes out of scope. To access the underlying object, we apply the Handle * operator. That operator returns a reference to the underlying int object.

Using a Handle to Use-Count a Pointer

As an example of using Handle in a class implementation, we might reimplement our Sales_item class (Section 15.8.1, p. 599). This version of the class defines the same interface, but we can eliminate the copy-control members by replacing the pointer to Item_base by a Handle<Item_base>:

Although the interface to the class is unchanged, its implementation differs considerably from the original:

• Both classes define a default constructor and a constructor that takes a const reference to an Item_base object.

• Both define overloaded * and -> operators as const members.

The Handle-based version of Sales_item has a single data member. That data member is a Handle attached to a copy of the Item_base object given to the constructor. Because this version of Sales_item has no pointer members, there is no need for copy-control members. This version of Sales_item can safely use the synthesized copy-control members. The work of managing the use-count and associated Item_base object is done inside Handle.

Because the interface is unchanged, there is no need to change code that uses Sales_item. For example, the program we wrote in Section 15.8.3 (p. 603) can be used without change:

It’s worthwhile to look in detail at the statement that calls net_price:

     sum += (*iter)->net_price(items.count(*iter));

This statement uses operator -> to fetch and run the net_price function. What’s important to understand is how this operator works:

• (*iter) returns h, our use-counted handle member.

• (*iter)-> therefore uses the overloaded arrow operator of the handle class

• The compiler evaluates h.operator->(), which in turn yields the pointer to Item_base that the Handle holds.

• The compiler dereferences that Item_base pointer and calls the net_price member for the object to which the pointer points.

16.6 Template Specializations

It is not always possible to write a single template that is best suited for every possible template argument with which the template might be instantiated. In some cases, the general template definition is simply wrong for a type. The general definition might not compile or might do the wrong thing. At other times, we may be able to take advantage of some specific knowledge about a type to write a more efficient function than the one that is instantiated from the template.

Our compare function and our Queue class are both good examples of the problem: Neither works correctly when used with C-style character strings. Let’s look again at our compare function template:

If we call this template definition on two const char* arguments, the function compares the pointer values. It will tell us the relative positions in memory of these two pointers but says nothing about the contents of the arrays to which the pointers point.

To get be able to use compare with character strings, we would have to provide a specialized definition that knows how to compare C-style strings. The fact that these versions are specialized is transparent to users of these templates. Calls to a specialized function or use of a specialized class are indistinguishable from uses of a version instantiated from the general template.

16.6.1 Specializing a Function Template

A template specialization is a separate definition in which the actual type(s) or value(s) of one or more template parameter(s) is (are) specified. The form of a specialization is:

• The keyword template followed by an empty bracket pair (<>),

• followed by the template name and a bracket pair specifying the template parameters(s) that this specialization defines,

• the function parameter list,

• and the function body.

The following program defines a specialization of compare when the template parameter type is bound to const char*:

The declaration for the specialization must match that of the corresponding template. In this case, the template has one type parameter and two function parameters. The function parameters are const references to the type parameter. Here we are fixing the type parameter to const char*; our function parameters, therefore, are const references to a const char*.

Now when we call compare, passing it two character pointers, the compiler will call our specialized version. It will call the generic version for any other argument types (including plain char*):

Declaring a Template Specialization

As with any function, we can declare a function template specialization without defining it. A template specialization declaration looks like the definition but omits the function body:

This declaration consists of an empty template parameter list (template<>) followed by the return type, the function name (optionally) followed by explicit template argument(s) specified inside a pair of angle brackets, and the function parameter list. A template specialization must always include the empty template parameter specifier, template<>, and it must include the function parameter list. If the template arguments can be inferred from the function parameter list, there is no need to explicitly specify the template arguments:

Function Overloading versus Template Specializations

Omitting the empty template parameter list, template<>, on a specialization may have surprising effects. If the specialization syntax is missing, then the effect is to declare an overloaded nontemplate version of the function:

     // generic template definition
     template <class T>
     int compare(const T& t1, const T& t2) { /* ... */ }

     // OK: ordinary function declaration
     int compare(const char* const&, const char* const&);

The definition of compare does not define a template specialization. Instead, it declares an ordinary function with a return type and a parameter list that could match those of a template instantiation.

We’ll look at the interaction of overloading and templates in more detail in the next section. For now, what’s important to know is that when we define a nontemplate function, normal conversions are applied to the arguments. When we specialize a template, conversions are not applied to the argument types. In a call to a specialized version of a template, the argument type(s) in the call must match the specialized version function parameter type(s) exactly. If they don’t, then the compiler will instantiate an instantiation for the argument(s) from the template definition.

Duplicate Definitions Cannot Always Be Detected

If a program consists of more than one file, the declaration for a template specialization must be visible in every file in which the specialization is used. A function template cannot be instantiated from the generic template definition in some files and be specialized for the same set of template arguments in other files.

Ordinary Scope Rules Apply to Specializations

Before we can declare or define a specialization, a declaration for the template that it specializes must be in scope. Similarly, a declaration for the specialization must be in scope before that version of the template is called:

This program is in error because a call that would match the specialization is made before the specialization is declared. When the compiler sees a call, it must know to expect a specialization for this version. Otherwise, the compiler is allowed to instantiate the function from the template definition.

It is an error for a specialization to appear after a call to that instance of the template has been seen.

16.6.2 Specializing a Class Template

Our Queue class has a problem similar to the one in compare when used with C-style strings. In this case, the problem is in the push function. That function copies the value it’s given to create a new element in the Queue. By default, copying a C-style character string copies only the pointer, not the characters. Copying a pointer in this case has all the problems that shared pointers have in other contexts. The most serious is that if the pointer points to dynamic memory, it’s possible for the user to delete the array to which the pointer points.

Defining a Class Specialization

One way to provide the right behavior for Queue’s of C-style strings is to define a specialized version of the entire class for const char*:

This implementation gives Queue a single data element: a Queue of strings. The various members delegate their work to this member—for example, pop is implemented by calling pop on real_queue.

This version of the class does not define the copy-control members. Its only data element has a class type that does the right thing when copied, assigned, or destroyed; we can use the synthesized copy-control members.

Our Queue class implements mostly, but not entirely, the same interface as the template version of Queue. The difference is that we return a string rather than a char* from the front members. We do so to avoid having to manage the character array that would be required if we wanted to return a pointer.

It is worth noting that a specialization may define completely different members than the template itself. If a specialization fails to define a member from the template, that member may not be used on objects of the specilization type. The member definitions of the class template are not used to create the definitions for the members of an explicit specialization.

Class Specialization Definition

Our class defines only one member outside the class:

Although it does little obvious work, this function implicitly copies the character array to which val points. The copy is made in the call to real_queue.push, which creates a new string from the const char* argument. That argument uses the string constructor that takes a const char*. The string constructor copies the characters from the array pointed to by val into an unnamed string that will be stored in the element we push onto real_queue.

16.6.3 Specializing Members but Not the Class

If we look a bit more deeply at our class, we can see that we can simplify our code: Rather than specializing the whole template, we can specialize just the push and pop members. We’ll specialize push to copy the character array and pop to free the memory we used for that copy:

Now, the class type Queue<const char*> will be instantiated from the generic class template definition, with the exception of the push and pop functions. When we call push or pop on a Queue<const char*>, then the specialized version will be called. When we use any other member, the generic one will be instantiated for const char* from the class template.

Specialization Declarations

Member specializations are declared just as any other function template specialization. They must start with an empty template parameter list:

     // push and pop specialized for const char*
     template <>
     void Queue<const char*>::push(const char* const &);
     template <> void Queue<const char*>::pop();

These declarations should be placed in the Queue header file.

16.6.4 Class-Template Partial Specializations

If a class template has more than one template parameter, we might want to specialize some but not all of the template parameters. We can do so using a class template partial specialization:

A class template partial specialization is itself a template. The definition of a partial specialization looks like a template definition. Such a definition begins with the keyword template followed by a template parameter list enclosed by angle brackets (<>). The parameter list of a partial specialization is a subset of the parameter list of the corresponding class template definition. The partial specialization for some_template has only one template type parameter named T1. The second template argument for T2 is known to be int. The template parameter list for the partial specialization only lists the parameters for which the template arguments are still unknown.

Using a Class-Template Partial Specialization

The partial specialization has the same name as the class template to which it corresponds—namely, some_template. The name of the class template must be followed by a template argument list. In the previous example, the template argument list is <T1,int>. Because the argument value for the first template parameter is unknown, the argument list uses the name of the template parameter T1 as a placeholder. The other argument is the type int, for which the template is partially specialized.

As with any other class template, a partial specialization is instantiated implicitly when used in a program:

Notice that the type of the second variable, some_template parameterized by string and int, could be instantiated from the generic class template definition as well as from the partial specialization. Why is it that the partial specialization is chosen to instantiate the template? When a parital specialization is declared, the compiler chooses the template definition that is the most specialized for the instantiation. When no partial specialization can be used, the generic template definition is used. The instantiated type of foo does not match the partial specialization provided. Thus, the type of foo must be instantiated from the general class template, binding int to T1 and string to T2. The partial specialization is only used to instantiate some_template types with a second type of int.

The definition of a partial specialization is completely disjointed from the definition of the generic template. The partial specialization may have a completely different set of members from the generic class template. The generic definitions for the members of a class template are never used to instantiate the members of the class template partial specialization.

16.7 Overloading and Function Templates

A function template can be overloaded: We can define multiple function templates with the same name but differing numbers or types of parameters. We also can define ordinary nontemplate functions with the same name as a function template.

Of course, declaring a set of overloaded function templates does not guarantee that they can be called successfully. Overloaded function templates may lead to ambiguities.

Function Matching and Function Templates

The steps used to resolve a call to an overloaded function in which there are both ordinary functions and function templates are as follows:

1. Build the set of candidate functions for this function name, including:

   (a) Any ordinary function with the same name as the called function.

   (b) Any function-template instantiation for which template argument deduction finds template arguments that match the function arguments used in the call.

2. Determine which, if any, of the ordinary functions are viable (Section 7.8.2, p. 269). Each template instance in the candidate set is viable, because template argument deduction ensures that the function could be called.
3. Rank the viable functions by the kinds of conversions, if any, required to make the call, remembering that the conversions allowed to call an instance of a template function are limited.

   (a) If only one function is selected, call this function.

   (b) If the call is ambiguous, remove any function template instances from the set of viable functions.

4. Rerank the viable functions excluding the function template instantiations.

   • If only one function is selected, call this function.

   • Otherwise, the call is ambiguous.

An Example of Function-Template Matching

Consider the following set of overloaded ordinary and function templates:

The overload set contains three functions: The first template handles simple values, the second template compares elements from two sequences, and the third is an ordinary function to handle C-style character strings.

Resolving Calls to Overloaded Function Templates

We could call these functions on a variety of types:

We’ll look at each call in turn:

compare(1, 0): Both arguments have type int. The candidate functions are the first template instantiated with T bound to int and the ordinary function named compare. The ordinary function, however, isn’t viable—we cannot pass an int to a parameter expecting a char*. The instantiated function using int is an exact match for the call, so it is selected.

     compare(ivec1.begin(), ivec1.end(), ivec2.begin())

compare(ia1, ia1 + 10, ivec1.begin()): In these calls, the only viable function is the instantiation of the template that has three parameters. Neither the template with two arguments nor the ordinary nonoverloaded function can match these calls.

compare(const_arr1, const_arr2): This call, as expected, calls the ordinary function. Both that function and the first template with T bound to const char* are viable. Both are also exact matches. By rule 3b, we know that the ordinary function is preferred. We eliminate the instance of the template from consideration, leaving just the ordinary function as viable.

compare(ch_arr1, ch_arr2): This call also is bound to the ordinary function. The candidates are the version of the function template with T bound to char* and the ordinary function that takes const char* arguments. Both functions require a trivial conversion to convert the arrays, ch_arr1 and ch_arr2, to pointers. Because both functions are equal matches, the plain function is preferred to the template version.

Conversions and Overloaded Function Templates

It can be difficult to design a set of overloaded functions in which some are templates and others are ordinary functions. Doing so requires deep understanding of the relationships among types and in particular of the implicit conversions that may or may not take place when templates are involved.

Let’s look at two examples of why it is hard to design overloaded functions that work properly when there are both template and nontemplate versions in the overload set. First, consider a call to compare using pointers instead of the arrays themselves:

     char *p1 = ch_arr1, *p2 = ch_arr2;
     compare(p1, p2);

This call matches the template version! Ordinarily, we expect to get the same function whether we pass an array or a pointer to an element to that array. In this case, however, the function template is an exact match for the call, binding char* to T. The plain version still requires a conversion from char* to const char*, so the function template is preferred.

Another change that has surprising results is what happens if the template version of compare has a parameter of type T instead of a const reference to T:

     template <typename T> int compare2(T, T);

In this case, if we have an array of plain char; then, whether we pass the array itself or a pointer, the template version is called. The only way to call the non-template version is when the arguments are arrays of const char or pointers to const char*:

In these cases, the plain function and the function template are exact matches. As always, when the match is equally good, the nonoverloaded version is preferred.

Chapter Summary

Templates are a distinctive feature of C++ and are fundamental to the library. A template is a type-independent blueprint that the compiler uses to generate a variety of type-specific instances. We write the template once, and the compiler instantiates the template for the type or types with which we use the template. We can write both function templates and class templates.

Function templates are the base on which the algorithms library is built. Class templates are the base on which the library container and iterator types are built.

Compiling templates requires assistance from the programming environment. The language defines two broad strategies for instantiating templates: the inclusion model and the separate compilation model. These models have impacts on how we build our systems in so far as they dictate whether template definitions go in header files or source files. At this time, all compilers implement the inclusion model, while only some implement the separate compilation model. Your compiler’s user’s guide should specify how your system manages templates.

An explicit template argument lets us fix the type or value of one or more template parameters. Explicit arguments are useful in letting us design functions in which a template type need not be inferred from a corresponding argument and lets us allow conversions on the arguments.

A template specialization is a specialized definition that defines a distinct version of the template that binds one or more parameters to specified types or values. Specializations are useful when there are types for which the default template definition does not apply.

Defined Terms

class template

A class definition that can be used to define a set of type-specific classes. Class templates are defined using the template keyword followed by a comma-separated list of one or more parameters enclosed in < and > brackets.

export keyword

Keyword used to indicate that the compiler must remember the location of the associated template definition. Used by compilers that support the separate-compilation model of template instantiation. The export keyword ordinarily goes with a function definition; a class is normally declared as exported in the associated class implementation file. A template may be defined with the export keyword only once in a program.

function template

A definition for a function that can be used for a variety of types. A function template is defined using the template keyword followed by a comma-separated list of one or more template parameters enclosed in < and > brackets.

generic handle class

A class that holds and manages a pointer to another class. A generic handle takes a single type parameter and allocates and manages a pointer to an object of that type. The handle class defines the necessary copy control members. It also defines the dereference (*) and arrow (->) member access operators to provide access to the underlying object. A generic handle requires no knowledge of the type it manages.

inclusion compilation model

Mechanism used by compilers to find template definitions that relies on template definitions being included in each file that uses the template. Typically, template definitions are stored in a header, and that header must be included in any file that uses the template.

instantiation

Compiler process whereby the actual template argument(s) are used to generate a specific instance of the template in which the parameter(s) are replaced by the corresponding argument(s). Functions are instantiated automatically based on the arguments used in a call. Template arguments must be provided explicitly whenever a class template is used.

member template

A member of a class or class template that is a function template. A member template may not be virtual.

nontype parameter

A template parameter that represents a value. When a function template is instantiated, each nontype parameter is bound to a constant expression as indicated by the arguments used in the call. When a class template is instantiated, each nontype parameter is bound to a constant expression as indicated by the arguments used in the class instantiation.

partial specialization

A version of a class template in which some some but not all of the template parameters are specified.

separate compilation model

Mechanism used by compilers to find template definitions that allows template definitions and declarations to be stored in independent files. Template declarations are placed in a header, and the definition appears only once in the program, typically in a source file. The compiler implements whatever programming environment support is necessary to find that source file and instantiate the versions of the template used by the program.

template argument

Type or value specified when using a template type, such as when defining an object or naming a type in a cast.

template argument deduction

Process by which the compiler determines which function template to instantiate. The compiler examines the types of the arguments that were specified using a template parameter. It automatically instantiates a version of the function with those types or values bound to the template parameters.

template parameter

A name specifed in the template parameter list that may be used inside the definition of a template. Template parameters can be type or non-type parameters. To use a class template, actual arguments must be specified for each template parameter. The compiler uses those types or values to instantiate a version of the class in which uses of the parameter(s) are replaced by the actual argument(s). When a function template is used, the compiler deduces the template arguments from the arguments in the call and instantiates a specific function using the deduced template arguments.

template parameter list

List of type or nontype parameters (separated by commas) to be used in the definition or declaration of a template.

template specialization

Redefinition of a class template or a member of a class template in which the template parameters are specified. A template specialization may not appear until after the class that it specializes has been defined. A template specialization must appear before any use of the template for the specialized arguments is used.

type parameter

Name used in a template parameter list to represent a type. When the template is instantiated, each type parameter is bound to an actual type. In a function template, the types are inferred from the argument types or are explicitly specified in the call. Type arguments must be specified for a class template when the class is used.