Chapter 3
Templates
An important goal of object-oriented program is to support code reuse. This chapter introduces one mechanism that is used to further this goal, the C++ template. The template allows us to write routines that work for arbitrary types, without knowing, as we write the routines, what these types will be. Although this is supported somewhat by the use of the typedef facility, the template is more powerful than the typedef.
In this chapter, we will see:
•	What a template is and how it differs from the typedef
•	How to write some useful function templates
•	How to write class templates
•	The limitations of templates
3.1	What Is a Template?
Consider the problem of finding the largest item in an array of items. A simple algorithm is the sequential scan, in which we examine each item in order, keeping track of the maximum. As is typical of many algorithms, the sequential scan algorithm is type-independent. By type-independent, we mean that the logic of this algorithm does not depend on the type of items that are stored in the array. The same logic works for an array of integers, floating-point numbers, or any type for which comparison can be meaningfully defined.
Throughout this text, we will describe algorithms and data structures that are type independent. Swapping, sorting, and searching are classic exmaples of type-independent algorithms. When we write C++ code for a type-independent algorithm or data structure, we would prefer to write the code once, rather than recode it for each different type.
In this chapter we will describe how type-independent algorithms (also known as generic algorithms) are written in C++. This is done by using a template. We begin by discussing function templates. Then we examine class templates.
3.2	Function Templates
The typedef is a simple mechanism to allow generic routines. However it is unsuitable if we want routines with two different types.
Suppose we want to write a swap routine in Figure 1.13 for doubles instead of ints. The logic is identical; we just need to change the type declarations. One way to do this is to write the swap routine for an arbitrary Object and then issue the appropriate typedef. The typedef is a simple mechanism to allow generic routines. This is shown in Figure 3.1.
Suppose, however, that we want to use swap for both int and double. Certainly this would be acceptable because the two swap routines would have different signatures. The typedef would not work because Object cannot assume both int and double simultaneously. C++ provides templates that make it possible to write a routine that can be used for both types.
A function template is a design for a function.
A function template is not an actual function but instead is a pattern for what could become an actual function. For example, a template for a swap routine is shown in Figure 3.2. This design is expanded (much like a preprocessor macro) as needed to provide an actual routine. If a call to swap with two int parameters is made, the compiler will generate a routine from the template shown in Figure 3.2, using lines 4 through 9, with int replacing Object.
When the template is instantiated with a particular type, a new function is logically created.
This expansion instantiates the function template. The compiler must now check that the instantiation is legal C++. Some of the checking may have been performed when the template was defined. For example, missing semicolons and unbalanced parentheses are easy to check. Some checks cannot be performed that early. For instance, operator= might be disallowed for the instantiated type, and that check could only be performed at the point of instantiation. In that case the swap operation could not work. If the instantiated type does not have a copy constructor but does have operator=, we could rewrite the swap template in Figure 3.2 to avoid the copy constructor. Thus there is occasionally a trade-off between requiring more operations to be supported by the template parameter and code compactness (and/or efficiency).
Only one instantiation is created for each parameter type combination.
Figure 3.3 shows the swap template in use. Each call to swap with previously unseen parameter types generates new instantiations. Thus if there are two calls to swap(int,int) and one call to swap(double,double), then there are two instantiations of the swap template: one with Object of int and another with Object of double.
	1	typedef double Object;
	2	
	3	// Standard swap routine
	4	void swap( Object & lhs, Object & rhs )
	5	{
	6	    Object tmp = lhs;
	7	    lhs = rhs;
	8	    rhs = tmp;
	9	}
Figure 3.1	swap routine using typedefs
	1	// swap function template
	2	// Object: must have copy constructor and operator=
	3	template <class Object>
	4	void swap( Object & lhs, Object & rhs )
	5	{
	6	    Object tmp = lhs;
	7	    lhs = rhs;
	8	    rhs = tmp;
	9	}
