Section 16.2. Instantiation

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:

     // simulated version of Queue instantiated for type int
     template <class Type> class Queue<int> {
     public:
         Queue();                  // this bound to Queue<int>*
         int &front();             // return type bound to int
         const int &front() const; // return type bound to int
         void push(const int &);   // parameter type bound to int
         void pop();               // type invariant code
         bool empty() const;       // type invariant code
     private:
         // ...
     };

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.

Each instantiation of a class template constitutes an independent class type. The Queue instantiation for the type int has no relationship to nor any special access to the members of any other Queue type.

Class Template Arguments Are Required

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

     Queue qs; // error: which template instantiation?

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:

     Queue<int> qi;         // ok: defines Queue that holds ints
     Queue<string> qs;      // ok: defines Queue that holds strings

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:

     int main()
     {
        compare(1, 0);             // ok: binds template parameter to int
        compare(3.14, 2.7);        // ok: binds template parameter to double
        return 0;
     }

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:

     int compare(const int &v1, const int &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;
     }

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:

     template <typename T>
     int compare(const T& v1, const T& v2)
     {
         if (v1 < v2) return -1;
         if (v2 < v1) return 1;
         return 0;
     }
     int main()
     {
         short si;
         // error: cannot instantiate compare(short, int)
         // must be: compare(short, short) or
         // compare(int, int)
         compare(si, 1024);
         return 0;
     }

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:

     // argument types can differ, but must be compatible
     template <typename A, typename B>
     int compare(const A& v1, const B& v2)
     {
         if (v1 < v2) return -1;
         if (v2 < v1) return 1;
         return 0;
     }

Now the user may supply arguments of different types:

     short si;
     compare(si, 1024); // ok: instantiates compare(short, int)

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

Limited Conversions on Type Parameter Arguments

Consider the following calls to compare:

     short s1, s2;
     int i1, i2;
     compare(i1, i2);           // ok: instantiate compare(int, int)
     compare(s1, s2);           // ok: instantiate compare(short, short)

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:

     template <typename T> T fobj(T, T); // arguments are copied
     template <typename T>
     T fref(const T&, const T&);       // reference arguments
     string s1("a value");
     const string s2("another value");
     fobj(s1, s2);     // ok: calls f(string, string), const is ignored
     fref(s1, s2);     // ok: non const object s1 converted to const reference
     int a[10], b[42];
     fobj(a, b); // ok: calls f(int*, int*)
     fref(a, b); // error: array types don't match; arguments aren't converted to pointers

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

The restriction on type conversions applies only to those arguments whose types are template parameters.

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

     template <class Type> Type sum(const Type &op1, int op2)
     {
         return op1 + op2;
     }

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:

     double d = 3.14;
     string s1("hiya"), s2(" world");
     sum(1024, d); // ok: instantiates sum(int, int), converts d to int
     sum(1.4, d); // ok: instantiates sum(double, int), converts d to int
     sum(s1, s2); // error: s2 cannot be converted to int

In the first two calls, the type of the second argument dd 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 dd. 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.

When the address of a function-template instantiation is taken, the context must be such that it allows a unique type or value to be determined for each template parameter.

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:

     // overloaded versions of func; each take a different function pointer type
     void func(int(*) (const string&, const string&));
     void func(int(*) (const int&, const int&));
     func(compare); // error: which instantiation of compare?

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.

Exercises Section 16.2.1

Exercise 16.19:
What is instantiation?

Exercise 16.20:
What happens during template argument deduction?

Exercise 16.21:
Name two type conversions allowed on function arguments involved in template argument deduction.

Exercise 16.22:
Given the following templates

template <class Type> Type calc (const Type* array, int size); template <class Type> Type fcn(Type p1,Type p2;

which ones of the following calls, if any, are errors? Why?

double dobj; float fobj; char cobj; int ai[5] = { 511, 16, 8, 63, 34 }; (a) calc(cobj, 'c'); (b) calc(dobj, fobj); (c) fcn(ai, cobj);

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 differnt 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:

     // neither T nor U works as return type
     sum(3, 4L); // second type is larger; want U sum(T, U)
     sum(3L, 4); // first type is larger; want T sum(T, U)

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:

     // ok: now either T or U works as return type
     int i; short s;
     sum(static_cast<int>(s), i); // ok: instantiates int sum(int, int)

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:

     // T1 cannot be deduced: it doesn't appear in the function parameter list
     template <class T1, class T2, class T3>
     T1 sum(T2, T3);

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:

     // ok T1 explicitly specified; T2 and T3 inferred from argument types
     long val3 = sum<long>(i, lng); // ok: calls long sum(int, long)

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

     // poor design: Users must explicitly specify all three template parameters
     template <class T1, class T2, class T3>
     T3 alternative_sum(T2, T1);

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

     // error: can't infer initial template parameters
     long val3 = alternative_sum<long>(i, lng);
     // ok: All three parameters explicitly specified
     long val2 = alternative_sum<long, int, long>(i, lng);

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:

     template <typename T> int compare(const T&, const T&);
     // overloaded versions of func; each take a different function pointer type
     void func(int(*) (const string&, const string&));
     void func(int(*) (const int&, const int&));
     func(compare<int>); // ok: explicitly specify which version of compare

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.