A good mechanisms for dealing with these situations should avoid repetitive programming and preserve the type safety normally expect of a well designed class. Avoiding repetitive code means that it should not be necessary to implement as distinct classes MouseEventQueue and CharacterQueue where the only difference between them is the type of the data contained in the queue. 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. 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:
template <class QueueItem> class Queue { private: QueueItem buffer[100]; int head, tail, count; public: Queue(); void Insert(QueueItem item); QueueItem Remove(); ~Queue(); };In this code QueueItem is first used to define the type of the buffer array. This array is used to hold the elements that are 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.
A parameterized type (template) can be used to create a new class by instantiating the template with an appropriate parameter. The template can be used to create a new class in one of two ways. The first way directly creates an object as shown here:
Queue<int> intQueue; // a queue of integers objectIn 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 as shown here:
typedef Queue<int> IntegerQueue; // a class for a queue of integers IntegerQueue intQueue;In either case an object is created that acts like a queue of integers. This object 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 2Notice that there is no difference in the way the intQueue objects is accessed. An object created from an instantitated template is indistinugishable from an object created from a non-parameterized class.
To complete the implementation of a template class each of its methods must be defined. Each template method may be part of several classes. For example the Queue's Remove method may be in the class Queue<int> and in the class Queue<char> and in the class Queue<floatgt>. To prevent confusion the definition of each method must carry a preamble that allows it to be associated with the specific template instantiation to which it belongs. This leads to the (somewhat wordy) syntax:
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 preceeded 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 here:
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*ltint>), 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.
Queue<Queue<int>> Queue <Queue <int> >
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() {}