Figure 3.2	swap function template
	1	// Exercise the swap function template
	2	int main( )
	3	{
	4	    int x = 5;
	5	    int y = 7;
	6	    double a = 2;
	7	    double b = 4;
	8	
	9	    swap( x, y );   // Instantiates swap with int
	10	    swap( x, y );   // Uses already instantiated swap with int
	11	    swap( a, b );   // Instantiates swap with double
	12	    cout << x << ' ' << y << endl;
	13	    cout << a << ' ' << b << endl;
	14	//  swap( x, b );   // Illegal: no match
	15	
	16	    return 0;
	17	}
Figure 3.3	Using the swap function template.
3.3	A Sorting Function Template
Swapping is a classic example of a routine that is type independent and thus well suited for a template implementation. In this section we will write another template function that sorts and show how a main routine uses it.
Our simple program will read a sequence of integers (until the end of input or bad input is detected), and will sort and output them. If we change our minds and decide that we want a sequence of floating-point numbers or string objects, then we expect only a one-word change (in one location) to the entire program. Sorting will be accomplished by a simple sort template function.
Insertion sort is a simple sorting algorithm that is appropriate for small inputs.
Sorting is implemented by an algorithm known as insertion sort. Insertion sort is generally considered a good solution if only a few elements need sorting because it is such a short algorithm and the time required to sort is not likely to be an issue. If we are dealing with a large amount of data, however, then insertion sort is a poor choice because it is too time consuming. In that case better algorithms should be used, as discussed in Chapter 9. The insertion sort algorithm is coded in Figure 3.4. We will use this routine in Section 4.3.
Insertion sort works as follows. The initial state is that the first element, considered by itself, is sorted. The final state that we need to attain is that all elements (assume that there are N), considered as a group, are sorted. Figure 3.5 shows that the basic action of insertion sort is to arrange that elements in positions 0 through p (where p ranges from 1 to ) are sorted. In each stage p increases by 1. That is what the outer loop at line 7 in Figure 3.4 is controlling.
	1	// InsertionSort: sort items in array a
	2	// Comparable: must have copy constructor, operator=,
	3	//   and operator<
	4	template <class Comparable>
	5	void insertionSort( vector<Comparable> & a )
	6	{
	7	    for( int p = 1; p < a.size( ); p++ )
	8	    {
	9	        Comparable tmp = a[ p ];
	10	        int j;
	11	
	12	        for( j = p; j > 0 && tmp < a[ j - 1 ]; j-- )
	13	            a[ j ] = a[ j - 1 ];
	14	        a[ j ] = tmp;
	15	    }
	16	}
Figure 3.4	Templated insertion sort

Array position
0
1
2
3
4
5
Initial State:
8
5
9
2
6
3
After a[0..1] is sorted:
5
8
9
2
6
3
After a[0..2] is sorted:
5
8
9
2
6
3
After a[0..3] is sorted:
2
5
8
9
6
3
After a[0..4] is sorted:
2
5
6
8
9
3
After a[0..5] is sorted:
2
3
5
6
8
9
Figure 3.5	Basic action of insertion sort (shaded part is sorted)

