6.4 Templates with Related 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 declaration is:

   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();
};

	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

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 equiped with a pointer that can be used for this purpose.

To maintain the structure of the list another template is defined that is related to the List template. This second template will provide the needed pointer and will also be to place 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 follows:

	template  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();
        };

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 other 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.

   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(){}

   template  class List {
   private:
      Node *head;           // begining of list
      Node *current;        // current element in traversal
      Node *previous;       // previous element; needed for deletion
   public:

      ... // shown above

   };

The most interesting of the List template's methods 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). 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.

   template  
   void List::Insert(BaseType val) {
      Node *newNode = new Node(val);
      if (!head) { 
         head = current = newNode;
         return;}
      assert(current);
      newNode->ConnectTo(current->Next());
      current->ConnectTo(newNode);
      current = newNode; 
    }

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