C++ Programming Guide

Chapter 4

Templates

Templates make it possible for you to write a single body of code that applies to a wide range of types in a type-safe manner. This chapter introduces template concepts and terminology in the context of function templates, discusses the more complicated (and more powerful) class templates, and describes the composition of templates. Also discussed are template instantiation, default template parameters, and template specialization. The chapter concludes with a discussion of potential problem areas for templates.

4.1 Function Templates

A function template describes a set of related functions that differ only by the types of their arguments or return values.

4.1.1 Function Template Declaration

You must declare a template before you can use it. A declaration, as in the following example, provides enough information to use the template, but not enough information to implement the template.

template <class Number> Number twice( Number original );

In this example, Number is a template parameter; it specifies the range of functions that the template describes. More specifically, Number is a template type parameter, and its use within the template definition stands for a type determined at the location where the template is used.

4.1.2 Function Template Definition

If you declare a template, you must also define it. A definition provides enough information to implement the template. The following example defines the template declared in the previous example.

template <class Number> Number twice( Number original ) { return original + original; }

Because template definitions often appear in header files, a template definition might be repeated in several compilation units. All definitions, however, must be the same. This restriction is called the One-Definition Rule.

Sun WorkShop 6 C++ does not support expressions involving non-type template parameters in the function parameter list, as shown in the following example.

// Expressions with non-type template parameters // in the function parameter list are not supported template<int I> void foo( mytype<2*I> ) { ... } template<int I, int J> void foo( int a[I+J] ) { ... }

4.1.3 Function Template Use

Once declared, templates can be used like any other function. Their use consists of naming the template and providing function arguments. The compiler can infer the template type arguments from the function argument types. For example, you can use the previously declared template as follows.

double twicedouble( double item ) { return twice( item ); }

If a template argument cannot be inferred from the function argument types, it must be supplied where the function is called. For example:

template<class T> T func(); // no function arguments int k = func<int>(); // template argument supplied explicitly

4.2 Class Templates

A class template describes a set of related classes or data types that differ only by types, by integral values, by pointers or references to variables with global linkage, or by a combination thereof. Class templates are particularly useful in describing generic, but type-safe, data structures.

4.2.1 Class Template Declaration

A class template declaration provides only the name of the class and its template arguments. Such a declaration is an incomplete class template.

The following example is a template declaration for a class named Array that takes any type as an argument.

template <class Elem> class Array;

This template is for a class named String that takes an unsigned int as an argument.

template <unsigned Size> class String;

4.2.2 Class Template Definition

A class template definition must declare the class data and function members, as in the following examples.

template <class Elem> class Array { Elem* data; int size; public: Array( int sz ); int GetSize(); Elem& operator[]( int idx ); };

template <unsigned Size> class String { char data[Size]; static int overflows; public: String( char *initial ); int length(); };

Unlike function templates, class templates can have both type parameters (such as class Elem) and expression parameters (such as unsigned Size). An expression parameter can be:

• A value that has an integral type or enumeration
• A pointer or a reference to an object
• A pointer or a reference to a function
• A pointer to a class member function

4.2.3 Class Template Member Definitions

The full definition of a class template requires definitions for its function members and static data members. Dynamic (nonstatic) data members are sufficiently defined by the class template declaration.

4.2.3.1 Function Member Definitions

The definition of a template function member consists of the template parameter specification followed by a function definition. The function identifier is qualified by the class template's class name and the template arguments. The following example shows definitions of two function members of the Array class template, which has a template parameter specification of template <class Elem>. Each function identifier is qualified by the template class name and the template argument Array<Elem>.

template <class Elem> Array<Elem>::Array( int sz ) { size = sz; data = new Elem[ size ]; } template <class Elem> int Array<Elem>::GetSize( ) { return size; }

This example shows definitions of function members of the String class template.

#include <string.h> template <unsigned Size> int String<Size>::length( ) { int len = 0; while ( len < Size && data[len] != '\0' ) len++; return len; } template <unsigned Size> String<Size>::String( char *initial ) { strncpy( data, initial, Size ); if ( length( ) == Size ) overflows++; }

