This particular page contains materials from the second of the two chapters that introduce the C++ class concept. This second chapter, "Intermediate class" covers a number of topics including operator functions, friend relations, resource management, and an introduction to inheritance. The content material here comes from a subsection on "iterators" for "collection classes" (illustrate design ideas as well as being good examples of use of friend relationships).

23 Intermediate class

"static" class members for shared data

Section 23.1 looks at the problem of data that need to be shared by all instances of a class. Shared data are quite common. For example, the air traffic control program in Chapter 20 had a minimum height for the aircraft defined by a constant; but it might be reasonable to have the minimum height defined by a variable (at certain times of the day, planes might be required to make their approaches to the auto lander somewhat higher say 1000 feet instead of 600 feet). The minimum height would then have to be a variable. Obviously, all the aircraft are subject to the same height restriction and so need to have access to the same variable. The minimum height variable could be made a global; but that doesn't reflect its use. If really is something that belongs to the aircraft and so should somehow belong to class Aircraft. C++ classes have "static" members; these let programmers define such shared data.

Friends - sneaking through the walls of privacy

Section 23.2 introduces "friends". One of the motivations for classes was the need to build privacy walls around data and specialist housekeeping functions. Such walls prevent misuse of data such as can occur with simple structs that are universally accessible. Private data and functions can only be used within the member functions of the class. But sometimes you want to slightly relax the protection. You want private data and functions to be used within member functions, and in addition in a few other functions that are explicitly named. These additional functions may be global functions, or they may be the member functions of some second class. Such functions are nominated as "friends" in a class declaration. (The author of a class nominates the friends if any. You can't come along later and try to make some new function a "friend" of an existing class because, obviously, this would totally defeat the security mechanisms.) There aren't many places where you need friend functions. They sometimes appear when you have a cluster of separate classes whose instances need to work together closely. Then you may get situations where there a class has some data members or functions that you would like to make accessible to instances of other members of the class cluster without also making them accessible to general clients.

Iterators

Section 23.3 introduces iterators. Iterator classes are associated with collection classes like those presented in Chapter 21. An Iterator is very likely to be a "friend" of the collection class with which it is associated. Iterators help you organize code where you want to go through a collection looking at each stored item in turn.

Operator functions

My own view is that for the most part "operator functions", the topic of Section 23.4, are an overrated cosmetic change to the ordinary function call syntax. Remember how class Number in Chapter 19 had functions like Multiply() (so the code had things like a.Multiply(b) with a and b instances of class Number)? With operator functions, you can make that a * b. Redefining the meaning of operator * allows you to pretty up such code.

Such cosmetic uses aren't that important. But there are a few cases where it is useful to redefine operators. For instance, you often want to extend the interface to the iostream library so that you can write code like Number x; ... cout << "x = " << x << endl. This can be done by defining a new global function involving the << operator. Another special case is the assignment operator, operator =; redefinition of operator = is explained in the next section on resource manager classes. Other operators that you may need to change are the pointer dereference operator, -> and the new operator. However, the need to redefine the meanings of these operators only occurs in more advanced work, so you wont see examples in this text.

Resource manager classes

Instances of simple classes, like class Number, class Queue, class Aircraft are all represented by a single block of data. But there are classes where the instances own other data structures (or, more generally, other resources such as open files, network connections and so forth). Class DynamicArray is an example; it owns that separately allocated array of void* pointers. Classes List and BinaryTree also own resources; after all, they really should be responsible for those listcells and treenodes that they create in the heap.

Destructor functions for resource manager classes

Resource managers have special responsibilities. They should make certain that any resources that they claim get released when no longer required. This requirement necessitates a new kind of function - a "destructor". A destructor is a kind of counterpart for the constructor. A constructor function initializes an object (possibly claiming some resources, though usually additional resources are claimed later in the object's life). A destructor allows an object to tidy up and get rid of resources before it is itself discarded. The C++ compiler arranges for calls to be made to the appropriate destructor function whenever an object gets destroyed. (Dynamic objects are destroyed when you apply operator delete; automatic objects are destroyed on exit from function; and static objects are destroyed during "at_exit" processing that takes place after return from main().)

Operator = and resource manager classes

There is another problem with resource manager classes - assignment. The normal meaning of assignment for a struct or class instance is "copy the bytes". Now the bytes in a resource manager will include pointers to managed data structures. If you just copy the bytes, you will get two instances of the resource manager class that both have pointers to the same managed data structure. Assignment causes sharing. This is very rarely what you would want.

If assignment is meaningful for a resource manager, its interpretation is usually "give me a copy just like this existing X"; and that means making copies of any managed resources. The C++ compiler can not identify the managed resources. So if you want assignment to involve copying resources, you have to write a function does this. This becomes the "assignment function" or "operator=()" function. You also have to write a special "copy constructor".

Preventing assignment

Actually, you usually want to say "instances of this resource manager class cannot be assigned". Despite examples in text books, there are very few situations in real programs where you want to say something like "give me a binary tree like this existing binary tree". There are mechanisms that allow you to impose constraints that prohibit assignment.

Inheritance

The final section of this chapter introduces the idea of inheritance. Basically, inheritance allows you to define a new class that in some way extends an existing defined class. There are several different uses for inheritance and the implications of inheritance are the main topic of Part V of this text.

Although your program may involve many different kinds of object, there are often similarities among classes. Sometimes, it is possible to exploit such similarities to simplify the overall design of a program. An example like this is used to motivate the use of class hierarchies where specialized classes inherit behaviours from more general abstract classes.

The next subsection shows how class hierarchies can be defined in C++ and explains the meanings of terms like "virtual function". Other subsections provide a brief guide to how programs using class hierarchies actually work and cover some uses of multiple inheritance.

23.3 Iterators

DynamicArray	d1;
...
...
for(int i = 1; i < d1.Length(); i++) {
	Thing* t = (Thing*) d1.Nth(i);
	t->DoSomething();
	...
	}

The PrintOn() function for BinaryTree involved a "traversal" that in effect iterated though each data item stored in the tree (starting with the highest key and working steadily to the item with the lowest key). However the BinaryTree class didn't provide any general mechanism for accessing the stored elements in sequence.

Mechanisms for visiting each data element in turn could have been incorporated in the classes. The omission was deliberate.

Increasingly, program designers are trying to generalize, they are trying to find mechanisms that apply to many different problems. General approaches have been proposed for working through collections.

The basic idea is to have an "Iterator" associated with the collection (each collection has a specialized form of Iterator as illustrated below). An Iterator is in itself a simple class. Its public interface would be something like the following (function names may differ and there may be slight variations in functionality):

class Iterator {
public:
	Iterator(...);
	void	First(void);
	void	Next(void);
	int	IsDone(void);
	void	*CurrentItem(void);
private:
	...
};

Collection	c1;
...
Iterator	i1(c1);
i1.Start();
while(!i1.IsDone()) {
	Thing* t = (Thing*) i1.CurrentItem();
	t->DoSomething();
	...;
	i1.Next();
	}

An "abstract base class" for Iterators?

As explained in the final section of this chapter, it is possible to start by giving an abstract definition of an iterator as a "pure abstract class", and then define derived subclasses that represent specialized iterators for different types of collection. Here, we won't bother to define the general abstraction, and will just define and use examples of specialized classes for the different collections.

Insecure iterators

The iterators illustrated here are "insecure". If a collection gets changed while an iterator is working, things can go wrong. (There is an analogy between an iterator walking along a list and a person using stepping stones to cross a river. The iterator moves from listcell to listcell in response to Next() requests; it is like a person stepping onto the next stone and stopping after each step. Removal of the listcell where the iterator is standing has an effect similar to magically removing a stepping stone from under the feet of the river crosser.) There are ways of making iterators secure, but they are too complex for this introductory treatment.

23.3.1 ListIterator

Consequently, adding an iterator for class List requires only modification of the header file:

#ifndef __MYLIST__
#define __MYLIST__

class ListIterator;

class List {
public:
	List();
	
	int		Length(void) const;
	...
	friend class ListIterator;
private:
	struct ListCell { void *fData; ListCell *fNext; };
	ListCell *Head(void) const;
	
	int		fNum;
	ListCell	*fHead;
	ListCell	*fTail;	
};

class ListIterator {
public:
	ListIterator(List *l);
	void	First(void);
	void	Next(void);
	int	IsDone(void);
	void	*CurrentItem(void);
private:
	List::ListCell *fPos;
	List		*fList;
};

inline int List::Length(void) const { return fNum; }
inline List::ListCell *List::Head() const { return fHead; }

inline ListIterator::ListIterator(List *l) 
	{ fList = l; fPos = fList->Head(); }
inline void ListIterator::First(void) { fPos = fList->Head(); }
inline void ListIterator::Next(void) 
	{ if(fPos != NULL) fPos = fPos->fNext; }
inline int ListIterator::IsDone(void) { return (fPos == NULL); }
inline void *ListIterator::CurrentItem(void) 
	{ if(fPos == NULL) return NULL; else return fPos->fData; }
#endif

Friend nomination

There are several points to note in this header file. Class List nominates class ListIterator as a friend; this means that in the code of class ListIterator, there can be statements involving access to private data and functions of class List.

Access function List::Head()

Here, an extra function is defined - List::Head(). This function is private and therefore only useable in class List and its friends (this prevents clients from getting at the head pointer to the chain of listcells). Although, as a friend, a ListIterator can directly access the fHead data member, it is still preferable that it use a function style interface. You don't really want friends becoming too intimate for that makes it difficult to locate problems if something goes wrong.

Declaration of ListIterator class

The class declaration for ListIterator is straightforward except for the type of its fPos pointer. This is a pointer to a ListCell. But the struct ListCell is defined within class List. If, as here, you want to refer to this data type in code outside of that of class List, you must give its full type name. This is a ListCell as defined by class List. Hence, the correct type name is List::ListCell.

Implementation of ListIterator

The member functions for class ListIterator are all simple. The constructor keeps a pointer to the List that it is to work with, and initializes the fPos pointer to the first listcell in the list. Member function First() resets the pointer (useful if you want the iterator to run through the list more than once); Next() advances the pointer; CurrentItem() returns the data pointer from the current listcell; and IsDone() checks whether the fPos pointer has advanced off the end of the list and become NULL. (The code for Next() checks to avoid falling over at the end of a list by being told to take the "next" of a NULL pointer. This could only occur if the client program was in error. You might choose to "throw an exception", see Chapter 26, rather than make it a "soft error".)

The test program used to exercise class List and class DynamicArray can be extended to check the implementation of class ListIterator:. It needs a new branch in its switch() statement, one that allows the tester to request that a ListIterator "walk" along the List:

case 'w':
		{
		ListIterator li(&c1);
		li.First();
		cout << "Current collection " << endl;
		while(!li.IsDone()) {
			Book p = (Book) li.CurrentItem();
			cout << p << endl;
			li.Next();
			}
		}
		break;

The statement:

ListIterator li(&c1);

The statement, li.First(), is redundant because the constructor has already performed an equivalent initialization. It is there simply because that is the normal pattern for walking through a collection:

li.First();
while(!li.IsDone()) {
	... li.CurrentItem();
	...
	li.Next();
	}

Note the need for the typecast:

Book p = (Book) li.CurrentItem();

Backwards and forwards iterators in two way lists

Class List is singly linked, it only has "next" pointers in its listcells. This means that it is only practical to "walk forwards" along the list from the head to the tail. If the list class uses listcells with both "next" and "previous" pointers, it is practical to walk the list in either direction. Iterators for doubly linked lists usually take an extra parameter in their constructor; this is a "flag" that indicates whether the iterator is a "forwards iterator" (start at the head and follow the next links) or a "backwards iterator" (start at the tail and follow the previous links).

23.3.2 TreeIterator

An iterator that can "walk" a binary tree is a little more elaborate than that needed for a list. It is easy to descend the links from the root to the leaves of a tree, but there aren't any "back pointers" that you could use to find your way back from a leaf to the root. Consequently, a TreeIterator can't manage simply with a pointer to the current TreeNode, it must also maintain some record of information describing how it reached that TreeNode.

Stack of pointers maintain state of traversal

As illustrated in Figure 23.1, the iterator uses a kind of "stack" of pointers to TreeNodes. In response to a First() request, it chases down the left vine from the root to the left most leaf; so, in the example shown in Figure 23.1 it stacks up pointers to the TreeNodes associated with keys 19, 12, 6.

A CurrentItem() request should return the data item associated with the entry at the top of this stack.

A Next() request has to replace the topmost element by its successor (which might actually already be present in the stack). As illustrated in Figure 23.1, the Next() request applied when the iterator has entries for 19, 12, and 6, should remove the 6 and add entries for 9 and 7.

Figure 23.1 Tree and tree iterator.

A subsequent Next() request removes the 7, leaving 19, 12, and 9 on the stack. Further Next() requests remove entries until the 19 is removed, it has to be replaced with its successor so then the stack is filled up again with entries for 28 and 26.

Representing the stack

The programmer implementing class TreeIterator has to chose how to represent this stack. If you wanted to be really robust, you would use a DynamicArray of TreeNode pointers, this could grow to whatever size was needed. For most practical purposes a fixed size array of pointers will suffice, for instance an array with one hundred elements. The size you need is determined by the maximum depth of the tree and thus depends indirectly on the number of elements stored in the tree. If the tree were balanced, a depth of one hundred would mean that the tree had quite a large number of nodes (something like 299). Most trees are poorly balanced. For example if you inserted 100 data items into a tree in decreasing order of their keys, the left branch would be one hundred deep. Although a fixed array will do, the code needs to check for the array becoming full.

Class BinaryTree has to nominate class TreeIterator as a "friend", and again for style its best to provide a private access function rather than have this friend rummage around in the data:

class BinaryTree
{
public:
	BinaryTree();
	...
	friend class TreeIterator;
private:
	TreeNode	*Root(void);
	...
};

inline TreeNode *BinaryTree::Root(void)  { return fRoot; }

Class TreeIterator has the standard public interface for an iterator; its private data consist of a pointer to the BinaryTree it works with, an integer defining the depth of the "stack", and the array of pointers:

class TreeIterator {
public:
	TreeIterator(BinaryTree *tree);
	void	First(void);
	void	Next(void);
	int	IsDone(void);
	void	*CurrentItem(void);
private:
	int		fDepth;
	TreeNode	*fStack[kITMAXDEPTH];
	BinaryTree	*fTree;
};

The constructor simply initializes the pointer to the tree and the depth counter. This initial value corresponds to the terminated state, as tested by the IsDone() function. For this iterator, a call to First() must be made before use.

TreeIterator::TreeIterator(BinaryTree *tree)
{
	fTree = tree;
	fDepth = -1;
}

int	TreeIterator::IsDone(void)
{
	return (fDepth < 0);
}

Function First() starts at the root and chases left links for as far as it is possible to go; each TreeNode visited during this process gets stacked up. This process gets things set up so that the data item with the smallest key will be the one that gets fetched first.

void TreeIterator::First(void)
{
	fDepth = -1;
	TreeNode *ptr = fTree->Root();
	while(ptr != NULL) {
		fDepth++;
		fStack[fDepth] = ptr;
		ptr = ptr->LeftLink();
		}
}

Data items are obtained from the iterator using CurrentItem(). This function just returns the data pointer from the TreeNode at the top of the stack:

void *TreeIterator::CurrentItem(void)
{
	if(fDepth < 0) return NULL;
	else
	 return fStack[fDepth]->Data();
}

The Next() function has to "pop" the top element (i.e. remove it from the stack) and replace it by its successor. Finding the successor involves going down the right link, and then chasing left links as far as possible. Again, each TreeNode visited during this process gets "pushed" onto the stack. (If there is no right link, the effect of Next() is merely to pop an element from the stack.)

void TreeIterator::Next(void)
{
	if(fDepth < 0) return;
	
	TreeNode *ptr = fStack[fDepth];
	fDepth--;
	ptr = ptr->RightLink();
	while(ptr != NULL) {
		fDepth++;
		fStack[fDepth] = ptr;
		ptr = ptr->LeftLink();
		}
}

Use of the iterator should be tested. An additional command can be added to the test program shown previously:

case 'w':
		{
		TreeIterator ti(&gTree);
		ti.First();
		cout << "Current tree " << endl;
		while(!ti.IsDone()) {
			DataItem *d = (DataItem*) ti.CurrentItem();
			d->PrintOn(cout);
			ti.Next();
			}
		}
		break;