Template Definition
You declare a parameterized List object (a template for a list) by writing
1: template <class T> // declare the template and the parameter
2: class List // the class being parameterized
3: {
4: public:
5: List();
6: // full class declaration here
7 :};
The keyword template is used at the beginning of every declaration and definition of a template class. The parameters of the template are after the keyword template; they are the items that will change with each instance. For example, in the list template shown in the previous code snippet, the type of the objects stored in the list will change. One instance might store a list of Integers, whereas another might store a list of Animals.
In this example, the keyword class is used, followed by the identifier T. The keyword class indicates that this parameter is a type. The identifier T is used throughout the rest of the template definition to refer to the parameterized type. One instance of this class will substitute int everywhere T appears, and another will substitute Cat.
To declare an int and a Cat instance of the parameterized list class, you would write
List<int> anIntList;
List<Cat> aCatList;
The object anIntList is of the type list of integers; the object aCatList is of the type ListOfCats. You can now use the type List<int> anywhere you would normally use a type—as the return value from a function, as a parameter to a function, and so forth.
Listing 23.1 parameterizes the List object. This is an excellent technique for building templates: Get your object working on a single type, as we did in Hour 19, “Linked Lists.” Then by parameterizing, generalize your object to handle any type.
Listing 23.1. Demonstrating Parameterized Lists
0: // ***********************************************
1: // FILE: Listing 23.1
2: //
3: // PURPOSE: Demonstrate parameterized list
4: // NOTES:
5: //
6: // COPYRIGHT: Copyright 1997 Liberty Associates, Inc.
7: // All Rights Reserved
8: //
9: // Demonstrates an object-oriented approach to parameterized
10: // linked lists. The list delegates to the node.
11: // The node is an abstract Object type. Three types of
12: // nodes are used, head nodes, tail nodes and internal
13: // nodes. Only the internal nodes hold Object.
14: //
15: // The Object class is created to serve as an object to
16: // hold in the linked list.
17: //
18: // ***********************************************
19: #include <iostream>
20:
21: enum { kIsSmaller, kIsLarger, kIsSame};
22:
23: // Object class to put into the linked list
24: // Any class in this linked list must support two methods:
25: // Show (displays the value) and
26: // Compare (returns relative position)
27: class Data
28: {
29: public:
30: Data(int val):myValue(val){}
31: ~Data()
32: {
33: std::cout << "Deleting Data object with value: ";
34: std::cout << myValue << "
";
35: }
36: int Compare(const Data &);
37: void Show() { std::cout << myValue << std::endl; }
38: private:
39: int myValue;
40: };
41:
42: // compare is used to decide where in the list
43: // a particular object belongs.
44: int Data::Compare(const Data & theOtherObject)
45: {
46: if (myValue < theOtherObject.myValue)
47: return kIsSmaller;
48: if (myValue > theOtherObject.myValue)
49: return kIsLarger;
50: else
51: return kIsSame;
52: }
53:
54: // Another class to put into the linked list
55: // Again, every class in this linked
56: // list must support two methods:
57: // Show (displays the value) and
58: // Compare (returns relative position)
59: class Cat
60: {
61: public:
62: Cat(int age): myAge(age){}
63: ~Cat()
64: {
65: std::cout << "Deleting ";
66: std::cout << myAge << " years old Cat.
";
67: }
68: int Compare(const Cat &);
69: void Show()
70: {
71: std::cout << "This cat is ";
72: std::cout << myAge << " years old
";
73: }
74: private:
75: int myAge;
76: };
77:
78:
79: // compare is used to decide where in the list
80: // a particular object belongs.
81: int Cat::Compare(const Cat & theOtherCat)
82: {
83: if (myAge < theOtherCat.myAge)
84: return kIsSmaller;
85: if (myAge > theOtherCat.myAge)
86: return kIsLarger;
87: else
88: return kIsSame;
89: }
90:
91:
92: // ADT representing the node object in the list
93: // Every derived class must override Insert and Show
94: template <class T>
95: class Node
96: {
97: public:
98: Node(){}
99: virtual ~Node(){}
100: virtual Node * Insert(T * theObject)=0;
101: virtual void Show() = 0;
102: private:
103: };
104:
105: template <class T>
106: class InternalNode: public Node<T>
107: {
108: public:
109: InternalNode(T * theObject, Node<T> * next);
110: ~InternalNode(){ delete myNext; delete myObject; }
111: virtual Node<T> * Insert(T * theObject);
112: virtual void Show()
113: {
114: myObject->Show();
115: myNext->Show();
116: } // delegate!
117: private:
118: T * myObject; // the Object itself
119: Node<T> * myNext; // points to next node in the linked list
120: };
121:
122: // All the constructor does is initialize
123: template <class T>
124: InternalNode<T>::InternalNode(T * theObject, Node<T> * next):
125: myObject(theObject),myNext(next)
126: {
127: }
128:
129: // the meat of the list
130: // When you put a new object into the list
131: // it is passed to the node which figures out
132: // where it goes and inserts it into the list
133: template <class T>
134: Node<T> * InternalNode<T>::Insert(T * theObject)
135: {
136: // is the new guy bigger or smaller than me?
137: int result = myObject->Compare(*theObject);
138:
139: switch(result)
140: {
141: // by convention if it is the same as me it comes first
142: case kIsSame: // fall through
143: case kIsLarger: // new Object comes before me
144: {
145: InternalNode<T> * ObjectNode =
146: new InternalNode<T>(theObject, this);
147: return ObjectNode;
148: }
149: // it is bigger than I am so pass it on to the next
150: // node and let HIM handle it.
151: case kIsSmaller:
152: myNext = myNext->Insert(theObject);
153: return this;
154: }
155: return this; // appease MSC
156: }
157:
158: // Tail node is just a sentinel
159: template <class T>
160: class TailNode : public Node<T>
161: {
162: public:
163: TailNode(){}
164: virtual ~TailNode(){}
165: virtual Node<T> * Insert(T * theObject);
166: virtual void Show() { }
167: private:
168: };
169:
170: // If Object comes to me, it must be inserted before me
171: // as I am the tail and NOTHING comes after me
172: template <class T>
173: Node<T> * TailNode<T>::Insert(T * theObject)
174: {
175: InternalNode<T> * ObjectNode =
176: new InternalNode<T>(theObject, this);
177: return ObjectNode;
178: }
179:
180: // Head node has no Object, it just points
181: // to the very beginning of the list
182: template <class T>
183: class HeadNode : public Node<T>
184: {
185: public:
186: HeadNode();
187: virtual ~HeadNode() { delete myNext; }
188: virtual Node<T> * Insert(T * theObject);
189: virtual void Show() { myNext->Show(); }
190: private:
191: Node<T> * myNext;
192: };
193:
194: // As soon as the head is created
195: // it creates the tail
196: template <class T>
197: HeadNode<T>::HeadNode()
198: {
199: myNext = new TailNode<T>;
200: }
201:
202: // Nothing comes before the head so just
203: // pass the Object on to the next node
204: template <class T>
205: Node<T> * HeadNode<T>::Insert(T * theObject)
206: {
207: myNext = myNext->Insert(theObject);
208: return this;
209: }
210:
211: // I get all the credit and do none of the work
212: template <class T>
213: class LinkedList
214: {
215: public:
216: LinkedList();
217: ~LinkedList() { delete myHead; }
218: void Insert(T * theObject);
219: void ShowAll() { myHead->Show(); }
220: private:
221: HeadNode<T> * myHead;
222: };
223:
224: // At birth, i create the head node
225: // It creates the tail node
226: // So an empty list points to the head which
227: // points to the tail and has nothing between
228: template <class T>
229: LinkedList<T>::LinkedList()
230: {
231: myHead = new HeadNode<T>;
232: }
233:
234: // Delegate, delegate, delegate
235: template <class T>
236: void LinkedList<T>::Insert(T * pObject)
237: {
238: myHead->Insert(pObject);
239: }
240:
241: // test driver program
242: int main()
243: {
244: Cat * pCat;
245: Data * pData;
246: int val;
247: LinkedList<Cat> ListOfCats;
248: LinkedList<Data> ListOfData;
249:
250: // ask the user to produce some values
251: // put them in the list
252: for (;;)
253: {
254: std::cout << "What value? (0 to stop): ";
255: std::cin >> val;
256: if (!val)
257: break;
258: pCat = new Cat(val);
259: pData= new Data(val);
260: ListOfCats.Insert(pCat);
261: ListOfData.Insert(pData);
262: }
263:
264: // now walk the list and show the Object
265: std::cout << "
";
266: ListOfCats.ShowAll();
267: std::cout << "
";
268: ListOfData.ShowAll();
269: std::cout << "
************
";
270: return 0; // The lists fall out of scope and are destroyed!
271: }
|
What value? (0 to stop): 5
What value? (0 to stop): 13
What value? (0 to stop): 2
What value? (0 to stop): 9
What value? (0 to stop): 7
What value? (0 to stop): 0
This cat is 2 years old
This cat is 5 years old
This cat is 7 years old
This cat is 9 years old
This cat is 13 years old
2
5
7
9
13
************
Deleting Data object with value: 13
Deleting Data object with value: 9
Deleting Data object with value: 7
Deleting Data object with value: 5
Deleting Data object with value: 2
Deleting 13 years old Cat.
Deleting 9 years old Cat.
Deleting 7 years old Cat.
Deleting 5 years old Cat.
Deleting 2 years old Cat.
 | The first thing to notice is the striking similarity to the listing in Hour 19. Go ahead, find the original listing; I'll wait right here…. As you can see, little has changed. |
The biggest change is that each of the class declarations and methods is now preceded by
This tells the compiler that you are parameterizing this list on a type that you will define later, when you instantiate the list. For example, the declaration of the Node class now becomes
template <class T>
class Node
This indicates that Node will not exist as a class in itself, but rather that you will instantiate Nodes of Cats and Nodes of Data objects. The actual type you'll pass in is represented by T.
Thus, InternalNode now becomes InternalNode<T> (read that as “InternalNode of T”). And InternalNode<T> points not to a Data object and another Node; rather, it points to a T (whatever type of object) and a Node<T>. You can see this on lines 118 and 119.
Look carefully at Insert, defined on lines 133–156. The logic is just the same, but where we used to have a specific type (Data) we now have T. Thus, on line 134 the parameter is a pointer to a T. Later, when we instantiate the specific lists, the T will be replaced by the compiler with the right type (Data or Cat).
The important thing is that the InternalNode can continue working, indifferent to the actual type. It knows to ask the objects to compare themselves. It doesn't care whether Cats compare themselves in the same way Data objects do. In fact, we can rewrite this so that Cats don't keep their age; we can have them keep their birth date and compute their relative age on the fly, and the InternalNode won't care a bit.
