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

 

 Pushing elements onto doubleStack
 1.1 2.2 3.3 4.4 5.5
 Stack is full. Cannot push 6.6

 Popping elements from doubleStack
 5.5 4.4 3.3 2.2 1.1
 Stack is empty. Cannot pop

 Pushing elements onto intStack
 1 2 3 4 5 6 7 8 9 10
 Stack is full. Cannot push 11

 Popping elements from intStack
 10 9 8 7 6 5 4 3 2 1
 Stack is empty. Cannot pop

 

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

 

 Pushing elements onto doubleStack
 1.1 2.2 3.3 4.4 5.5
 Stack is full. Cannot push 6.6

 Popping elements from doubleStack
 5.5 4.4 3.3 2.2 1.1
 Stack is empty. Cannot pop

 Pushing elements onto intStack
 1 2 3 4 5 6 7 8 9 10
 Stack is full. Cannot push 11

 Popping elements from intStack
 10 9 8 7 6 5 4 3 2 1
 Stack is empty. Cannot pop