4.2.3.2 Static Data Member Definitions

The definition of a template static data member consists of the template parameter specification followed by a variable definition, where the variable identifier is qualified by the class template name and its template actual arguments.

template <unsigned Size> int String<Size>::overflows = 0;

4.2.4 Class Template Use

A template class can be used wherever a type can be used. Specifying a template class consists of providing the values for the template name and arguments. The declaration in the following example creates the variable int_array based upon the Array template. The variable's class declaration and its set of methods are just like those in the Array template except that Elem is replaced with int (see Section 4.3 "Template Instantiation"").

Array<int> int_array( 100 );

The declaration in this example creates the short_string variable using the String template.

String<8> short_string( "hello" );

You can use template class member functions as you would any other member function

int x = int_array.GetSize( );

int x = short_string.length( );

.

4.3 Template Instantiation

Template instantiation involves generating a concrete class or function (instance) for a particular combination of template arguments. For example, the compiler generates a class for Array<int> and a different class for Array<double>. The new classes are defined by substituting the template arguments for the template parameters in the definition of the template class. In the Array<int> example, shown in the preceding "Class Templates" section, the compiler substitutes int wherever Elem appears.

4.3.1 Implicit Template Instantiation

The use of a template function or template class introduces the need for an instance. If that instance does not already exist, the compiler implicitly instantiates the template for that combination of template arguments.

4.3.2 Whole-Class Instantiation

When the compiler implicitly instantiates a template class, it usually instantiates only the members that are used. To force the compiler to instantiate all member functions when implicitly instantiating a class, use the -template=wholeclass compiler option. To turn this option off, specify the -template=no%wholeclass option, which is the default.

4.3.3 Explicit Template Instantiation

The compiler implicitly instantiates templates only for those combinations of template arguments that are actually used. This approach may be inappropriate for the construction of libraries that provide templates. C++ provides a facility to explicitly instantiate templates, as seen in the following examples.

4.3.3.1 Explicit Instantiation of Template Functions

To instantiate a template function explicitly, follow the template keyword by a declaration (not definition) for the function, with the function identifier followed by the template arguments.

template float twice<float>( float original );

Template arguments may be omitted when the compiler can infer them.

template int twice( int original );

4.3.3.2 Explicit Instantiation of Template Classes

To instantiate a template class explicitly, follow the template keyword by a declaration (not definition) for the class, with the class identifier followed by the template arguments.

template class Array<char>;

template class String<19>;

When you explicitly instantiate a class, all of its members are also instantiated.

4.3.3.3 Explicit Instantiation of Template Class Function Members

To explicitly instantiate a template class function member, follow the template keyword by a declaration (not definition) for the function, with the function identifier qualified by the template class, followed by the template arguments

template int Array<char>::GetSize( );

template int String<19>::length( );

.

4.3.3.4 Explicit Instantiation of Template Class Static Data Members

To explicitly instantiate a template class static data member, follow the template keyword by a declaration (not definition) for the member, with the member identifier qualified by the template class, followed by the template argument

template int String<19>::overflow;

.

4.4 Template Composition

You can use templates in a nested manner. This is particularly useful when defining generic functions over generic data structures, as in the standard C++ library. For example, a template sort function may be declared over a template array class:

template <class Elem> void sort( Array<Elem> );

and defined as:

template <class Elem> void sort( Array<Elem> store ) { int num_elems = store.GetSize( ); for ( int i = 0; i < num_elems-1; i++ ) for ( int j = i+1; j < num_elems; j++ ) if ( store[j-1] > store[j] ) { Elem temp = store[j]; store[j] = store[j-1]; store[j-1] = temp; } }

The preceding example defines a sort function over the predeclared Array class template objects. The next example shows the actual use of the sort function.

Array<int> int_array( 100 ); // construct an array of ints sort( int_array ); // sort it

4.5 Default Template Parameters

You can give default values to template parameters for class templates (but not function templates).

