13.1 TEMPLATIZED CLASSES AND FUNCTIONS IN C

13.1 TEMPLATIZED CLASSES AND FUNCTIONS IN C++

We will use the prototypical example of a linked list to illustrate the concepts and the syntax of class and function parameterization in C++. We will first see how one might structure a regular (meaning, a non-parameterized) C++ program for a linked-list of ints. We will then "templatize" (or "parameterize") the program so that the same program can be used for different data types.

13.1.1 A C++ Implementation of a Linked-List Program

We evidently need some kind of a data structure to serve as a node in a linked list. We could use the following structure:

     struct Node {         Node* previous;         Node* next;         int item;         // ....     }; 

In this node, the data member item can be used to store one item in a list of integers and the data members previous and next tell us how to get to the previous node and to the next node in a linked list.^[2]

To be able to create a node, we also need a constructor for a Node:

     struct Node {         Node* previous;         Node* next;         int item;         //node constructor:         Node(Node* p, Node* n, int i) : previous(p), next(n), item(i){}     }; 

We can now create a new Node by

     int i = 10;     Node* newNode = new Node(0, 0, i); 

and then link it to previousNode, a previously constructed node, by

     previousNode->next = newNode;     newNode->previous = previousNode; 

The entire chain of nodes created in this manner can be encapsulated in an object of type LinkedList, defined below, so as to hide the details of the implementation from a user of the linked list:

 
     class LinkedList {         struct Node {                                     //(A)             Node* previous;             Node* next;             int item;             Node( Node* p, Node* n, int i)                   : previous(p), next(n), item(i) {}         };         Node* head;                                       //(B)     public:         // code for constructors, destructor,         // copy constructor, copy assignment         // operator, add and remove functions         // for the nodes, and so on.          }; 
 

Note how the struct Node in line (A), together with its constructor, belongs to the private section of LinkedList. That's because the users of a LinkedList do not need to know how exactly the members of a LinkedList are stored and constructed. Also private to the class LinkedList is the data member head in line (B), which will serve as a pointer to the first node of a linked list.

What follows is a working partial implementation for the LinkedList class. We have provided implementation code for a no-arg constructor; a constructor for the first item inserted in the list; a destructor; an addToList() function; a removeFromList() function; and a print function. However, we have left the implementations of the copy constructor and the copy assignment operator as exercises for the reader.

 
 //LinkedList.cc #include <iostream> using namespace std; class LinkedList {     struct Node {         Node* previous;         Node* next;         int item;         Node( Node* p, Node* n, int i)               : previous(p), next(n), item(i) {}     };     Node* head; public:     //no-arg constructor:     LinkedList();                                                 //(C)      //constructor:     LinkedList( int x );                                          //(D)     //copy constructor (exercise for the reader):     LinkedList( const LinkedList& 11 );                           //(E)     //copy assignment operator (exercise for the reader):     LinkedList& operator=( const LinkedList& 11 );                //(F)     //destructor:     ~LinkedList();                                                //(G)     void addToList( int );                                        //(H)     void removeFromList( int );                                   //(I)     void printAll();                                              //(J) };   //end of class definition LinkedList:: LinkedList() : head(0) {}                            //(K) LinkedList::LinkedList( int x ) : head( new Node(0, 0, x) ) {}    //(L) //always add at the end of the list void LinkedList::addToList( int m ) {                             //(M)     Node* p = head;     //check if the list was created previously. If not     //start the list:     if ( p == 0 ) {         head = new Node( 0, 0, m );         return;     }    //find the end of the list:    while (p->next)        p = p->next;    //now add a new node at the end:    p->next = new Node(0, 0, m);    p->next->previous = p; } //removes the first occurrence only void LinkedList::removeFromList( int m ) {                        //(N)     Node* p = head;     //trying to remove from an empty list:     if ( p == 0 ) return;     //search for the item to be removed:     while (p->item != m) {        //end of list reached without finding the item:        if (p->next == 0) return;        p = p->next;    }       //if item was found in the first node:    if (p == head) {        head = head->next;        head->previous = 0;        delete p;        return;    }    //link the previous node to the next node so that    //the current node containing the item can be deleted:    p->previous->next = p->next;    //unless the item to be deleted is at the end of the list,    //link the next node back to the previous node:    if (p->next != 0) p->next- >previous = p->previous;    //now delete the node containing the item:    delete p; } void LinkedList::printAll() {                                     //(O)     for ( Node* p = head; p; p = p- >next ) cout << p->item << ' ';     cout << endl; } LinkedList::~LinkedList() {                                       //(P)     Node* p = head;     while ( p != 0 ) {         Node* temp = p;         p = p->next;         delete temp;     } } int main() {     LinkedList alist(3);              // 3     alist.addToList(5);               // 3 5     alist.addToList(7);               // 3 5 7     alist.addToList(9);               // 3 5 7 9     alist.addToList(11);              // 3 5 7 9 11     alist.printAll();                 // 3 5 7 9 11         alist.removeFromList(7);     alist.printAll();                 // 3 5 9 11         alist.removeFromList(3);          // 5 9 11     alist.printAll();         alist.removeFromList( 11 );     alist.printAll();                 // 5 9 } 
 

The no-arg constructor, declared in line (C) and defined in line (K), sets the data member head to the null pointer, an appropriate thing to do for an empty list. We then declare in line (D) and define at (L) what it means for a LinkedList to contain a single integer. For this case, we have a LinkedList of just one node, pointed to by the data member head, whose previous and next pointers are both null and for which the item data member is set equal to the int to be stored.

Lines (E) and (F) carry declarations for the copy constructor and the copy assignment operator. Implementations of these are left as exercises for the reader. (Obviously, the code in main does not invoke either the copy constructor or the copy assignment operator.)

The destructor is declared in line (G) and its implementation provided in line (L). As you'd expect, the destructor hops from node to node and frees up the memory occupied by each.

A linked list would not be very useful if it was not possible to add to it new items and to delete from it existing item. The functions addToList() and removeFromList(), declared in lines (H) and (I) and with implementations provided in lines (M) and (N), provide the class with this basic functionality.

Finally, we have also provided the class with a print function declared in line (J), with its implementation in line (O).

13.1.2 A Parameterized Linked-List Program

The program we showed in the previous section can only be used for storing a list of ints, or for storing other data types that the compiler is allowed to convert to int. We could write a similar program for storing a list of chars, strings, and so on. All of these programs would have a great deal in common, as was mentioned before, but would not be interchangeable functionally.

We will now create a parameterized version of the linked-list program of the previous section. We will then be able to use this more general program directly for creating linked lists of different data types.

Here is a parameterized version of the class LinkedList, with only the prototypes shown for four out of six functions in the public section of the class. This class definition does not include a copy constructor and a copy assignment operator for the class, whose implementations are left as exercises for the reader.

 
 template <class T> class LinkedList {                         //(A)     struct Node {         Node* previous;         Node* next;         const T& item;                                        //(B)         Node( Node* p, Node* n, const T& t)                   //(C)                  : previous(p), next(n), item(t) {}     };     Node* head;                                               //(D) public:     LinkedList() : head() {}                                  //(E)     LinkedList( const T& t ) : head( new Node(0, 0, t)) {}    //(F)     ~LinkedList();                                            //(G)     void addToList( const T& );                               //(H)     void removeFromList( const T& );                          //(I)     void printAll();                                          //(J) }; 
 

Note the prefix

     template<class T> 

in the header of the class definition in line (A). This prefix specifies that a templatized (or parameterized) class is being declared, with the identifier T serving as a type parameter (or the template parameter). What we have created above is a class template, as opposed to a function template that we will talk about shortly. The name of this class template is LinkedList. The scope of the type parameter T extends to the end of the block that follows the header in line (A).

A templatized class can be used like any other class in C++ after a previously defined type is substituted for the template parameter. For example, the above templatized class could be used as the following classes:

       LinkedList<int>       LinkedList<double>       LinedList<float>       LinkedList<string> 

or, even,

       LinkedList<LinkedList> 

provided the operators used in the function definitions are defined for this type.

A templatized class will, in general, contain constructors and functions that utilize the type parameters used for the parameterization of the class. For example, the constructor shown in line (F) utilizes the type parameter T. When such constructors and functions are given in-class definitions, the implementation code looks much like that for a non-templatized class. However, when it is desired to provide the implementation code outside the body of a class, the headers of the the definitions need to be expressed in a particular way.

Consider, for example, the function addToList( T item ) whose prototype is included in line (H) in the definition of the LinkedList class above. To provide a definition for this function outside the class, its syntax would be something like this:

 template <class T> void LinkedList<T>::addToList( const T& item ) {     Node* p = head;     //check if the list was created previously. If not     //start the list:     if ( p == 0) {         head = new Node(0, 0, item );         return;     }     //find the end of the list:     while (p->next)         p = p->next;     //now add a new node at the end:     p->next = new Node(0, 0, item);     p->next->previous = p; } 

Note how the implementation of the function carries the prefix template<class T> in its header. Then comes the return type of the function, in this case void. This is followed by the name of the class template for which the function is being defined, the name here being LinkedList<T>. Next comes the scope operator ::, followed by actual name of the function, addToList. The parameter list that comes next also contains the type parameter T in the example here. Such a function definition may be referred to as a function template, although that name is used more frequently for templatized versions of stand-alone functions.

Here is the code for a templatized version of the linked list program. Note again that it is only a partial working implementation of the class, partial in the sense that we have not provided the class with a copy constructor and a copy assignment operator, and so on, whose implementations are left to the reader as exercises.

 
 //LinkedListGeneric.cc #include <iostream> #include <string> using namespace std; template <class T> class LinkedList {                   //(A)     struct Node {         Node* previous;         Node* next;         const T& item;                                  //(B)         Node(Node* p, Node* n, const T& t)              //(C)                 : previous(p), next(n), item(t) {}     };     Node* head;                                          //(D) public:     LinkedList() : head() {}                             //(E)     LinkedList(const T& t) : head(new Node(0, 0, t)) {}  //(F)     ~LinkedList();                                       //(G)     void addToList(const T&);                            //(H)     void removeFromList(const T&);                       //(I)     void printAll();                                     //(J) }; template<class T> LinkedList<T>::~LinkedList() {     Node* p = head;     while (p!= 0 ) {         Node* temp = p;         p = p->next;         delete temp;     } } template <class T> void   LinkedList<T>::addToList(const T& item) {     Node* p = head;     //check if the list was created previously. If not     //start the list:     if ( p == 0 ) {         head = new Node( 0, 0, item);         return;     }     //find the end of the list:     while (p->next)         p = p->next;     //now add a new node at the end:     p->next = new Node(0, 0, item);     p->next->previous = p; } template<class T> void LinkedList<T>::removeFromList(const T& item) {     Node* p = head;     for (; p->item!= item; p = p->next)                          //(K)         if (p->next == 0) return;       // item not in list     if (p == head) {                    // item in the first node         head = head->next;         head->previous = 0;         delete(p);         return;     }     p->previous->next = p->next;     if (p->next!=0)       // item to be deleted is at the end of list       p->next->previous = p->previous;     delete(p); } template<class T> void LinkedList<T>::printAll() {     for (Node* p = head; p; p = p->next)         cout << p->item << ' '; } //a class for testing the linked-list program for user-defined types: class X {                                                          //(L)     int n; public:     X( int nn ) : n(nn) {}     bool operator==(const X& xobj)  const {return n == xobj.n;}     bool operator!=(const X& xobj) const {return n!= xobj.n;}     friend ostream& operator<<(ostream& os, const X&       xobj) {         os << xobj.n << " ";     }     ~X(){} }; int main() {     //a linked-list of ints:     int i = 1;                                                     //(M)     LinkedList<int>* numlist =   new LinkedList<int>(i);     numlist->addToList(5);     numlist->addToList(6);     numlist->printAll();                // 1 5 6     cout << endl;     numlist->removeFromList(6);     numlist->printAll();                // 1 5     cout << endl;     delete numlist;     //a linked-list of chars:     char x = 'c';                                                  //(N)     LinkedList<char>* charlist =      new LinkedList<char>(x);     charlist->addToList('a');     charlist->addToList('t');     charlist->printAll();               // c a t     cout << endl;     charlist->removeFromList('c');     charlist->printAll();               // a t     cout << endl;     delete charlist;     //a linked-list of string types:     string str1("high");                                           //(O)     string str2("sierras");     string str3("green");     string str4("tiaras");     LinkedList<string>* stringList   = new LinkedList<string>(str1);     stringList->addToList(str2);     stringList->addToList(str3);     stringList->addToList(str4);     stringList->printAll();              // high sierras green  tiaras     cout << endl;     stringList->removeFromList(str1);     nstringList->printAll();             // sierras green tiaras     cout << endl;     delete stringList;     //a linked-list of user-defined class types:     X xobj1(300);                                                  //(P)     X xobj2(400);     X xobj3(500);     LinkedList<X>* listptr = new         LinkedList<X>(xobj1);     listptr->addToList(xobj2);     listptr->addToList(xobj3);     listptr->printAll();                  // 300 400 500     cout << endl;     listptr->removeFromList(xobj1);     listptr->printAll();                  // 400 500     cout << endl;     delete listptr;          return 0; } 
 

The code shown in main above tests the templatized linked-list by constructing a list of integers in the code section starting in line (M); a list of characters in the code section beginning in line (N); a list of strings in the code section starting in line (O); and, finally, a list of objects of type X, a programmer-defined class defined in line (L) of the program. The last linked-list is in the code section beginning in line (P).

With regard to using the above program for a linked-list of class type objects, the list only stores const references to the objects created in main. (On the other hand, the STL list stores copies of the objects.) This should be clear from the type of the data member item in line (B). As shown in line (C), the node constructor is passed the object to be stored as a const reference. The same is the case with the functions for adding new objects to the list and removing objects from the list. This implies that there is only one copy of each class type object created in main. This can be verified by placing a print statement in the destructor for class X. As the reader will see, X's destructor will be invoked only once for each of the X objects created in main.

13.1.3 Template Specialization

It is not always possible to write a C++ template class that would work universally for every data type. In such cases, it could become necessary to provide alternative definitions for the same template and let the compiler choose the most applicable one.

For example, the previously defined class template for a linked list would not work for those types for which the overload definitions of the operators ‘==’ and ‘!=’ (needed, for instance, in line (K) of the code for removeFromList() above) are not provided.

To illustrate this point, let's say we would like to use the previously defined class template for C-style strings—that is, for the type char*. In other words, we wish to create objects of type

      LinkedList<char*> 

But that obviously will not work because C-style strings are traditionally compared using the strcmp() function from the string.h library and not by using the ‘==’ and ‘!=’ operators. So, in such cases, we may wish to provide an alternative definition of the template, as we do below.

Shown below is a specialization of the LinkedList<T> class for the case of char*. Note that the program pulls in the template class of the previous program, LinkedListGeneric.cc, through the header file LinkedListGeneric.h. So, now, when we try to make a linked-list of integers in main, the compiler automatically chooses the original template class defined in LinkedListGeneric.cc. On the other hand, when we try to make a linked-list of C-style strings, the compiler uses the specialization provided here.

 
 //LinkedListSpecialized.cc #include<iostream> #include "LinkedListGeneric.h"   // This is the same as the program                                  // LinkedListGeneric.cc but without                                  // its main() class LinkedList<char*> {                                          //(A)     struct Node {         Node* pre;         Node* next;         char* item;         Node( Node* p, Node* n, char* c)                  : pre(p), next(n), item(c) {}     };     Node* head; public:     LinkedList() : head(0) {}     LinkedList( char* t ) : head( new Node(0, 0, t)) {}     ~LinkedList() {         Node* p = head;         while (p!= 0) {             Node* temp = p;             p = p->next;             delete temp;         }     }     void printAll() {         for (Node* p = head; p; p = p-  >next )             cout << p->item << ' ';     }     void addToList(char*);     void removeFromList(char*); }; void LinkedList<char*>::addToList(char* item) {                   //(B)     Node* newNode = new Node(0, head, item);     head = newNode;     newNode->next->pre = head; } void LinkedList<char*>::removeFromList(char* item) {     Node* p = head;     for (; 0 != strcmp(p->item, item); p = p->next)         if (p->next == 0) return;          // string not in list     if (p == head) {                       // string in the first node         head = head->next;         head->pre = 0;         delete p;         return;     }     p->pre->next = p->next;     if (p->next != 0) p->next- >pre = p->pre;     delete p; }      int main() {     // use the template class from LinkedListGeneric.h for storing ints     int i = 1;     LinkedList<int>* numlist = new LinkedList<int>(i);     numlist->addToList(5);     numlist->addToList(6);     numlist->printAll();                            // 6 5 1     cout << endl;     numlist->removeFromList(6);     numlist->printAll();                            // 5 1     cout << endl;     // use the specialized template class defined here     // for a list of C-style strings     char* cstr = "high";     LinkedList<char*>* cstringList = new LinkedList<char*>(cstr);     cstringList->addToList("sierras");     cstringList->addToList("green");     cstringList->addToList("tiaras");     cstringList->printAll();         // tiaras green sierras high     cout << endl;     cstringList->removeFromList(high");     cstringList->printAll();              // tiaras green sierras     cout << endl;     return 0; } 
 

As shown in line (A) of the template specialization provided above, the prefix template <class T> is now missing from the header of the class definition. However, if we so wanted, we could have used the prefix template <> and defined the specialization as

     template <> class LinkedList<char*> {         // same as before     }; 

Although we do not need the prefix any more, the compiler knows that this specialization is an alternative to the LinkedList template defined previously in LinkedListGeneric.cc. So when we try to make objects of type LinkedList<char*>, it will automatically choose the specialization rather than the original implementation.

For the same reason we did not need the prefix template<class T> for the class template, we do not need it for the functions whose implementation code is provided outside the class, as shown by the function header in line (B) above.

In some cases, it might be possible to provide a single specialization for all pointer types. In fact, Stroustrup recommends defining a specialization for void* that'd work for all pointer types [54]. But it may not always be possible to do so. For example, we could not have defined a LinkedList<void*> specialization in the same manner we defined LinkedList<char*> because the function strcmp() in removeFromList() must have char* arguments.

13.1.4 General Syntax of a Template Declaration

Now that the reader has an idea of what C++ templates are, it is time to introduce the full syntax of a template declaration for a templatized class:

      template< ---- template parameter list ---- > class nameOfClass {          // implementation      }; 

What follows the keyword template inside the tokens ‘<’ and ‘>’ is called the template parameter list. In this list, a parameter can be either a type parameter or a nontype parameter representing a constant expression.

A type parameter consists of the keyword class or the keyword typename followed by an identifier.^[3] A nontype parameter consists of an ordinary parameter declaration.

Let's first consider the case in which the template parameter list consists of only type parameters:

      template < class T1, class T2, class T3 > class className {          // ....      }; 

Here the parameters T1, T2, and T3 can be any built-in or user-defined types.

Now let's consider the case, taken from Stroustrup [54], in which a template parameter list has both a type parameter and a nontype parameter:

     template< class T, int i > class Buffer {         T v[ i ];         int sz;     public:         Buffer() : sz(i) {}         //      }; 

Here i is a nontype parameter in the parameter list of the template. So nontype parameters in a template parameter list are ordinary parameter declarations. You can think of a nontype parameter as representing a constant in a template definition. In the above definition, the parameter i determines the size of the buffer. So a declaration like

     Buffer<char, 128> cbuf; 

declares cbuf to be a char Buffer of size 128.

The parameters in a template parameter list are allowed to have default values. These work just like the default values for function parameters. As was the case with function parameters, the parameters are default initialized from the right of the parameter list, meaning that a default-initialized parameter cannot be to the left of an uninitialized parameter. For example, the above definition for the template class Buffer could have been written in the following manner:

     template< class T, int i = 128 > class Buffer {         T v[ i ];         int sz;     public:         Buffer() : sz(i) {}         //     }; 

which specifies a default value of 128 for the nontype parameter i, or, in the following manner:

     template< class T = string, int i = 128 > class Buffer {         T v[ i ];         int sz;     public:         Buffer() : sz(i) {}         //     }; 

where we have default choices for both the type parameter and the nontype parameter. The second choice for defining our templatized Buffer class allows us to declare different kinds of buffers of different sizes as in the examples below:

      Buffer<> buf1;                // a string buffer of size 128      Buffer<string, 512> buff2;    // a string buffer of size 512      Buffer<int> buff3;            // an int buffer of size 128      Buffer<int, 512> buff4;       // an int buffer of size 512 

^[2]A minimalist implementation of a linked list would only use one of the linking pointers, either a pointer to the next node or a pointer to the previous node.

^[3]The keyword typename may not be supported in some of the current compilers. The reason for why we need the keyword typename is explained in Section 2.2.1 of Josuttis [42].