7.4 Templates with Related Parameters


 

Two or more templates may be designed to be used together. It is frequently the case for such templates that they share a common parameter. That is, in order for the templates to cooperate as intended, it is necessary that they manipulate a common type that is defined by one of their template parameters.

A singly linked list will be used to illustrate two related templates. One of the template classes in the example is the template for the list itself, whose partial definition is given in the figure below. In this definition, the type of the data maintained in the list is given by the template parameter BaseType.


Partial Definition of the List Template
template <class BaseType> class List {
   private:
       ...
   public:

               List();
     void      First();                   // set current element to first element
     void      Next();                    // advance to next list element
     int       Done();                    // is there a "current" element?
     BaseType& Current();                 // reply current value
     void      Insert(BaseType val);      // insert after current element
     void      Delete();                  // delete current element
    ~List();
};

  

The list is intended to be used as follows:

       List<int> list;        // create a list of integers

        list.Insert(100);      // add six elements to the list
        list.Insert(200);
        list.Insert(300);
        list.Insert(400);
        list.Insert(500);
        list.Insert(600);

        list.First();                           // start at first element
        while(!list.Done()) {                   // iterate through the list
           cout << list.Current() << endl;      // print current element
           list.Next();                         // move to next element
        }

        list.First();           //  
        list.Next();            //  move to third element...
        list.Next();            //      
        list.Delete();          // ...and delete it

        list.First();
        list.Next();            // for second element...
        list.Current() = 999;   // ...change its value

The List template provides for a list of arbitrary length. The methods of the List template allow elements to be inserted and deleted from the list. Iteration through the list is provided by the method First, Next, Current, and Done. Since the Current method returns a reference, it is possible to assign a new value directly to an element in the list without having to delete the existing element and insert a newly created element.

A design issue for this template class is how to maintain the structure of the list. A general list implementation usually uses a linked-list technique, where each element in the list maintains a pointer to the next element in the list. However, the int type does not come equipped with a pointer that can be used for this purpose.

To maintain the structure of the list, another template related to the List template is defined. This second template will provide the needed pointer and will also be placed where the value of the list element is stored. In essence, this second template is creating the abstraction of an entity in a linked list that maintains a value of the same type as that defined for the list itself. Since an element in a linked list structure is sometimes referred to as a "node" in the list, the template class is defined as shown in the figure below.


The Node Template
template <class BaseType> class Node {
        private:
          BaseType        value;        // value contained in this node in the list
          Node<BaseType> *next;         // next element in the list
        public:

                           Node(BaseType base);
           BaseType&       Value();
           void            ConnectTo(Node<BaseType>* nxt);
           Node<BaseType>* Next();
                          ~Node();
        };

       

The fact that the Node template and the List template use the same name (BaseType) to refer to their template argument does not guarantee that the same type will be used to elaborate both templates. Only the pattern of usage will guarantee this effect. The code for the List template shown in Code Sample 7-12 illustrates how the two templates are related.

Notice that the Node template maintains a private data member of BaseType; this is the value that will be held by the Node when it is in the linked list. The next pointer is the link to the next element in the linked list. The type of the next pointer, Node<BaseType>, correctly indicates that a Node of a given BaseType points to another Node of that same BaseType.

Two of the methods of the Node template provide ways to manipulate the value portion of the Node and two others provide ways to deal with the linked-list portion of the Node. The constructor and Value methods allow the Node's value to be initialized, read and updated. The ConnectTo and Next methods allow a Node to be linked to another Node and for this link to be followed.

The code for the Node template is straightforward, as shown in the following figure.


Implementation of the Node Template
  template <class BaseType> 
   Node<BaseType>::Node(BaseType base) :value(base), next(0) {}

   template <class BaseType> 
   BaseType& Node<BaseType>::Value(){return value;}

   template <class BaseType> 
   void Node<BaseType>::ConnectTo(Node<BaseType>* nxt) {next = nxt; }

   template <class BaseType> 
   Node<BaseType>* Node<BaseType>::Next() {return next; }

   template <class BaseType> 
   Node<BaseType>::~Node(){}

  

The relatedness of the List and Node templates is achieved in the data and code of the List class. The private data of the List class is as follows.


Relationship Between the List and Node Templates
  
   template <class BaseType> class List {

     private:
        Node<BaseType> *head;           // beginning of list
        Node<BaseType> *current;        // current element in traversal
        Node<BaseType> *previous;       // previous element; needed for deletion

     public:

      ... // shown above

   };

The List class maintains three pointers, each of type Node<BaseType>* where BaseType is the parameter of the List class itself. Thus, the type used to elaborate the List template is also used to elaborate the Node template. The relatedness comes because of the relationship between the two templates defined in the List template. The three pointers indicate the first element in the list (head), the current element in a traversal of the list (current), and the element immediately preceding the current element (previous).

The most interesting methods of the List template are those for inserting and deleting an element. The Insert method is given a value of the BaseType that is to be added into the list. The method first creates a new Node<BaseType> object to hold the value (and supply the pointer needed to build the linked list), and this new object (newNode) is then added as the first element of the list, if the list is empty, or added immediately after the current element. An assert is used to insure that the program will abort if there is no "current" element. The implementation of the Insert and Delete methods is given below.


Implementation of the Insert and Delete Methods
template <class BaseType>  
   void List<BaseType>::Insert(BaseType val) {
      Node<BaseType> *newNode = new Node<BaseType>(val);
      if (!head) { 
         head = current = newNode;
         return;}
      assert(current);
      newNode->ConnectTo(current->Next());
      current->ConnectTo(newNode);
      current = newNode; 
    }

   template <class BaseType> 
   void List<BaseType>::Delete() {
      assert(current);
      Node<BaseType> *temp = current;
      if(current == head) {
         head = head->Next();
         current = head;
         delete temp;
         return;
       }
       assert(previous);
       current = current->Next();
       previous->ConnectTo(current);
       delete temp;
    }

The Delete method removes the current element from the list and disposes of it. Two assert calls are used to ensure that the current and previous pointers are not null. As with the Insert method, the Next and ConnectTo methods of the Node class are used to maintain the current structure of the list.

 

  1. Write the destructor for the List template. Be sure that memory leaks are avoided.

  2. Complete the implementation of the List template and test your implementation for a variety of classes.

  3. Revise the List template by adding a method that allows a new element to be appended to the end of the list.

  4. Revise the List template by adding a method that allows a new element to be prepended to the front of the list.

  5. Design and implement a DoubleLinkedList template. Test your implementation for a variety of classes.

 




©1998 Prentice-Hall, Inc.
A Simon & Schuster Company
Upper Saddle River, New Jersey 07458

Legal Statement