7.1 Templates
A number of common programming situations require the same class
structure to be applied to different data types. Examples of such
situations are the following:
- queue class
- a queue of characters entered by a user
- a queue of mouse events that have occurred and are waiting to
be handled
- list class
- a list of windows that currently appear on the screen
- a list of menu items in a menu
- set class
- a set of one or more buttons
- a set of currently available pens or colors
In each case the same basic algorithms and supporting data structures are needed. What varies among uses of the class is the type of data being manipulated.
A good mechanism for dealing with these situations should avoid repetitive programming and preserve the type safety normally expected of a well-designed class. Avoiding repetitive code means that it should not be necessary to implement MouseEventQueue and CharacterQueue as distinct classes when the only difference between them is the type of data contained in their queues. Preserving the type safety means that we do not want to avoid the repetitive code by writing an overly general (type-dumb) class. For example, it is possible to implement a single Queue class that manipulates "void*" types, but this design is overly general because it allows anything to be put into the queue (e.g., MouseEvents in a CharacterQueue).
A template is a parameterized class whose parameter denotes the varying type of data. The syntax in C++ to introduce a template for the queue class is as follows:
template < class QueueItem > class Queue { ... }
Enclosed in the angle brackets after the keyword template is the template parameter. In this example the template parameter, QueueItem, is a class. For a Queue, QueueItem is intended to denote the type of the items that the Queue will hold. The template parameter may be used in the parameterized class (Queue) in one or more of the following ways: to define the argument type of a method in the parameterized class, to define the type returned by a method in the parameterized class, or to define the type of local data that is defined in the parameterized class. These uses of the template parameter are shown in the expansion of the Queue class shown below.
In the code for the Queue template class below, QueueItem is first used to define the type of the buffer array, which is used to hold the elements currently in the queue. The parameter of the Insert method is defined as a QueueItem, matching the declaration of the buffer array where the input value will be stored. Finally, the result returned by the Remove method is also of type QueueItem, since this is the type of data extracted from the buffer array.
|
Queue Template Class |
template <class QueueItem> class Queue {
private:
QueueItem buffer[100];
int head, tail, count;
public:
Queue();
void Insert(QueueItem item);
QueueItem Remove();
~Queue();
};
|
A parameterized type (template) can be used to create a new class by instantiating the template with an appropriate parameter. The template may be used to create a new class in two ways. The first way directly creates an object as shown here:
Queue<int> intQueue; // a queue of integers object
In this case, the object intQueue is defined as an instance of the parameterized typed Queue where the parameter is taken as an int type. The second way uses the typedef to define a type (class) name:
typedef Queue<int> IntegerQueue; // a class for a queue of integers
IntegerQueue intQueue;
In either case an object that acts like a queue of integers is created, and can be manipulated in the usual ways. For example, the queue of integers can be tested as follows:
intQueue.Insert(100); // add 100
intQueue.Insert(200); // add 200
int x = intQueue.Remove(); // remove 100
intQueue.Insert(300); // queue now has (200,300)
int x = intQueue.Size(); // size is 2
Notice that there is no difference in the way the intQueue object is accessed. An object created from an instantiated template is indistinguishable from an object created from a non-parameterized class.
To complete the implementation of a template class, each of its methods must be defined. The syntax for a template method must carry a preamble that associates it with the template and with the template's parameters. This leads to the (somewhat wordy) syntax shown in the figure below.
|
Syntax for Implementing the Methods of a Template Class |
template<class QueueItem> Queue<QueueItem>::Queue()
{ ... }
template<class QueueItem> void Queue<QueueItem>::Insert(QueueItem item)
{ ... }
template<class QueueItem> QueueItem Queue<QueueItem>::Remove()
{ ... }
template<class QueueItem> int Queue<QueueItem>::Size()
{ ... }
template<class QueueItem> Queue<QueueItem>::~Queue()
{ ... }
|
Each method definition is preceded by a template specification (template< class QueueItem>). In addition, the class name contains the template syntax (Queue<QueueItem>::). Note that in the case of the Remove method, the return type comes after the initial template specification and before the class name.
The complete code for the parameterized Queue class is shown in the following figure.
|
A Complete Template Class |
template <class QueueItem> class Queue {
private:
QueueItem buffer[100];
int head, tail, count;
public:
Queue();
void Insert(QueueItem item);
QueueItem Remove();
int Size();
~Queue();
};
template <class QueueItem>
Queue<QueueItem>::Queue() : count(0), head(0), tail(0) {}
template <class QueueItem>
void Queue<QueueItem>::Insert(QueueItem item) {
assert(count <100);
buffer[tail] = item;
tail = (tail + 1)% 100;
count++;
}
template <class QueueItem>
QueueItem Queue<QueueItem>::Remove() {
assert(count > 0);
int val = head;
head = (head + 1)%100;
count--;
return buffer[val];
}
template <class QueueItem>
int Queue<QueueItem>::Size() { return count; }
template <class QueueItem>
Queue<QueueItem>::~Queue() {}
|
Templates also differ from non-parameterized classes in where the method definitions are placed. In non-parameterized classes, the method definitions are put in a code (.cc or .C of .cpp) file. However, for a parameterized class the method definitions are placed in the header (.h) file itself. This is necessary so that when the compiler is asked to elaborate a template (e.g, by seeing a declaration of the form Queue<int>), it need only examine the header file (that has been referenced in a #include statement) to find all of the information that it needs to fully understand how to elaborate the template and generate the code for the required class.
      |
|
- Write a program that creates and manipulates two queues of type Queue<int>. Declare one of the queues directly as a Queue<int> and declare the other queue using a typedef.
- Use the code developed in exercise one to determine if you can assign a queue to a queue. Does this do what you expect? Explain.
- Write a program that creates and manipulates two queues of type Queue<Location>. Declare one of the queues directly as a Queue<Location> and declare the other queue using a typedef.
- Compile the following two declarations. Which one has a syntax
error?
Queue<Queue<int>>Queue <Queue <int> >
- Draw a picture showing what structure is defined by the declaration in exercise four.
- Write a test program that declares and manipulates the queue structure defined in exercise four.
- Named Collection: Implement and write a program to test a template
class that maintains a collection of up to 100 elements, each
of which has an associated name. The type of the elements is defined
by the template parameter while the name is always a string (a
char*). The following example illustrates how the template could
be used:
NamedCollection<int> collection;
...
collection.Add("first", 10); // associate 10 with the name "first"
collection.Add("next", 20); // associate 20 with the name "next"
...
if (collection.Contains("next"))
{ int val = collection.ValueOf("next");
...
}
You may assume that duplicate names do not occur.
- Shown below is the code for an IntArray class. Create a template
version of this class and write a program to test your template.
class IntArray {private:
int array[100];
public:
Array();
int& At(int i);
~Array();
};
IntArray::IntArray() {};
int& IntArray::At(int i)
{assert(0<i && i < 100);
return array[i];
}
IntArray::~IntArray() {}
- Using your Array template, write a test program to create and manipulate a two dimensional integer array as follows: typedef Array< Array<int> > Matrix. How do you access elements in this two dimensional array?
- Write a test program that declares and manipulates an array of queues.
- Write a test program that declares and manipulates a queue of arrays.
|
|
||||
|
|
||||