Array position
0
1
2
3
4
5
Initial State:
8
5
After a[0..1] is sorted:
5
8
9
After a[0..2] is sorted:
5
8
9
2
After a[0..3] is sorted:
2
5
8
9
6
After a[0..4] is sorted:
2
5
6
8
9
3
After a[0..5] is sorted:
2
3
5
6
8
9
Figure 3.6	Closer look at action of insertion sort (dark shading indicates sorted area; light shading is where new element was placed)
When the body of the for loop is entered at line 9, we are guaranteed that the elements in array positions 0 through p-1 are already sorted, and we need to extend this to positions 0 to p. Figure 3.6 gives a closer look at what has to be done, detailing only the relevant part of the array. At each step the element in boldface type needs to be added to the previously sorted part of the array. This is easily done by placing it in a temporary variable and sliding all of the elements that are larger than it over one position to the right. After that is done we can copy the temporary variable into the former position of the leftmost relocated element (indicated by lighter shading on the following line). We keep a counter j, which is the position where the temporary variable should be written back to. j decreases by 1 every time an element is slid over. Lines 9 to 14 implement this.
Always check the boundary cases.
It is important to check that this insertion sort works in two boundary cases. First, in Figure 3.6, if the boldface element already is the largest in the group, then it is copied out to the temporary variable and then back immediately, and thus is correct. If the boldface element is the smallest in the group, then the entire group moves over, and the temporary is copied into array position zero. We just need to be careful that we do not run past the end of the array. Thus we can be sure that when the outer for loop terminates, the array is sorted.
Now that we have the support functions done, we can write main. This is shown in Figure 3.7.
The instantiated type does not always make sense. In that case an error may be noticed at the instantiation point, or in some cases the code is legal but erroneous.
We can use templates to have sorting at our fingertips for any type. However, it does not always make sense. Let us look at a couple of different types:
	1.	double: No problem; a one-line change in main and everything works well.
	2.	Rational: No problem; a one-line change in main and everything works well.
	3.	char * (primitive strings): Serious problem; the operator= and operator< do not make sense, so the program will not work. Specifically, we cannot just read into a char * object without first setting aside memory. Assuming we have done that, then the sort will not work because operator< for two char * objects compares their memory locations.
	4.	string: A possitible efficiency problem; the algorithm will work, but the cost could be overly expensive because of repeated calls to operator=. The result will be that we could do excessive string copies, which are very expensive. A solution to this problem is discussed in Chapter 9 (it involves moving pointers rather than the actual string objects). Note that many string implementations optimize string copies by using an extra level of pointers, in which case there is no efficiency problem.
	5.	A type for which operator<, or some needed operator is not defined: This will generate an error at link time. At that point, the linker will notice that operator< is not implemented. Note that this occurs even if operator> is implemented.
	6.	A type for which operator= is disallowed via placement in the private section: This will generate an error at compile time when the template is instantiated.
As a result, it is good practice to place in a comment a listing of the conditions that must be satisfied by the template parameter. Throughout this text, we will use Object and Comparable as template types. For Object, we assume that zero-parameter constructors, and both a copy constructor and copy assignment operator are available. For the Comparable, we require that in addition to the properties that are satisfied by Object, operator< also be available. If additional operations are needed, then we will specify them in a comment. Otherwise, we will on occasion omit the long comments to save space, if they are merely restating the assumptions we establish here.
3.4	Class Templates
Classes can be templated. The syntax is onerous.
In this section we show how we can create and use class templates. Since -vector is actually a class template, we have already been using class templates. At the end of this chapter, we will provide an implementation of vector. But first, we will use a simpler example to illustrate the syntax and show how to template the IntCell class from Section 2.2.
3.4.1	A MemoryCell Template
Figure 3.8 shows a template version of the IntCell class previously depicted in Figure 2.1. We will use the more generic name, MemoryCell. This version does not separate the interface and implementation. We will revise the code shortly to do so, because as we discussed in Section 2.3, the separation is usually preferable. We begin without a separation in order to illustrate the most basic syntax.
	1	#include <iostream>
	2	#include <vector>
	3	using namespace std;
	4	
	5	// Read an arbitrary number of items, sort and print them.
	6	int main( )
	7	{
	8	    vector<int> array;       // The array
	9	    int x;                   // An item to read
	10	
	11	    cout << "Enter items to sort: " << endl;
	12	    while( cin >> x )
	13	        array.push_back( x );
	14	
	15	    insertionSort( array );
	16	
	17	    cout << "Sorted items are: " << endl;
	18	    for( int i = 0; i < array.size( ); i++ )
	19	        cout << array[ i ] << '\n';
	20	
	21	    return 0;
	22	}
Figure 3.7	main routine to read some integers, sort them, and output them
	1	// MemoryCell template class interface:
	2	//   simulate one Object RAM
	3	//
	4	// Object: must have zero-parameter constructor and operator=
	5	// CONSTRUCTION: with (a) no initializer, or
	6	//                    (b) an Object, or
	7	//                    (c) another MemoryCell
	8	// ******************PUBLIC OPERATIONS**********************
	9	// Object read( )          --> Return stored value
	10	// void write( Object x )  --> Place x as stored value
	11	
	12	template <class Object>
	13	class MemoryCell
	14	{
	15	  public:
	16	    explicit MemoryCell( const Object & initVal = Object( ) )
	17	      : storedValue( Object ) { }
	18	
	19	      // Public member functions
	20	    const Object & read( ) const
	21	      { return StoredValue; }
	22	    void write( const Object & x )
	23	      { storedValue = x; }
	24	
	25	  private:
	26	    Object storedValue;
	27	};
