The apclasses used in the course so far have been templated to support the storage of different data types.  It is now time to learn how to implement your own templated class.  The student outline will focus on a templated list class while the lab exercise will have you change the implementation of the apstack class.

The key topics for this lesson are:

A.  Templates
B.   A Templated-List class
C.  Overloading the List Assignment Operator   
D.  The List class Copy Constructor and Destructor

VOCABULARY:                   TEMPLATE                            TEMPLATED CLASS

DISCUSSION:                      

A.  Templates

1.   A template in general is like a stencil or original from which we duplicate similar but different objects.  A templated function generates similar copies of a function to work with different data types.  Here is a review of templated functions as presented in Lesson 7.

2.   A function template must begin with the keyword template followed by a list of formal parameters.  The formal parameters must be enclosed in angle brackets (<, >).  Each parameter must be preceded by the keyword class.  For example, in

template <class itemType>

      the identifier itemType is a formal parameter which becomes an alias for some other data type.  In the templated swap function

template <class itemType>

void swap (itemType &a, itemType &b)

{

        itemType  temp = a;

        a = b;

        b = temp;

}

      the identifier itemType will become whatever data type is passed to the swap function.  If swap is used to swap two integers, then itemType becomes an alias for the integer type.

3.   It is possible to allow for more than one templated data type to be defined within the angle brackets.

template  <class typeA, class typeB>

      Notice that each identifier must be preceded by the keyword class.

4.   We now extend this ability to template functions in C++ to support templated classes.

  B.   A Templated-List class

1.   A list is a simple data structure which will maintain a list of data, sometimes ordered based on a value, other times unordered.  We would like to code a list which can store and manipulate lists of whatever data type we wish.

list();                                              default constructor

list (const list &);                          copy constructor

~list();                                            destructor

void insert (const itemType &);    insert item in list,

                                                      list is unordered

void print();                                   print entire list

int length();                                   returns length of list

const list & operator= (const list &);       assignment operator

3.   The best approach when developing a list class would be to separate the interface (list.h) file from the implementation (list.cpp) file.  The interface and implementation code have been combined in one file in order to make it easier with which to study and work.

4.   The implementation scheme for this list will be a linked list, defined in the private section.  The linked list manipulations will involve the traditional algorithms you learned in the lessons on linked lists.  Two private variables will be maintained:  pointers to the first (front) and last (tail) nodes in a linked list.  New values will be added to the tail of the list.

5.   The additional syntax required to implement a templated class shows up in two key locations.  Before the definition section of the class we need to add the templated data type.

template <class itemType>

class list

{

        public:

                ... more code ...

        private:

                ... more code ...

}

      This instructs the compiler to allow list to work with data of type itemType.  If itemType is declared as an int, then the list class will store integers.  If itemType is declared as char, then the list class will store characters.

      Second, the implementation of each member function must be preceded with extra code.  Here is the implementation of the default constructor.

template <class itemType>  // same as the line before class definition

list <itemType>:: list()         // need to add <itemType> to list::list()

{

        myFront = NULL;

}

6.   To use this new abstraction of a list ADT, we must include the data type when the list is declared.  This syntax is similar to declaring an apvector, apmatrix, or apstack.  Here is a sample program which uses the list abstraction.

      Program 41-1

#include <iostream.h>

#include <list.h>

main()

{

        list<int>  sampleList;  //  you must specify <data type>

        int  k;

        for (k=1; k<=5; k++)

                sampleList.insert (k);

        sampleList.print();

        return 0;

}

   Run output:

   1  2  3  4  5

7.   When a list object is declared, the programmer must include a data type within the angle brackets.  This data type must satisfy two preconditions:  it must support a default constructor and its assignment operation (=) must be overloaded correctly.

8.   The insert, print, and length member functions are standard linked-list algorithms.  The difference is that you must code the algorithms to work with the private myFront and myTail   pointers as the front and tail of the list.  The algorithms for insert, print and length are left for your review and study in H.A.41.1.

C.  Overloading the List Assignment Operator

1.   It would be valuable to support an assignment operator for the list class.  This would allow statements such as  list2 = list1  which makes list2 as an identical copy of list1.  Note that this is different from making list1 and list2 point to the same list.  Each list variable will point to a separate list of memory locations.

2.   The code must deal with some special cases which could occur:

      list1 = list1;          

            // this is useless code, but list1 should not change

      list3 = list2 = list1;

            // we should support chaining

      list1.clear();

      list2 = list1;

            // watch out for the empty list case

      ... code to insert 5 values into list1 ...

      ... code to insert 5 values into list2 ...

      list1 = list2;

            //    we need to delete the old list1 before we give it a copy of list2      

