18.2 Class Templates
It’s possible to understand the concept of a stack (a data structure into which we insert items only at the top and retrieve those items only from the top in last-in, first-out order) independent of the type of the items being placed in the stack. We discussed stacks in Section 6.11 where we presented the function-call stack. To instantiate a stack, a data type must be specified. This creates a nice opportunity for software reusability—as you already saw with the stack container adapter in Section 15.7.1. Here, we define a stack generically then use type-specific versions of this generic stack class.
Software Engineering Observation 18.1
Class templates encourage software reusability by enabling a variety of type-specific class-template specializations to be instantiated from a single class template.
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. To produce many specializations you write only one class-template definition (as we’ll do shortly). When a particular specialization is needed, you use a concise, simple notation, and the compiler writes the specialization source code. One Stack class template, for example, could thus become the basis for creating many Stack class-template specializations (such as “Stack of doubles,” “Stack of ints,” “Stack of Employees,” “Stack of Bills,” “Stack of ActivationRecords,” etc.) used in a program.
Common Programming Error 18.1
To create a template specialization with a user-defined type, the user-defined type must meet the template’s requirements. For example, the template might compare objects of the user-defined type with < to determine sorting order, or the template might call a specific member function on an object of the user-defined type. If the user-defined type does not overload the required operator or provide the required functions, compilation errors occur.
18.2.1 Creating Class Template Stack<T>
The Stack class-template definition in Fig. 18.2 looks like a conventional class definition, with a few key differences. First, it’s preceded by line 7
template<typename T>
All class templates begin with keyword template followed by a list of template parameters enclosed in angle brackets (< and >); each template parameter that represents a type must be preceded by either of the interchangeable keywords typename or class (though type-name is preferred). The type parameter T acts as a placeholder for the Stack’s element type. The names of type parameters must be unique inside a template definition. You need not specifically use identifier T—any valid identifier can be used. The element type is mentioned generically throughout the Stack class-template definition as T (lines 11, 16 and 36). The type parameter becomes associated with a specific type when you create an object using the class template—at that point, the compiler generates a copy of the class template in which all occurrences of the type parameter are replaced with the specified type. Another key difference is that we did not separate the class template’s interface from its implementation.
Software Engineering Observation 18.2
Templates are typically defined in headers, which are then #include d in the appropriate client source-code files. For class templates, this means that the member functions are also defined in the header—typically inside the class definition’s body, as we do in Fig. 18.2.
Fig. 18.2 Stack class template.
Alternate View
1 // Fig. 18.2: Stack.h
2 // Stack class template.
3 #ifndef STACK_H
4 #define STACK_H
5 #include <deque>
6
7 template<typename T>
8 class Stack {
9 public:
10 // return the top element of the Stack
11 const T& top() {
12 return stack.front();
13 }
14
15 // push an element onto the Stack
16 void push(const T& pushValue) {
17 stack.push_front(pushValue);
18 }
19
20 // pop an element from the stack
21 void pop(){
22 stack.pop_front();
23 }
24
25 // determine whether Stack is empty
26 bool isEmpty() const{
27 return stack.empty();
28 }
29
30 // return size of Stack
31 size_t size() const{
32 return stack.size();
33 }
34
35 private:
36 std::deque<T> stack;// internal representation of the Stack
37 };
38
39 #endif
18.2.2 Class Template Stack<T>’s Data Representation
Section 15.7.1 showed that the Standard Library’s stack adapter class can use various containers to store its elements. Of course, a stack requires insertions and deletions only at its top. So, for example, a vector or a deque could be used to store the stack’s elements. A vector supports fast insertions and deletions at its back. A deque supports fast insertions and deletions at its front and its back. A deque is the default representation for the Standard Library’s stack adapter because a deque grows more efficiently than a vector. A vector is maintained as a contiguous block of memory—when that block is full and a new element is added, the vector allocates a larger contiguous block of memory and copies the old elements into that new block. A deque, on the other hand, is typically implemented as a list of fixed-size, built-in arrays—new fixed-size built-in arrays are added as necessary and none of the existing elements are copied when new items are added to the front or back. For these reasons, we use a deque (line 36) as the underlying container for our Stack class.
18.2.3 Class Template Stack<T>’s Member Functions
The member-function definitions of a class template are function templates, but are not preceded with the template keyword and template parameters in angle brackets (< and >) when they’re defined within the class template’s body. As you can see, however, they do use the class template’s template parameter T to represent the element type. Our Stack class template does not define it’s own constructors—the default constructor provided by the compiler will invoke the deque’s default constructor. We also provide the following member functions in Fig. 18.2:
top(lines 11–13) returns aconstreference to theStack’s top element.push(lines 16–18) places a new element on the top of theStack.pop(lines 21–23) removes theStack’s top element.isEmpty(lines 26–28) returns aboolvalue—trueif theStackis empty andfalseotherwise.size(lines 31–33) returns the number if elements in theStack.
Each of these member functions calls the appropriate member function of class template deque—this is known as delegating.
18.2.4 Declaring a Class Template’s Member Functions Outside the Class Template Definition
Though we did not do so in our Stack class template, member-function definitions can appear outside a class template definition. If you do this, each must begin with the template keyword followed by the same set of template parameters as the class template. In addition, the member functions must be qualified with the class name and scope resolution operator. For example, you can define the pop function outside the class-template definition as follows:
template<typename T>
inline void Stack<T>::pop() {
stack.pop_front();
}
Stack<T>:: indicates that pop is in the scope of class Stack<T>. The Standard Library’s container classes tend to define all their member functions inside their class definitions.
18.2.5 Testing Class Template Stack<T>
Now, let’s consider the driver (Fig. 18.3) that exercises the Stack class template. The driver begins by instantiating object doubleStack (line 8). This object is declared as a 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 with elements of type double that actually stores its elements in a deque<double>.
Fig. 18.3 Stack class template test program.
Alternate View
1 // Fig. 18.3: fig18_02.cpp
2 // Stack class template test program.
3 #include <iostream>
4 #include "Stack.h" // Stack class template definition
5 using namespace std;
6
7 int main() {
8 Stack<double> doubleStack; // create a Stack of double
9 const size_t doubleStackSize{5}; // stack size
10 double doubleValue{1.1}; // first value to push
11
12 cout << "Pushing elements onto doubleStack
";
13
14 // push 5 doubles onto doubleStack
15 for (size_t i{0}; i < doubleStackSize; ++i) {
16 doubleStack.push(doubleValue);
17 cout << doubleValue << ' ';
18 doubleValue += 1.1;
19 }
20
21 cout << "
Popping elements from doubleStack
";
22
23 // pop elements from doubleStack
24 while (!doubleStack.isEmpty()) {// loop while Stack is not empty
25 cout << doubleStack.top() << ' '; // display top element
26 doubleStack.pop(); // remove top element
27 }
28
29 cout << "
Stack is empty, cannot pop.
";
30
31 Stack<int> intStack; // create a Stack of int
32 const size_t intStackSize{10}; // stack size
33 int intValue{1}; // first value to push
34
35 cout << "
Pushing elements onto intStack
";
36
37 // push 10 integers onto intStack
38 for (size_t i{0}; i < intStackSize; ++i) {
39 intStack.push(intValue);
40 cout << intValue++ << ' ';
41 }
42
43 cout << "
Popping elements from intStack
";
44
45 // pop elements from intStack
46 while (!intStack.isEmpty()) {// loop while Stack is not empty
47 cout << intStack.top() << ' '; // display top element
48 intStack.pop();// remove top element
49 }
50
51 cout << "
Stack is empty, cannot pop." << endl;
52 }
Pushing elements onto doubleStack 1.1 2.2 3.3 4.4 5.5 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 Popping elements from intStack 10 9 8 7 6 5 4 3 2 1 Stack is empty, cannot pop
Lines 15–19 invoke push (line 16) to place the double values 1.1, 2.2, 3.3, 4.4 and 5.5 onto doubleStack. Next, lines 24–27 invoke top and pop in a while loop to remove the five values from the stack. Notice in the output of Fig. 18.3 that the values pop off in last-in, first-out order. When doubleStack is empty, the pop loop terminates.
Line 31 instantiates int stack intStack with the declaration
Stack<int> intStack;
(pronounced “intStack is a Stack of int”). Lines 38–41 repeatedly invoke push (line 39) to place values onto intStack, then lines 46–49 repeatedly invoke top and pop to remove values from intStack until it’s empty. Once again, notice in the output that the values pop off in last-in, first-out order.