Figure 3.8	Complete declaration of a MemoryCell class
	1	// Exercise the MemoryCell class
	2	int main( )
	3	{
	4	    MemoryCell<int> n;
	5	
	6	    m.write( 5 );
	7	    cout << "Cell contents are " << m.read( ) << endl;
	8	
	9	    return 0;
	10	}
Figure 3.9	A simple test routine to show how MemoryCell objects are accessed.
	1	// Memory cell interface; same as in Figure 3.8
	2	
	3	template <class Object>
	4	class MemoryCell
	5	{
	6	  public:
	7	    explicit MemoryCell( const Object & initVal = Object( ) );
	8	    const Object & Read( ) const;
	9	    void Write( const Object & X );
	10	
	11	  private:
	12	    Object StoredValue;
	13	};
Figure 3.10	MemoryCell class template interface
A template class must have the -template specification prior to the interface. Objects of a template class type must be instantiated with the template parameters.
The class template syntax is similar to the function template syntax; we merely add a template specification (shown on line 12 or Figure 3.8). Notice that write accepts a parameter passed by constant reference, and read returns its parameter by constant reference. When possible, constant references should be used instead of call/return by value because, if Object is a large object, making a copy could be inefficient (or illegal if the copy constructor for Object is either disabled or not defined). Do not use constant reference returns blindly, however. Remember that you cannot return a reference to an automatic variable. Figure 3.9 shows a simple main that uses the template class. 
We need to take note of two features of this routine. First, in the commented description of the interface, we do not specify whether a function is a constant member or how parameters are passed. This would merely duplicate information that is clearly specified in the interface code. Second, Object must have a zero-parameter constructor because the default constructor is used for MemoryCell, and it is a member-by-member call of the zero-parameter constructors.
If we implement class templates as a single unit, then there is very little syntax baggage. Many class templates are, in fact, implemented this way because currently, separate compilation of templates does not work well on many platforms. Therefore, in many cases, the entire class, with its implementation must be placed in a .h file. Popular implementations of the STL follow this strategy.
However, eventually, separate compilation will work, and it will be better to separate the class templates interface and implementation in the same way that is done for classes in Chapter 2. Unfortunately, this does add some syntax baggage.
	1	// Implementation of the class members
	2	
	3	#include "MemoryCell.h"
	4	
	5	template <class Object>
	6	MemoryCell<Object>::MemoryCell( const Object & initVal )
	7	  : storedValue( initVal )
	8	{
	9	}
	10	
	11	template <class Object>
	12	const Object & MemoryCell<Object>::read( ) const
	13	{
	14	    return storedValue;
	15	}
	16	
	17	template <class Object>
	18	void MemoryCell<Object>::write( const Object & x )
	19	{
	20	    storedValue = x;
	21	}
Figure 3.11	MemoryCell class template implementation
	1	// Typical template interface
	2	template <class Object>
	3	class ClassName
	4	{  
	5	  public:
	6	    // Public members
	7	  private:
	8	    // Private members
	9	};  
	10	
	11	
	12	// Typical member implementation
	13	template <class Object>
	14	ReturnType
	15	ClassName<Object>::MemberName( Parameter List ) /* const */
	16	{ 
	17	    // Member body
	18	} 
Figure 3.12	Typical layout for template interface and member functions
	1	template <class Object>
	2	const MemoryCell<Object> &
	3	MemoryCell<Object>::operator=( const MemoryCell<Object> & rhs )
	4	{
	5	    if( this != &rhs )
	6	        storedValue = rhs.storedValue;
	7	    return *this;
	8	}
