Class Templates
It is possible to understand the concept of a "stack" (a data structure into which we insert items at the top and retrieve those items in last-in, first-out order) independent of the type of the items being placed in the stack. However, to instantiate a stack, a data type must be specified. This creates a wonderful opportunity for software reusability. We need the means for describing the notion of a stack generically and instantiating classes that are type-specific versions of this generic stack class. C++ provides this capability through class templates.
Software Engineering Observation 14.2
|
Class templates encourage software reusability by enabling type-specific versions of generic classes to be instantiated. |
Class templates are called parameterized types, because they require one or more type parameters to specify how to customize a "generic class" template to form a class-template specialization.
The programmer who wishes to produce a variety of class-template specializations writes only one class-template definition. Each time an additional class-template specialization is needed, the programmer uses a concise, simple notation, and the compiler writes the source code for the specialization the programmer requires. One Stack class template, for example, could thus become the basis for creating many Stack classes (such as "Stack of double," "Stack of int," "Stack of char," "Stack of Employee," etc.) used in a program.
Creating Class Template Stack< T >
Note the Stack class-template definition in Fig. 14.2. It looks like a conventional class definition, except that it is preceded by the header (line 6)
template< typename T >
to specify a class-template definition with type parameter T which acts as a placeholder for the type of the Stack class to be created. The programmer need not specifically use identifier Tany valid identifier can be used. The type of element to be stored on this Stack is mentioned generically as T throughout the Stack class header and member-function definitions. In a moment, we show how T becomes associated with a specific type, such as double or int. Due to the way this class template is designed, there are two constraints for nonfundamental data types used with this Stackthey must have a default constructor (for use in line 44 to create the array that stores the stack elements), and they must support the assignment operator (lines 55 and 69).
Figure 14.2. Class template Stack.
(This item is displayed on pages 756 - 757 in the print version)
|
1 // Fig. 14.2: Stack.h 2 // Stack class template. 3 #ifndef STACK_H 4 #define STACK_H 5 6 template< typename T > 7 class Stack 8 { 9 public: 10 Stack( int = 10 ); // default constructor (Stack size 10) 11 12 // destructor 13 ~Stack() 14 { 15 delete [] stackPtr; // deallocate internal space for Stack 16 } // end ~Stack destructor 17 18 bool push( const T& ); // push an element onto the Stack 19 bool pop( T& ); // pop an element off the Stack 20 21 // determine whether Stack is empty 22 bool isEmpty() const 23 { 24 return top == -1; 25 } // end function isEmpty 26 27 // determine whether Stack is full 28 bool isFull() const 29 { 30 return top == size - 1; 31 } // end function isFull 32 33 private: 34 int size; // # of elements in the Stack 35 int top; // location of the top element (-1 means empty) 36 T *stackPtr; // pointer to internal representation of the Stack 37 }; // end class template Stack 38 39 // constructor template 40 template< typename T > 41 Stack< T >::Stack( int s ) 42 : size( s > 0 ? s : 10 ), // validate size 43 top( -1 ), // Stack initially empty 44 stackPtr( new T[ size ] ) // allocate memory for elements 45 { 46 // empty body 47 } // end Stack constructor template 48 49 // push element onto Stack; 50 // if successful, return true; otherwise, return false 51 template< typename T > 52 bool Stack< T >::push( const T &pushValue ) 53 { 54 if ( !isFull() ) 55 { 56 stackPtr[ ++top ] = pushValue; // place item on Stack 57 return true; // push successful 58 } // end if 59 60 return false; // push unsuccessful 61 } // end function template push 62 63 // pop element off Stack; 64 // if successful, return true; otherwise, return false 65 template< typename T > 66 bool Stack< T >::pop( T &popValue ) 67 { 68 if ( !isEmpty() ) 69 { 70 popValue = stackPtr[ top-- ]; // remove item from Stack 71 return true; // pop successful 72 } // end if 73 74 return false; // pop unsuccessful 75 } // end function template pop 76 77 #endif |
The member-function definitions of a class template are function templates. The member-function definitions that appear outside the class template definition each begin with the header
template< typename T >
(lines 40, 51 and 65). Thus, each definition resembles a conventional function definition, except that the Stack element type always is listed generically as type parameter T. The binary scope resolution operator is used with the class-template name Stack< T > (lines 41, 52 and 66) to tie each member-function definition to the class template's scope. In this case, the generic class name is Stack< T >. When doubleStack is instantiated as type Stack< double >, the Stack constructor function-template specialization uses new to create an array of elements of type double to represent the stack (line 44). The statement
stackPtr = new T[ size ];
in the Stack class-template definition is generated by the compiler in the class-template specialization Stack< double > as
stackPtr = new double[ size ];
Creating a Driver to Test Class Template Stack< T >
Now, let us consider the driver (Fig. 14.3) that exercises the Stack class template. The driver begins by instantiating object doubleStack of size 5 (line 11). This object is declared to be of class Stack< double > (pronounced "Stack of double"). The compiler associates type double with type parameter T in the class template to produce the source code for a Stack class of type double. Although templates offer software-reusability benefits, remember that multiple class-template specializations are instantiated in a program (at compile time), even though the template is written only once.
Figure 14.3. Class template Stack test program.
(This item is displayed on pages 758 - 759 in the print version)
|
1 // Fig. 14.3: fig14_03.cpp 2 // Stack class template test program. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include "Stack.h" // Stack class template definition 8 9 int main() 10 { 11 Stack< double > doubleStack( 5 ); // size 5 12 double doubleValue = 1.1; 13 14 cout << "Pushing elements onto doubleStack "; 15 16 // push 5 doubles onto doubleStack 17 while ( doubleStack.push( doubleValue ) ) 18 { 19 cout << doubleValue << ' '; 20 doubleValue += 1.1; 21 } // end while 22 23 cout << " Stack is full. Cannot push " << doubleValue 24 << " Popping elements from doubleStack "; 25 26 // pop elements from doubleStack 27 while ( doubleStack.pop( doubleValue ) ) 28 cout << doubleValue << ' '; 29 30 cout << " Stack is empty. Cannot pop "; 31 32 Stack< int > intStack; // default size 10 33 int intValue = 1; 34 cout << " Pushing elements onto intStack "; 35 36 // push 10 integers onto intStack 37 while ( intStack.push( intValue ) ) 38 { 39 cout << intValue << ' '; 40 intValue++; 41 } // end while 42 43 cout << " Stack is full. Cannot push " << intValue 44 << " Popping elements from intStack "; 45 46 // pop elements from intStack 47 while ( intStack.pop( intValue ) ) 48 cout << intValue << ' '; 49 50 cout << " Stack is empty. Cannot pop" << endl; 51 return 0; 52 } // end main
|
Lines 1721 invoke push to place the double values 1.1, 2.2, 3.3, 4.4 and 5.5 onto doubleStack. The while loop terminates when the driver attempts to push a sixth value onto doubleStack (which is full, because it holds a maximum of five elements). Note that function push returns false when it is unable to push a value onto the stack.[1]
[1] Class Stack (Fig. 14.2) provides the function isFull, which the programmer can use to determine whether the stack is full before attempting a push operation. This would avoid the potential error of pushing onto a full stack. In Chapter 16, Exception Handling, if the operation cannot be completed, function push would "throw an exception." The programmer can write code to "catch" that exception, then decide how to handle it appropriately for the application. The same technique can be used with function pop when an attempt is made to pop an element from an empty stack.
Lines 2728 invoke pop in a while loop to remove the five values from the stack (note, in Fig. 14.3, that the values do pop off in last-in, first-out order). When the driver attempts to pop a sixth value, the doubleStack is empty, so the pop loop terminates.
Line 32 instantiates integer stack intStack with the declaration
Stack< int > intStack;
(pronounced "intStack is a Stack of int"). Because no size is specified, the size defaults to 10 as specified in the default constructor (Fig. 14.2, line 10). Lines 3741 loop and invoke push to place values onto intStack until it is full, then lines 4748 loop and invoke pop to remove values from intStack until it is empty. Once again, notice in the output that the values pop off in last-in, first-out order.
Creating Function Templates to Test Class Template Stack< T >
Notice that the code in function main of Fig. 14.3 is almost identical for both the doubleStack manipulations in lines 1130 and the intStack manipulations in lines 3250. This presents another opportunity to use a function template. Figure 14.4 defines function template testStack (lines 1438) to perform the same tasks as main in Fig. 14.3push a series of values onto a Stack< T > and pop the values off a Stack< T >. Function template testStack uses template parameter T (specified at line 14) to represent the data type stored in the Stack< T >. The function template takes four arguments (lines 1619)a reference to an object of type Stack< T >, a value of type T that will be the first value pushed onto the Stack< T >, a value of type T used to increment the values pushed onto the Stack< T > and a string that represents the name of the Stack< T > object for output purposes. Function main (lines 4049) instantiates an object of type Stack< double > called doubleStack (line 42) and an object of type Stack< int > called intStack (line 43) and uses these objects in lines 45 and 46. The testStack function calls each result in a testStack function-template specialization. The compiler infers the type of T for testStack from the type used to instantiate the function's first argument (i.e., the type used to instantiate doubleStack or intStack). The output of Fig. 14.4 precisely matches the output of Fig. 14.3.
Figure 14.4. Passing a Stack template object to a function template.
(This item is displayed on pages 759 - 760 in the print version)
|
1 // Fig. 14.4: fig14_04.cpp 2 // Stack class template test program. Function main uses a 3 // function template to manipulate objects of type Stack< T >. 4 #include 5 using std::cout; 6 using std::endl; 7 8 #include 9 using std::string; 10 11 #include "Stack.h" // Stack class template definition 12 13 // function template to manipulate Stack< T > 14 template< typename T > 15 void testStack( 16 Stack< T > &theStack, // reference to Stack< T > 17 T value, // initial value to push 18 T increment, // increment for subsequent values 19 const string stackName ) // name of the Stack< T > object 20 { 21 cout << " Pushing elements onto " << stackName >> ' '; 22 23 // push element onto Stack 24 while ( theStack.push( value ) ) 25 { 26 cout << value >> ' '; 27 value += increment; 28 } // end while 29 30 cout << " Stack is full. Cannot push " << value 31 << " Popping elements from " << stackName << ' '; 32 33 // pop elements from Stack 34 while ( theStack.pop( value ) ) 35 cout << value << ' '; 36 37 cout << " Stack is empty. Cannot pop" << endl; 38 } // end function template testStack 39 40 int main() 41 { 42 Stack< double > doubleStack( 5 ); // size 5 43 Stack< int > intStack; // default size 10 44 45 testStack( doubleStack, 1.1, 1.1, "doubleStack" ); 46 testStack( intStack, 1, 1, "intStack" ); 47 48 return 0; 49 } // end main
|