Back to July Calendar

Templates and inheritance is where I left off yesterday.

Templates and inheritance relate in several ways:

A class template can be derived from a class-template specialization.
A class template can be derived from a non-template class.
A class-template specialization can be derived from a class-template specialization.
A non-template class can be derived from a class-template specialization.

Why do I feel like this is more information than one might be expected to need?

What about templates and friends? Ack! I tend to think that one could just move on to study use of the STL and that these details are more about how the STL is built...but let's look under the hood a bit more.

Recall that a friend function of a class is defined outside the class's scope and yet can access non-public members of the class. You can also have an entire class as the friend of another class. The way a class grants access to friend functions is to include a prototype declaration in the class definition preceded by the keyword friend. To make all member functions of class ClassTwo as friends of class ClassOne, place a declaration of the form friend class ClassTwo in the definition of class ClassOne.

According to Deitel, "Functions and classes can be declared as friends of non-template classes. With class templates, friendship can be established between a class template and a global function, a member function of another class (possibly a class-template specialization), or even an entire class (possibly a class-template specialization). The notations required to establish these friendship relationships can be cumbersome." That's for sure!

Inside a class template for class X that has been declared with

template< class T > class X

a friendship declaration of the form

friend void f1();

makes function f1 a friend of every class-template specialization instantiated from the preceding class template.

Inside a class template for class X that has been declared as above, a friendship declaration of the form

friend void f2(X<T> &);

for a particular type T such as float makes function f2( X<float> & ) a friend of only class-template specialization X<float>.

Inside a class template, you can declare that a member function of another class is a friend of any class-template specialization generated from the class template. Name the member function of the other class, using the class name and the binary scope-resolution operator. For example, inside a class template for class X that has been declared as above, a friendship declaration of the form

friend void A::f4();

makes member function f4 of class A a friend of every class-template specialization instantiated from the preceding class template.

Inside a class template for class X that has been declared as above, a friendship declaration of the form

friend void C<T>::f5( X<T> & );

for a particular type T such as float makes member function

C<float>::f5( X<float> & )

a friend function of only class-template specialization X< float >

Inside a class template for class X that has been declared as above, a second class Y can be declared with

friend class Y;

making every member function of class Y a friend of every class-template specialization produced from the class template X.

Inside a class template for class X that has been declared as above, a second class Z can be declared with

friend class Z<T>;

Then, when a class-template specialization is instantiated with a particular type for T (such as float), all members of class Z<float> become friends of class-template specialization X<float>. We use this particular relationship in several examples of Chapter 17, Data Structures.

Fixed-size data structures such as single-subscripted arrays, double-subscripted arrays and structs, are often not sufficient to the job: such as the math parser I'm trying to put together. Dynamic data structures like linked lists grow and shrink during execution. Data items are “lined up in a chain”—insertions and removals can be made anywhere. Insertions and removals in a stack structure are made only at the top. This is the LIFO, or "last in first out" structure. Queues represent like supermarket lines with a LILO, "last in last out" structure. Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, representation of file system directories and compilation of expressions into machine language.

To prepare for reading Chapter 21 of Deitel where the Standard Template Library (STL) is the focus of study, it helps to have a good handle on these data structures. The STL provides containers and iterators for traversing those containers and algorithms for processing the elements of those containers. STL has taken the data structures mentioned above and packaged them into template classes. The STL code is carefully written to be portable, efficient and extensible. To use the prepackaged data structures, iterators and algorithms in the STL, it really helps to grasp the principles and construction of data structures, so let's do!

Programs implementing data structures in C++ are especially heavy on pointer manipulation. This kind of makes me cringe, because I have never much liked pointers and I know that other languages such as Java and Ruby and Python are built from the bottom up as pointer free object oriented languages. Nonetheless, I plunge ahead.

The Deitel chapter 17 exercise entitled “Building Your Own Compiler” looks as though it may help in the construction of a parser. Let's see. The idea is to write a program that will read a file of statements (read, tokens in a math expression?) written in a simple, yet powerful, high-level language similar to early versions of BASIC and translate these statements into a file of Simpletron Machine Language (SML) instructions (read, post fix notation?) The Simpletron Simulator program should execute the SML program produced by the hand hewn compiler!