Figure 3.13	Illustration of template syntax for operator=
Each member function must be declared as a template.
Figure 3.10 shows the interface for the template class. That part is, of course, simple enough, since it is identical to the entire class that we have already seen in Figure 3.9 with inline implementations removed. For the implementation, we have a collection of function templates. This means that each function must include the template line, and when using the scope operator, the name of the class must be instantiated with the template argument. Thus in Figure 3.11, the name of the class is MemoryCell<Object>.
 Figure 3.12 gives a layout of the general format that is used. Boldface items are typed exactly as shown. Although the syntax seem innocuous enough, it can get fairly substantial. For instance, to define operator= in the interface requires no extra baggage. In the implementation, we would have the horrendous-looking code in Figure 3.13.
Typically, the declaration part of the more complex functions will no longer fit on one line, and will need splitting as done above.
Even if the interface and implementation of the class template are separated, few compilers will automatically handle separate compilation correctly. The simplest, most portable solution, is to add an #include directive at the end of the interface file, to import the implementation. This is done in the online code (for class templates only). Alternative solutions involve adding explicit instantiations for each type as a separate .cpp file in the project. Since these details will change rapidly, it's best to consult local documentation to find the proper alternative.
3.4.2	Implementing the vector Class Template
We can use templates to design a safe, dynamically expanding array.
Our final example is a complete class that supports arrays in the manner of most programming languages: It provides index range checking and allows copying between identically sized (and typed) arrays. We also support dynamically changing array sizes. Given the fact that the string class in Section 2.6 supported very similar operations, the only new item is the use of templates in this class.
	1	// vector class interface. Supports construction with
	2	// initial size (default is 0), automatic destruction,
	3	// access of the current size, array indexing via [], deep
	4	// copy, and resizing. Index range checking is performed
	5	// unless NO_CHECK is defined.
	6	
	7	template <class Object>
	8	class vector
	9	{
	10	  public:
	11	    explicit vector( int initSize = 0 )
	12	      : theSize( initSize ), theCapacity( initSize )
	13	      { objects = new Object[ theCapacity ]; }
	14	    vector( const vector & rhs ) : objects( NULL )
	15	      { operator=( rhs ); }
	16	    ~vector( )
	17	      { delete [ ] objects; }
	18	
	19	    Object & operator[]( int index )
	20	    {
	21	                                              #ifndef NO_CHECK
	22	        if( index < 0 || index >= size( ) )
	23	            throw ArrayIndexOutOfBoundsException( );
	24	                                              #endif
	25	        return objects[ index ];
	26	    }
	27	
	28	    const Object & operator[]( int index ) const
	29	    {
	30	                                              #ifndef NO_CHECK
	31	        if( index < 0 || index >= size( ) )
	32	            throw ArrayIndexOutOfBoundsException( );
	33	                                              #endif
	34	        return objects[ index ];
	35	    }
	36	
	37	    const vector & operator= ( const vector & rhs );
	38	    void resize( int newSize );
	39	    void reserve( int newCapacity );
	40	    void push_back( const Object & x );
	41	    int size( ) const
	42	      { return theSize; }
	43	    int capacity( ) const
	44	      { return theCapacity; }
	45	
	46	  private:
	47	    int theSize;
	48	    int theCapacity;
	49	    Object * objects;
	50	};