template <class Elem = int> class Array; template <unsigned Size = 100> class String;

If a template parameter has a default value, all parameters after it must also have default values. A template parameter can have only one default value.

4.6 Template Specialization

There may be performance advantages to treating some combinations of template arguments as a special case, as in the following examples for twice. Alternatively, a template description might fail to work for a set of its possible arguments, as in the following examples for sort. Template specialization allows you to define alternative implementations for a given combination of actual template arguments. The template specialization overrides the default instantiation.

4.6.1 Template Specialization Declaration

You must declare a specialization before any use of that combination of template arguments. The following examples declare specialized implementations of twice and sort.

template <> unsigned twice<unsigned>( unsigned original );

template <> sort<char*>( Array<char*> store );

You can omit the template arguments if the compiler can unambiguously determine them. For example:

template <> unsigned twice( unsigned original );

template <> sort( Array<char*> store );

4.6.2 Template Specialization Definition

You must define all template specializations that you declare. The following examples define the functions declared in the preceding section.

template <> unsigned twice<unsigned>( unsigned original ) { return original << 1; }

#include <string.h> template <> void sort<char*>( Array<char*> store ) { int num_elems = store.GetSize( ); for ( int i = 0; i < num_elems-1; i++ ) for ( int j = i+1; j < num_elems; j++ ) if ( strcmp( store[j-1], store[j] ) > 0 ) { char *temp = store[j]; store[j] = store[j-1]; store[j-1] = temp; } }

4.6.3 Template Specialization Use and Instantiation

A specialization is used and instantiated just as any other template, except that the definition of a completely specialized template is also an instantiation.

4.6.4 Partial Specialization

In the previous examples, the templates are fully specialized. That is, they define an implementation for specific template arguments. A template can also be partially specialized, meaning that only some of the template parameters are specified, or that one or more parameters are limited to certain categories of type. The resulting partial specialization is itself still a template. For example, the following code sample shows a primary template and a full specializaton of that template.

template<class T, class U> class A { ... }; //primary template template<> class A<int, double> { ... };    //specialization

The following code shows examples of partial specialization of the primary template.

template<classU> class A<int> { ... };          // Example 1 template<class T, class U> class A<T*> { ... }; // Example 2 template<class T> class A<T**, char> { ... };   // Example 3

• Example 1 provides a special template definition for cases when the first template parameter is type int.
• Example 2 provides a special template definition for cases when the first template parameter is any pointer type.
• Example 3 provides a special template definition for cases when the first template parameter is pointer-to-pointer of any type, and the second template parameter is type char.

4.7 Template Problem Areas

This section describes problems you might encounter when using templates.

4.7.1 Nonlocal Name Resolution and Instantiation

Sometimes a template definition uses names that are not defined by the template arguments or within the template itself. If so, the compiler resolves the name from the scope enclosing the template, which could be the context at the point of definition, or at the point of instantiation. A name can have different meanings in different places, yielding different resolutions.

Name resolution is complex. Consequently, you should not rely on nonlocal names, except those provided in a pervasive global environment. That is, use only nonlocal names that are declared and defined the same way everywhere. In the following example, the template function converter uses the nonlocal names intermediary and temporary. These names have different definitions in use1.cc and use2.cc, and will probably yield different results under different compilers. For templates to work reliably, all nonlocal names (intermediary and temporary in this case) must have the same definition everywhere.

use_common.h	// Common template definition template <class Source, class Target> Target converter( Source source ) { temporary = (intermediary)source; return (Target)temporary; }
use1.cc	typedef int intermediary; int temporary; #include "use_common.h"
use2.cc	typedef double intermediary; unsigned int temporary; #include "use_common.h"

A common use of nonlocal names is the use of the cin and cout streams within a template. Few programmers really want to pass the stream as a template parameter, so they refer to a global variable. However, cin and cout must have the same definition everywhere.

4.7.2 Local Types as Template Arguments