3.   We begin our study of the overloaded list operator= by breaking down the parameter list.

template<class itemType>

const list&

list<itemType>::operator= (const list &otherList)

a.   The member function is ready to deal with lists of itemType, where itemType is a parameter for some data type.

b.   The function will return a const reference parameter.  This return type allows for chaining and protects the returned list from any changes.  For example in the chained expression:

        list3 = list2 = list1;

      the statement is processed from right to left.  The first operation solved is list2 = list1, which then returns list2.  Because the return value of list2 is a const reference parameter we avoid making a copy of list2 and we protect it from any changes.  The object list2 is then assigned to list3.

c.   This member function will create a duplicate of the parameter otherList and eventually have the private variables myFront and myTail point to this new duplicate list.    

4.   The code  list1 = list1  is dealt with by the first if statement

if (this != &otherList)

      which should result in no changes to list1.  If the destination object is the same of the object being copied, no changes should be made.

5.   The code inside the if block can be summarized in three sections.

if (this != &otherList)

{

        clear the list

        get new list started, copy first node

        copy rest of nodes

}

6.   To clear the existing list we simply call the member function clear.

clear ();

      A member function can solve problems regarding the object "self" by calling other member functions which have already been implemented.

7.   The code:

temp = otherList.myFront;

if (temp != NULL)

{

        myFront = myTail = new listNode (temp->myItem);

        temp = temp->next;

}

      gets the new list started by using the struct constructor.  The pointers myFront and myTail will point to the first node of the growing list. The pointer temp is used to traverse the old list (otherList) and myTail is used to point to the last node of the new growing list.

8.   The code:

while (temp != NULL)

{

        myTail->next = new listNode (temp->myItem);

        myTail = myTail->next;

        temp = temp->next;

}

      completes the copying of the list.

D.  The List class Copy Constructor and Destructor

1.   Suppose we had this function which receives a value parameter.

void  doSomething (list<int> tempList)

{

        tempList.print();

}

2.   When this function is called, the copy constructor is invoked and tempList becomes a copy of whatever list was passed to this function.  If we had not explicitly overloaded the = operator, the value tempList would be a pointer to the same list which was passed to this function.  By supporting a copy constructor we get the expected action of a value parameter.  The local list tempList is a value parameter which means it is a entire copy of the list which was passed. 

3.   Notice that the copy constructor is solved by calling the assignment operator.

4.   When this function terminates, the list object tempList is destroyed and the class destructor is invoked.  The class destructor consists of a single call to the already defined clear function.  All the memory used in the linked list is recovered.

5.   It should be noted that when a function terminates, all local variables are destroyed -  including private data members of any objects.  If the class destructor was not implemented in the list class, the private data members myFront and myTail of object tempList would still be destroyed.  We lose the pointers to the linked list, but the rest of the list is still resident in memory!  C++ will take care of eliminating any private variables inside of class objects, but the class destructor must take care of any dynamically allocated memory which is no longer needed.

SUMMARY/REVIEW:         The ability to create an alias for a data type is a great method for making code reusable and extensible.  We will now revisit the apstack class and change the implementation scheme to a linked list

ASSIGNMENT:                   Lab Exercise, L.A.41.1, Newstack.

1.   Your assignment in this lab exercise is to modify the implementation of the apstack class while leaving the interface the same.  Depending on your instructor you may separate the interface (apstack.h) and implementation files (apstack.cpp) or you can combine the two into one file.  You should name these files with the designation "newstack.h" and "newstack.cpp".

2.   In the class definition in the original apstack.h file, the name of the class is apstack.  Do not change this identifier.  However you are to change the implementation from an apvector to a linked list.  By leaving the identifier apstack the client program in the lab exercise of Lesson 39 will not change except to #include <newstack.h>.

3.   As you develop the member functions in your new apstack, test each with appropriate data to make sure they work correctly. 

4.   After you have tested your new apstack class, make the appropriate system changes to use the new apstack to test the non-recursive inorder algorithm from Lesson 40.  You should only have to make one change in your treeStack.cpp program; #include <apstack.h> will change to #include <newstack.h>.  System changes will include helping the compiler know where you have saved the new newstack.h file.

5.   In the original apstack implementation, it is an error to pop an empty stack.  You should maintain the error-checking by calling abort if pop is called on an empty stack.