A self-referential class contains a pointer member that points to a class object of the same class type. For example, the definition

class Node { 


public:
   Node( int );
   void setData( int );
   int getData() const;      
   void setNextPtr( Node * );
   Node *getNextPtr() const;


private:
   int data;
   Node *nextPtr;

}; // end class Node

defines a type, Node, with two private data members—integer member data and pointer member nextPtr. Member nextPtr points to an object of type Node—another object of the same type as the one being declared here, hence the term “self-referential class.” Member nextPtr is referred to as a link—i.e., nextPtr can be used to “tie” one Node to another Node. Type Node also has five member functions—a constructor that receives an integer to initialize member data, a setData function to set the value of member data, a getData function to return the value of member data, a setNextPtr function to set the value of member nextPtr and a getNextPtr function to return the value of member nextPtr.

Self-referential class objects are linked together to form data structures such as lists, queues, stacks and trees. The null (0) pointer is placed in the link member of the last, or any terminal self-referential class object to indicate that the link does not point to another object.

Working dynamic data structures requires the dreaded malloc: new and delete, in the modern parlance. The limit for dynamic memory allocation can be as large as the amount of available physical memory in the computer or the amount of available virtual memory in a virtual memory system. Often, the limits are much smaller because available memory must be shared among many programs.

For example, the statement

Node *newPtr = new Node( 10 );

allocates sizeof(Node) bytes, runs the Node constructor and stores a pointer to this memory in newPtr. If no memory is available, new throws a bad_alloc exception (yikes!). The node’s data is initialized by its constructor to 10.

The statement below will free this dynamically allocated memory:

delete newPtr;

Failing to free the dynamically allocated data can cause system failure through the dreaded "memory leak."

A linked list is a linear collection of self-referential class objects. The linked list is accessed via a pointer to the first node and subsequent nodes via the link-pointer member stored in each node. A node can contain data of any type, including objects of other classes. If nodes contain base-class pointers or base-class references to base-class and derived-class objects related by inheritance, we can have a linked list of such nodes and use virtual function calls to process these objects polymorphically. Stacks and queues are also linear data structures and are constrained versions of linked lists. Trees are nonlinear data structures.

Linked lists can be maintained in sorted order by inserting each new element at the proper point in the list. Existing list elements do not need to be moved. This may be partly because, unlike arrays elements, linked list nodes are normally not necessarily stored contiguously in memory.

The program listing of listNode.h, list.h and the implementation below (from Deitel) uses a List class template to manipulate a list of integer values and a list of floating-point values. The driver program provides five options:

1) Insert a value at the beginning of the list,
2) insert a value at the end of the list,
3) delete a value from the front of the list,
4) delete a value from the end of the list and
5) terminate the list processing.

The private members of the List class template are firstPtr and lastPtr (pointers to those ListNode elements of a List). The default constructor initializes these to 0 (null) and the destructor ensures that all ListNode objects in a List object are destroyed when that List object is destroyed. The primary List functions are insertAtFront, insertAtBack, removeFromFront and removeFromBack.

Function isEmpty is called a predicate function—it doesn't alter a List; rather, it determines whether the List is empty (i.e., the pointer to the first node of the List is null) and returns a bool. Function print displays a List’s contents. Utility function getNewNode returns a dynamically allocated ListNode object. This function is called from functions insertAtFront and insertAtBack.

The driver program uses function template testList to enable the user to manipulate objects of class List. Lines 81 and 85 create List objects for types int and double, respectively. Lines 82 and 86 invoke the testList function template with these List objects.

Function insertAtFront places a new node at the front of the list. The function consists of several steps:

Call function getNewNode, passing it a constant reference to the node value, value, to be inserted.
Function getNewNode uses operator new to create a new list node and return a pointer to this newly allocated node, which is assigned to newPtr in insertAtFront.
If the list is empty, then both firstPtr and lastPtr are set to newPtr.
If the list is not empty, then the node pointed to by newPtr is threaded into the list by copying firstPtr to newPtr->nextPtr so that the new node points to what used to be the first node of the list and copying newPtr to firstPtr so that firstPtr now points to the new first node of the list.