The template instantiation system relies on type-name equivalence to determine which templates need to be instantiated or reinstantiated. Thus local types can cause serious problems when used as template arguments. Beware of creating similar problems in your code. For example:

CODE EXAMPLE 4-1   Example of Local Type as Template Argument Problem

array.h	template <class Type> class Array { Type* data; int size; public: Array( int sz ); int GetSize( ); };
array.cc	template <class Type> Array<Type>::Array( int sz ) { size = sz; data = new Type[size]; } template <class Type> int Array<Type>::GetSize( ) { return size;}
file1.cc	#include "array.h" struct Foo { int data; }; Array<Foo> File1Data;
file2.cc	#include "array.h" struct Foo { double data; }; Array<Foo> File2Data;

The Foo type as registered in file1.cc is not the same as the Foo type registered in file2.cc. Using local types in this way could lead to errors and unexpected results.

4.7.3 Friend Declarations of Template Functions

Templates must be declared before they are used. A friend declaration constitutes a use of the template, not a declaration of the template. A true template declaration must precede the friend declaration. For example, when the compilation system attempts to link the produced object file for the following example, it generates an undefined error for the operator<< function, which is not instantiated.

CODE EXAMPLE 4-2   Example of Friend Declaration Problem

array.h	// generates undefined error for the operator<< function #ifndef ARRAY_H #define ARRAY_H #include <iosfwd> template<class T> class array { int size; public: array(); friend std::ostream& operator<<(std::ostream&, const array<T>&); }; #endif
array.cc	#include <stdlib.h> #include <iostream> template<class T> array<T>::array() { size = 1024; } template<class T> std::ostream& operator<<(std::ostream& out, const array<T>& rhs) { return out << '[' << rhs.size << ']'; }
main.cc	#include <iostream> #include "array.h" int main() { std::cout << "creating an array of int... " << std::flush; array<int> foo; std::cout << "done\n"; std::cout << foo << std::endl; return 0; }

Note that there is no error message during compilation because the compiler reads the following as the declaration of a normal function that is a friend of the array class.

friend ostream& operator<<(ostream&, const array<T>&);

Because operator<< is really a template function, you need to supply a template declaration for prior to the declaration of template class array. However, because operator<< has a parameter of type array<T>, you must precede the function declaration with a declaration of array<T>. The file array.h must look like this:

#ifndef ARRAY_H #define ARRAY_H #include <iosfwd> // the next two lines declare operator<< as a template function template<class T> class array; template<class T> std::ostream& operator<<(std::ostream&, const array<T>&); template<class T> class array { int size; public: array(); friend std::ostream& operator<<(std::ostream&, const array<T>&); }; #endif

4.7.4 Using Qualified Names Within Template Definitions

The C++ standard requires types with qualified names that depend upon template arguments to be explicitly noted as type names with the typename keyword. This is true even if the compiler can "know" that it should be a type. The comments in the following example show the types with qualified names that require the typename keyword.

struct simple { typedef int a_type; static int a_datum; }; int simple::a_datum = 0; // not a type template <class T> struct parametric { typedef T a_type; static T a_datum; }; template <class T> T parametric<T>::a_datum = 0;   // not a type template <class T> struct example { static typename T::a_type variable1;      // dependent static typename parametric<T>::a_type variable2; // dependent static simple::a_type variable3; // not dependent }; template <class T> typename T::a_type     // dependent example<T>::variable1 = 0;     // not a type template <class T> typename parametric<T>::a_type // dependent example<T>::variable2 = 0;     // not a type template <class T> simple::a_type   // not dependent example<T>::variable3 = 0;          // not a type

4.7.5 Nesting Template Declarations

Because the ">>" character sequence is interpreted as the right-shift operator, you must be careful when you use one template declaration inside another. Make sure you separate adjacent ">" characters with at least one blank space.

For example, the following ill-formed statement:

// ill-formed statement Array<String<10>> short_string_array(100); // >> = right-shift

is interpreted as:

Array<String<10 >> short_string_array(100);

The correct syntax is:

Array<String<10> > short_string_array(100);