Figure 3.14	vector.h 
	1	#include "vector.h"
	2	
	3	template <class Object>
	4	const vector<Object> &
	5	vector<Object>::operator=( const vector<Object> & rhs )
	6	{
	7	    if( this != &rhs )                        // Alias test
	8	    {
	9	        delete [ ] objects;                   // Reclaim old
	10	        theSize = rhs.size( );                // Copy size 
	11	        theCapacity = rhs.capacity( );        //  and capacity
	12	        objects = new Object[ capacity( ) ];  // Allocate
	13	        for( int k = 0; k < size( ); k++ )    // Copy items
	14	            objects[ k ] = rhs.objects[ k ];
	15	    }
	16	    return *this;                  // Return reference to self
	17	}
	18	
	19	template <class Object>
	20	void vector<Object>::push_back( const Object & x )
	21	{
	22	    if( theSize == theCapacity )              // If no room
	23	        reserve( 2 * theCapacity + 1 );       //   Make room
	24	    objects[ theSize++ ] = x;                 // Add x
	25	}
	26	
	27	template <class Object>
	28	void vector<Object>::resize( int newSize )
	29	{
	30	    if( newSize > theCapacity )               // If expanding
	31	        reserve( newSize );                   //   Get space
	32	    theSize = newSize;                        // Set size
	33	}
	34	
	35	template <class Object>
	36	void vector<Object>::reserve( int newCapacity )
	37	{
	38	    Object *oldArray = objects;               // Save old
	39	    int numToCopy = newCapacity < theSize ?   // Compute # to
	40	                    newCapacity : theSize;    //   copy
	41	
	42	    objects = new Object[ newSize ];          // Allocate new
	43	    currentSize = newSize;                    // Set new size
	44	    for( int k = 0; k < numToCopy; k++ )      // Copy items
	45	        objects[ k ] = oldArray[ k ];
	46	
	47	    if( newCapacity < theSize )               // If cap < size
	48	        theSize = newCapacity;                //   new size
	49	    theCapacity = newCapacity;                // set capacity
	50	    delete [ ] oldArray;                      // Reclaim old
	51	}
Figure 3.15	vector.cpp 
Our vector class supports array indexing, resizing, and copying, and performs index-range checking (the STL version does not). Because crucial functions are inlined, you can expect this version to be as efficient as the STL version, except for the overhead of index-range checking. The class uses the symbol NO_CHECK, which if defined, causes the range checking code to not be compiled. All compilers provide options to define symbols as part of the compilation command; check your compiler's documentation for details. All code in the text makes use of this vector class, however the STL version can be used instead; all member functions in this vector class are present in the STL version.
The vector class is implementing by storing a base-primitive array (objects) as a data member. Recall once again that a primitive array is a "second-class" object, implemented as a pointer to a block of memory large enough to store the array objects. Because the primitive array is represented as a pointer, the size of the array is unknown and needs to be maintained in a separate variable (currentSize). Memory for the array is obtained by calling the new[] operator. This occurs in the constructor, in the assignment operator, and also in the reserve operation. The memory needs to be reclaimed by delete[]. This occurs in the destructor, and also in the assignment and reserve operations (because for assignment, the old array is reclaimed prior to allocation of the new array, while in resizing, the old array is reclaimed after the allocation of the new array).
The class interface, shown in Figure 3.14, includes implementations of the functions that are one-liners, so as to avoid the overhead of function calls. The compiler can aggressively inline these functions. Normally this is not worthwhile, but fast vector operations are certain to be crucial in any application. The remaining member functions are shown in Figure 3.15.
3.5	Templates of Templates: A matrix Class
As mentioned in Section 1.2.7, the C++ library does not provide any support for first-class multidimensional arrays. However, a reasonable class to support two-dimensional arrays can be written quickly. We call this class a matrix. The basic idea is to use a vector of vectors. The matrix class is in Figure 3.16.
	1	template <class Object>
	2	class matrix
	3	{
	4	  public:
	5	    matrix( int rows, int cols ) : array( rows )
	6	    {
	7	        for( int i = 0; i < rows; i++ )
	8	            array[ i ].resize( cols );
	9	    }
	10	
	11	      // Copy constructor -- not really needed.
	12	    matrix( const matrix & rhs ) : array( rhs.array ) { }
	13	
	14	    const vector<Object> & operator[]( int row ) const
	15	      { return array[ row ]; }
	16	    vector<Object> & operator[]( int row )
	17	      { return array[ row ]; }
	18	
	19	    int numrows( ) const
	20	      { return array.size( ); }
	21	    int numcols( ) const
	22	      { return numrows( ) ? array[ 0 ].size( ) : 0; }
	23	
	24	    void push_back( const vector<Object> & newRow )
	25	      { array.push_back( newRow ); }
	26	
	27	  private:
	28	    vector< vector<Object> > array;
	29	};