The before and after insertAtFront lists are illustrated below. The top part of the figure shows the list and the new node before the insertAtFront operation. The dotted arrows in bottom part illustrate the steps 2 and 3 of the insertAtFront operation that enable the node containing 12 to become the new list front.

Function insertAtBack places a new node at the back of the list. The function consists of several steps:

Call function getNewNode, passing it a constant reference to the node value, value, to be inserted.
Function getNewNode uses operator new to create a new list node and return a pointer to this newly allocated node, which is assigned to newPtr in insertAtBack.
If the list is empty, then both firstPtr and lastPtr are set to newPtr.
If the list is not empty, then the node pointed to by newPtr is threaded into the list by copying newPtr to lastPtr->nextPtr so that the new node is pointed to by what used to be the last node of the list and copying newPtr to lastPtr so that lastPtr now points to the new last node of the list.

Function removeFromFront consists of several steps:

Assign tempPtr the address to which firstPtr points. Eventually, tempPtr will be used to delete the node being removed.
If firstPtr is equal to lastPtr, i.e., if the list has only one element prior to the removal attempt, then set firstPtr and lastPtr to zero to dethread that node from the list (leaving the list empty).
If the list has more than one node prior to removal, then leave lastPtr as is and set firstPtr to firstPtr->nextPtr, i.e., modify firstPtr to point to what was the second node prior to removal (and is the new first node now).
After all these pointer manipulations are complete, copy to reference parameter value the data member of the node being removed.
Now delete the node pointed to by tempPtr.
Return true, indicating successful removal.

Function removeFromBack consists of several steps:

Assign tempPtr the address to which lastPtr points. Eventually, tempPtr will be used to delete the node being removed.
If firstPtr is equal to lastPtr, i.e., if the list has only one element prior to the removal attempt, then set firstPtr and lastPtr to zero (line 138) to dethread that node from the list (leaving the list empty).
If the list has more than one node prior to removal, then assign currentPtr the address to which firstPtr points (line 140).
Now “walk the list” with currentPtr until it points to the node before the last node. This is done with a while loop that keeps replacing currentPtr by currentPtr->nextPtr, while currentPtr->nextPtr is not lastPtr.
Assign lastPtr to the address to which currentPtr points to dethread the back node from the list.
Set currentPtr->nextPtr to zero in the new last node of the list
After all the pointer manipulations are complete, copy to reference parameter value the data member of the node being removed.
Now delete the node pointed to by tempPtr.
Return true, indicating successful removal.

Wow, pretty deadly, huh?

Function print prints the data in the list or "The list is empty". The function initializes currentPtr as a copy of firstPtr, then prints the string "The list is: " While currentPtr is not null, currentPtr->data is printed and currentPtr is assigned the value of currentPtr->nextPtr. Note that if the link in the last node of the list is not null, the printing algorithm will erroneously print past the end of the list. The printing algorithm is identical for linked lists, stacks and queues.

// Fig. 17.3: listnode.h
// Template ListNode class definition.
#ifndef LISTNODE_H
#define LISTNODE_H

// forward declaration of class List
template< class NODETYPE > class List;

template< class NODETYPE>
class ListNode {
    friend class List< NODETYPE >; // make List a friend
    public:
       ListNode( const NODETYPE & ); // constructor
       NODETYPE getData() const;      // return data in node

    private:
       NODETYPE data;                // data
       ListNode< NODETYPE > *nextPtr; // next node in list

}; // end class ListNode


// constructor
template< class NODETYPE>
ListNode< NODETYPE >::ListNode( const NODETYPE &info )
   : data( info ),
     nextPtr( 0 )
{
   // empty body
} // end ListNode constructor
// return copy of data in node
template< class NODETYPE >
NODETYPE ListNode< NODETYPE >::getData() const
{
   return data;
} // end function getData
#endif