Figure 3.16	A complete matrix class
3.5.1	The Data Members, Constructor, and Basic Accessors
Make sure you have space between > and > when instantiating layers of templates.
The matrix is represented by an array data member that is declared to be a vector of vector<Object>. Note carefully that in the declaration of array, white space must separate the two > characters; otherwise, the compiler will interpret the >> token as a shift operation. In other words, we must write:
    vector<vector<Object> > array;   // white space needed
The constructor first constructs array, as having rows entries each of type vector<Object> that is constructed with the zero-parameter constructor. Thus we have rows zero-length vectors of Object.
The body of the constructor is then entered and each row is resized to have cols columns. Thus the constructor terminates with what appears to be a two-dimensional array. The numrows and numcols accessors are then easily implemented as shown. We also provide a push_back method that adds a new row; this is trivially implemented by a call to the underlying vector's push_back .
3.5.2	operator[] 
The idea of operator[] is that if we have a matrix m, then m[i] should return a vector corresponding to row i of matrix m. If this is done, then m[i][j] will give the entry in position j for vector m[i], using the normal vector indexing operator. Thus the matrix operator[] is to return not an Object, but instead a vector<Object>.
We use the now-standard trick of writing both an accessor and mutator version of -operator[], that in their return types. The accessor version of -operator[] returns a constant reference, and the mutator version returns the simple reference.
3.5.3	Destructor, copy assignment, copy constructor
These are all taken care of automatically because the vector has taken care of it. Thus this is all the code needed for a fully functioning matrix class. Some compilers that have template bugs may require a trivial implementation of the copy constructor. For that reason only, a copy constructor is provided.
3.6	Fancy Templates
Our discussion of templates has only scratched the surface. C++ has recently expanded the template facility. Many of these new additions are used to implement the STL. Unfortunately, many of these additions also do not work everywhere. We discuss three advanced features; only the first works on most platforms.
3.6.1	Multiple Template Parameters
The proposed template facility allows multiple instantiation parameters, such as
template <class ItemType, class ValueType>
class Map
{
    ...
};
Here the Map template requires two types for instantiation. For instance, to declare a Map that takes a city name (which is a string) as the item to search for and returns a zip code (which is an int) as the lookup value, we can declare:
Map<string,int> zipCodes;
In fact, the map (lower-case m) is part of the STL, and we will provide an implementation in Part IV.
3.6.2	Default Template Parameters
Just as functions can have default parameters, templates can have default template types. Here is an example:
template <class ItemType, class ValueType=string>
class Map
{
    ...
};
We can now make the following declarations:
Map<int,int> m1;   // ItemType==int, ValueType==int
Map<int> m2;       // ItemType==int, ValueType==string
Default template parameters are widely used in the STL. Unfortunately, not all compilers support them.
3.6.3	The Reserved Word typename
A recent addition to the STL allows the use of the new reserved word t-ypename instead of class in the template parameter list. In other words, we can write:
template <typename Object>
class MemoryCell
{
    ...
};
Everything else is the same. The logic is that class is misleading because the template can be expanded with both class types and primitive types. However, not all compilers support typename, and the language designer suggests sticking with class. Who are we to argue?
3.7	Bugs Associated with Templates
We close our discussion of templates with some warnings. Templates are a relatively recent addition to the language, and not all of the details have been completely worked out. Many compilers have bugs or unimplemented features that are a direct consequence of templates. We will describe some of the bugs that were noticed in the preparation of this text (note that some, or possibly none, might apply in your case).
Bad Error Messages and Inconsistent Rules
The rules on when templates need instantiation seem to change frequently, and the compiler writers are having a hard time keeping up. You may find that your compiler is accepting old syntax, and when you port to another system it will complain that you have forgotten an explicit instantiation or, in some cases, provided an instantiation that you should not have. Some compilers do not accept current syntax, such as the explicit instantiation of a template function call.
Template-Matching Algorithms
Sometimes, the matching algorithm breaks when templates are involved. The most common example of this is function templates.
Nested Classes in a Template
Not all compilers support the nesting of classes in class templates. If yours does not, you will have to unnest the classes and make the original outer class a friend of the original inner class. Because some compilers do not support nested classes in templates, we do not use them in our code.
Static Members in Class Templates
Many compilers do not correctly handle static methods and data members in class templates. As a result, we make no use of them in our code.
Summary
This chapter has provided a brief discussion of the C++ template facilities. Templates allow us to write general classes and functions, thus helping us achieve the goal of code reuse. We will see templates used throughout the text.
In Chapter 4 we will look at another important mechanism for code reuse: inheritance.
Objects of the Game
insertion sort A simple sorting algorithm that is appropriate for small inputs. (143)
instantiation When a template is instantiated with a particular type or types, a new function or class is logically created. (141)
template A template is a design for code and allows us to write routines that work for arbitrary types without knowing what these types will be. (141)
typedef A simple mechanism to allow generic routines. However it is unsuitable if we want routines with two different types simultaneously. (140)
Common Errors
	1.	The template line must precede the template class interface and each member function definition.
	2.	A common error is forgetting an instantiation of a template. This occurs frequently in member function definitions. The definition shown in Figure 3.12 is typical of the instantiations that are required.
	3.	When instantiating a class template with an object that is itself a template class, white space must be used to separate successive >s. Otherwise, >> is interpreted as a shift operator.
	4.	When writing class templates, we must be especially careful about parameter passing mechanisms. Avoid passing unknown types by copying. Use either reference or constant reference types. Always assume that you are working with a large object.
	5.	Sometimes when a template is instantiated, an ambiguity develops. For instance, if we have two constructors: T(int) and T(Object), for template class T and Object is an int, we have an ambiguity. When designing classes, be sure that no ambiguities can develop.
	6.	When a class template is instantiated, all operations that are needed must be available. For instance, the insertion sort template needs to have operator< defined for whatever Comparable is instantiated. Otherwise, an error will be detected at link time. Clearly state what conditions must be satisfied by the template parameters.
	7.	If a class template uses call by value and the instantiated type has a disabled copy constructor, a compile-time error will be detected.
	8.	All of the errors that occur for classes occur for class templates.
	9.	Be aware of the limitations of your compiler. Many compilers still have buggy template implementations.
	10.	Generally, function templates do not separately compile.