// Fig. 17.4: list.h
// Template List class definition.
#ifndef LIST_H
#define LIST_H
#include <iostream>
using std::cout;
#include <new>
#include "listnode.h" // ListNode class definition
template< class NODETYPE >
class List {
public:
    List();      // constructor
    ~List();     // destructor
    void insertAtFront( const NODETYPE & );
    void insertAtBack( const NODETYPE & );
    bool removeFromFront( NODETYPE & );
    bool removeFromBack( NODETYPE & );
    bool isEmpty() const;
    void print() const;
private:
    ListNode< NODETYPE > *firstPtr; // pointer to first node
    ListNode< NODETYPE > *lastPtr;   // pointer to last node
    // utility function to allocate new node
    ListNode< NODETYPE > *getNewNode( const NODETYPE & );
}; // end class List

// default constructor
template< class NODETYPE >
List< NODETYPE >::List()
   : firstPtr( 0 ),
     lastPtr( 0 )
{
   // empty body
} // end List constructor

// destructor
template< class NODETYPE >
List< NODETYPE >::~List()
{
   if ( !isEmpty() ) {   // List is not empty
      cout << "Destroying nodes ...\n";
      ListNode< NODETYPE > *currentPtr = firstPtr;
      ListNode< NODETYPE > *tempPtr;
      while ( currentPtr != 0 ) { // delete remaining nodes
         tempPtr = currentPtr;
         cout << tempPtr->data << '\n';
         currentPtr = currentPtr->nextPtr;
         delete tempPtr;
      } // end while
   } // end if
   cout << "All nodes destroyed\n\n";
} // end List destructor

// insert node at front of list
template< class NODETYPE >
void List< NODETYPE >::insertAtFront( const NODETYPE &value )
{
   ListNode< NODETYPE > *newPtr = getNewNode( value );
   if ( isEmpty() ) // List is empty
      firstPtr = lastPtr = newPtr;
   else { // List is not empty
      newPtr->nextPtr = firstPtr;
      firstPtr = newPtr;
   } // end else
} // end function insertAtFront

// insert node at back of list
template< class NODETYPE >
void List< NODETYPE >::insertAtBack( const NODETYPE &value )
{
   ListNode< NODETYPE > *newPtr = getNewNode( value );
   if ( isEmpty() ) // List is empty
      firstPtr = lastPtr = newPtr;
   else { // List is not empty
      lastPtr->nextPtr = newPtr;
      lastPtr = newPtr;
   } // end else
} // end function insertAtBack

// delete node from front of list
template< class NODETYPE >
bool List< NODETYPE >::removeFromFront( NODETYPE &value )
{
   if ( isEmpty() ) // List is empty
     return false; // delete unsuccessful
   else {
      ListNode< NODETYPE > *tempPtr = firstPtr;
      if ( firstPtr == lastPtr )
         firstPtr = lastPtr = 0;
      else
         firstPtr = firstPtr->nextPtr;
      value = tempPtr->data; // data being removed
      delete tempPtr;
      return true; // delete successful
   } // end else
} // end function removeFromFront

// delete node from back of list
template< class NODETYPE >
bool List< NODETYPE >::removeFromBack( NODETYPE &value )
{
   if ( isEmpty() )
      return false; // delete unsuccessful
   else {
      ListNode< NODETYPE > *tempPtr = lastPtr;
      if ( firstPtr == lastPtr )
         firstPtr = lastPtr = 0;
      else {
         ListNode< NODETYPE > *currentPtr = firstPtr;
         // locate second-to-last element
         while ( currentPtr->nextPtr != lastPtr )
            currentPtr = currentPtr->nextPtr;
         lastPtr = currentPtr;
         currentPtr->nextPtr = 0;
      } // end else
      value = tempPtr->data;
      delete tempPtr;
      return true; // delete successful
   } // end else
} // end function removeFromBack

// is List empty?
template< class NODETYPE >
bool List< NODETYPE >::isEmpty() const
{
return firstPtr == 0;
} // end function isEmpty

// return pointer to newly allocated node
template< class NODETYPE >
ListNode< NODETYPE > *List< NODETYPE >::getNewNode(
   const NODETYPE &value )
{
   return new ListNode< NODETYPE >( value );
} // end function getNewNode

// display contents of List
template< class NODETYPE >
void List< NODETYPE >::print() const
{
   if ( isEmpty() ) {
      cout << "The list is empty\n\n";
      return;
   } // end if
   ListNode< NODETYPE > *currentPtr = firstPtr;
   cout << "The list is: ";
   while ( currentPtr != 0 ) {
      cout << currentPtr->data << ' ';
      currentPtr = currentPtr->nextPtr;
   } // end while
   cout << "\n\n";
} // end function print
#endif

-----------------------------

1 // Fig. 17.5: fig17_05.cpp
2 // List class test program.
3 #include <iostream>
4
5 using std::cin;
6 using std::endl;
7
8 #include <string>
9
10 using std::string;
11
12 #include "list.h" // List class definition
13
14 // function to test a List
15 template< class T >
16 void testList( List< T > &listObject, const string &typeName )
17 {
18    cout << "Testing a List of " << typeName << " values\n";
19
20    instructions(); // display instructions
21
22 int choice;
23    T value;
24
25    do {
26       cout << "? ";
27       cin >> choice;
28
29       switch ( choice ) {
30          case 1:
31             cout << "Enter " << typeName << ": ";
32             cin >> value;
33             listObject.insertAtFront( value );
34             listObject.print();
35             break;
36
37          case 2:
38             cout << "Enter " << typeName << ": ";
39             cin >> value;
40             listObject.insertAtBack( value );
41             listObject.print();
42             break;
43
44          case 3:
45             if ( listObject.removeFromFront( value ) )
46                cout << value << " removed from list\n";
47
48             listObject.print();
49             break;
50
51          case 4:
52             if ( listObject.removeFromBack( value ) )
53                cout << value << " removed from list\n";
54
55             listObject.print();
56             break;
57
58       } // end switch
59
60    } while ( choice != 5 ); // end do/while
61
62    cout << "End list test\n\n";
63
64 } // end function testList
65
66 // display program instructions to user
67 void instructions()
68 {
69    cout << "Enter one of the following:\n"
70         << " 1 to insert at beginning of list\n"
71         << " 2 to insert at end of list\n"
72         << " 3 to delete from beginning of list\n"
73         << " 4 to delete from end of list\n"
74         << " 5 to end list processing\n";
75
76 } // end function instructions
77
78 int main()
79 {
80    // test List of int values
81    List< int > integerList;
82    testList( integerList, "integer" );
83
84    // test List of double values
85    List< double > doubleList;
86    testList( doubleList, "double" );
87
88    return 0;
89
90 } // end main

Here is some output:

Testing a List of integer values
Enter one of the following:
1 to insert at beginning of list
2 to insert at end of list
3 to delete from beginning of list
4 to delete from end of list
5 to end list processing
? 1
Enter integer: 111
The list is: 111

? 1
Enter integer: 222
The list is: 222 111

? 2
Enter integer: 000
The list is: 222 111 0

? 2
Enter integer: 99
The list is: 222 111 0 99

? 4
99 removed from list
The list is: 222 111 0

? 3
222 removed from list
The list is: 111 0

? 3
111 removed from list
The list is: 0

? 2
Enter integer: 1
The list is: 0 1

? 2
Enter integer: 2
The list is: 0 1 2

? 2
Enter integer: 3
The list is: 0 1 2 3

? 5
End list test

Testing a List of double values
Enter one of the following:
1 to insert at beginning of list
2 to insert at end of list
3 to delete from beginning of list
4 to delete from end of list
5 to end list processing
? 1.088
Enter double: The list is: 0.088

? 2
Enter double: .099
The list is: 0.088 0.099

? 1.1e-1
Enter double: The list is: 0.01 0.088 0.099

? 2
Enter double: 2.28-1
The list is: 0.01 0.088 0.099 2.28

? ? 2
Enter double: 2.29e-1
The list is: 0.01 0.088 0.099 2.28 0.229

? 4
0.229 removed from list
The list is: 0.01 0.088 0.099 2.28

? 4
2.28 removed from list
The list is: 0.01 0.088 0.099

? 4
0.099 removed from list
The list is: 0.01 0.088

? 4
0.088 removed from list
The list is: 0.01

? 4
0.01 removed from list
The list is empty

?