On the Internet
The available files are:
InsSort.cpp	Contains insertionSort, and main shown in Figure 3.4 to Figure 3.7.
vector.h	Contains vector class interface shown in Figure 3.14. (The actual class is slightly more complex, as shown in Chapter 7)
vector.cpp	Contains vector class implementation.
matrix.h	Contains the matrix class shown in Figure 3.16.
Exercises
In Short
3.1.	Write a function template to sort three Comparable objects.
3.2.	When templates are used, what types of errors are detected when the function template is scanned, and what errors are detected when the function is instantiated?
3.3.	Describe the syntax for class templates.
In Practice
3.4.	Write function templates min and max, each of which accepts two parameters.
3.5.	Write function templates min and max, each of which accepts a -vector.
3.6.	In many situations operator< is defined for an object, but we also need operator>. Assume operator== is unavailable. Explore the possibility of writing an operator> template that calls operator<.
3.7.	A SingleBuffer class supports get and put: The -SingleBuffer stores a single item and a data member that indicates whether or not the SingleBuffer is logically empty. A put may be applied only to an empty buffer and inserts an item to the buffer. A get may only be applied to a nonempty buffer and deletes and returns the contents of the buffer. Write a class template to implement -SingleBuffer. Throw an exception to signal an error. What is the return type of get, and why?
Programming Projects
3.8.	Implement an insertion sort that takes a primitive array and its size as a single parameter.
3.9.	Implement a routine that reads an arbitrary number of Objects and stores them in a vector.
3.10.	Add a resize member function to the matrix class.
3.11.	Write a class template for the Rational class in Chapter 2.
3.12.	Modify the vector class as follows:
a.	Add a function that returns a reference to the internal array.
b.	Add a constructor that takes a primitive array and a size.
c.	Allow the vector to be constructed with a lower and upper bound that represent the valid index range. The size of the array is upper-lower+1.
d.	Add a function, fill, that fills all entries with a given value.