Columns

Stepping Up To C++

Designing Generic Container Classes, Part 1

Dan Saks

Dan Saks is the president of Saks & Associates, which offers consulting and training in C++ and C. He is secretary of the ANSI and ISO C++ committees. Dan is coauthor of C++ Programming Guidelines, and codeveloper of the Plum Hall Validation Suite for C++ (both with Thomas Plum). You can reach him at 393 Leander Dr., Springfield OH, 45504-4906, by phone at (513)324-3601, or electronically at dsaks@wittenberg.edu.

A container (or collection) is a data structure that holds other objects. Containers can be threaded data structures, like lists or trees, or tabular structures like vectors and matrices. More elaborate containers, such as hash tables, use a combination of tabular and threaded structures. Although different types of containers employ different storage and retrieval algorithms, they share many similar design and implementation problems.

All but the simplest C or C++ programs use at least one container. Larger programs typically use an assortment of containers. For example, the cross-reference generator I presented in my two previous articles (which is hardly a large program) uses both a binary tree and linear lists. That program uses the tree to alphabetize the words in the cross-reference, along with one list for each word in the tree to hold the text line numbers on which that word occurred. Some systems use the same type of container for different purposes. For example, an operating system typically uses some queues to hold processes, and other queues to hold messages that are in transit between processes.

Implementing a simple container, such as a queue, for a particular element type is not all that difficult. You can always look up how to do it in any of the numerous books on data structures available today. (In fact, the study of algorithms and data structures is one of the few areas where computing is truly a science rather than a black art.) However, by the time you implement a queue for a third or fourth different element type, you'll probably notice that the source code for all these queues is nearly identical, and that you may be wasting your time as you duplicate both source and object code. It would be nice to avoid that waste and duplication by implementing just one generic queue — a queue that holds elements of any type — and use that queue for all applications.

C++ programmers tried for nearly a decade to write generic container classes using available language features, namely:

Unfortunately, these features cannot do the job satisfactorily. Consequently, Bjarne Stroustrup (the inventor of C++) proposed adding templates to C++ as a better tool for crafting generic container classes. Templates first appeared in commercially-available C++ compilers circa 1991 and are now generally available. Despite the sometimes frustrating dialectic variations across platforms that come with new language features, templates are indeed a better tool for writing generic containers.

Of course, templates are not a panacea, and like most of C++, they aren't fool proof either. You may find that using templates increases compile and link times and produces surprisingly large executables. Fortunately, most of these problems have solutions, and discovering them is what makes life interesting.

However, this series of articles is not just about templates; it's about the issues that arise in designing and implementing generic container classes. Using templates is only part of that picture. Many issues, such as time-space tradeoffs or preserving the abstractness of a container, transcend using templates. In fact, introducing templates into the discussion prematurely only clouds some of these issues.

I've also found that understanding the past attempts to write generic containers without templates provides real insights into what templates can and cannot do for you. The earlier attempts were not total failures. Some of the techniques that evolved in the absence of templates are still useful, and work even better with templates.

Thus, this series of articles presents an evolutionary approach to designing generic container classes. Starting with a rudimentary container class, I'll demonstrate a progression of techniques for repackaging that container as a generic. Each technique yields some useful results, but each also has flaws that motivate the search for improvements. In the end, I hope you'll find some useful insights and techniques that will help you use templates very effectively.

A FIFO Queue

I'll use as my example a simple class that implements a FIFO (first-in-first-out) queue of elements of arbitrary type T. The queue provides the following operations:

As with most containers, the abstract notion of a queue has a variety of implementations. I've chosen a threaded implementation, as illustrated in Figure 1. Each cell object holds a queued element and a pointer to the next cell in the queue. The queue object itself is just a pair of pointers — a pointer to each the first and last cell in the queue.

Throughout, I'll consider two specific applications for the queue:

1. a queue of int (the primitive type)

2. a queue of str (a class for variable-length strings)

Always remember that C++ tries to avoid arbitrary distinctions between user-defined types and built-in types. That is, it offers most of the features you need to fashion user-defined types that look and act very much like built-in types. (These features account for much of the complexity in C++.) Well designed generic containers should work equally well for all types, user-defined as well as pre-defined. Thus, I'll test the generic container against both.

Listing 1 shows the header that defines the first version of class intq, a queue of int. Listing 2 shows intq's non-inline member function definitions.

intq_cell is the auxiliary class for cell objects inside an intq. intq_cell has no public members. The keyword private is actually redundant because all members of a class (declared with the keyword class rather than struct) are private by default. In this case, I think the redundancy adds clarity. The friend declaration in intq_cell does not declare a member and is not subject to access control (declaring it public or private has no effect).

The reason that intq_cell has no public members is so that applications using intq can't access intq_cell directly. An application that includes the intq header adds both intq and intq_cell to its global namespace. But applications should not manipulate intq_cell objects directly because intq_cell is an implementation artifact, not part of the intq interface.

Since it has only private members, intq_cell is essentially unusable to all but its friends. In particular, intq_cell's constructor is private, so applications cannot call it. An application cannot create an intq_cell object directly (such as by a declaration or a new-expression) because that would invoke the intq_cell constructor, which is inaccessible.

The intq class can create and use intq_cell objects because intq_cell declares intq as a friend, which means that every intq member function is a friend of intq_cell. Thus, intq's members can invoke the (private) intq_cell constructor when creating intq_cell objects.

As I explained in an earlier column on nested classes (see "Stepping Up to C++: Nested Classes," CUJ, July 1993), I think nested classes are usually the better way to keep implementation classes like intq_cell out of the application's reach. Using forward-declared nested classes is even better. However, many good C++ programmers and authors still use private contructors and friend declarations. Furthermore, templates and nested classes don't always mesh together well. You may find that private constructors and friend declarations are the best solution to some awkward packaging problems.

Listing 3 shows the header that defines a first version of class strq, a queue of strings. Listing 3 is identical to Listing 1 (which defines class intq) except that Listing 3 uses str instead of int nearly everywhere. The one place where strq does not use str instead of int is in the return type of the remove function. The int return type represents a boolean indicating whether remove successfully removed an element from the queue.

I could have declared the append function in both Listing 1 and Listing 3 with a value parameter, of the form

void append(T e);
rather than with a reference-to-const parameter of the form:

void append(const T &e);
Either way, append has the same outward behavior. Passing by value is probably faster when T is a primitive type like int, and passing by reference may be faster when T is a user-defined type with a constructor and destructor. (Binding a reference to an lvalue avoids creating a temporary which must later be destroyed.) I elected to write both intq and strq in the same style to make it easier to transform both into a single generic. I don't believe the performance penalty for passing an int by reference is much cause for concern in this instance.

Just as strq's header is nearly identical to intq's, so are the corresponding member function definitions. Consequently, I did not list the strq member function definitions. You can produce them by simply replacing all occurrences of int in Listing 2 with str (except for the return type of remove).

The class and inline member function definitions for my variable-length string class appear as str.h in Listing 4, and the corresponding member function definitions appear as str.cpp in Listing 5. A str object stores the text of a string in a character array allocated from the free store, as illustrated in Figure 2. Each str has a data member ptr that holds the address of the first character in the array, and another data member len that holds the length of the string. The text in the array is null terminated, so the length of the string is one less than the length of the array.

Improperly designed containers may work fine when used to hold objects of a primitive type or of a class type with trivial constructors and destructors, but they can fail miserably when used to hold objects with non-trivial constructors and destractors. That's why I chose to test my container with both int (a primitive type) and str (a class with a non-trivial constructor and destractor).

Listing 6 contains a program for testing the queue operations. The program creates an array, q, of four queues, all initially empty. It then repeatedly reads simple commands from the standard input that specify operations on a numbered queue. For example, the command "a 2 xxx" appends a string with the value "xxx" to q[2]. The command "c 1" clears q[1], and "r 0" removes an element from q[0] (if such an element exists). You can rewrite this program to test intqs by simply changing str to int as needed.

The showheap function is a crude tool for monitoring the heap storage. The test program uses showheap to demonstrate that it destroys every object it creates. Strictly speaking, the free store and the heap are logically distinct memory pools. However, most implementations use the heap (managed by malloc and free) as the default free store.

showheap is very platform-specific. Listing 7 shows a version of showheap that conditionally compiles for either the Borland, Microsoft, or Watcom C++ compilers running under MS-DOS.

A First Attempt at a Generic Queue

The initial problem in building a queue for objects of any type is defining a queue cell that can accomodate objects of any type. Thus far, intq and strq copy each queued object into a fixed-type data member of a queue cell. But in a generic queue, a queued object can have any type, and thus any size. Storing objects of any type and size in a fixed-type data member can get pretty awkward. It's much easier to leave the queued objects outside the queue cells and simply store the address of a queued object as a void * element in a queued cell. Figure 3 illustrates the structure of a generic queue using this design.

Listing 8 shows a class definition for genq, a generic queue of void *. genq defines the cell type as a private nested class, thus completely removing the cell type from the global namespace. genq::cell is similar to strq_cell (in Listing 3) except for using void * instead of str as the element data member's type and as the type of the cell constructor's first parameter. Class genq itself is nearly identical to class strq, again except for an occasional void * instead of str.

Listing 9 shows the member function definitions for genq corresponding to the class definition in Listing 8. Most of the function bodies are nearly identical to the corresponding intq functions in Listing 2. The most significant change is the additional statement delete p->element; inside the loop in genq::clear. intq::clear (and strq::clear) need only delete p; to discard the queue cell addressed by p. When the queue object is inside the cell (as the element member), deleting p destroys the queued object as well. Now that the queued object is in separately-allocated storage addressed by p->element. clear must explicitly destroy that object (by deleting
p->element) as well as destroy the queue cell (by deleting p).

Iteration Functions

If this transformation to a generic queue seems too simple, that's because it is. genq::print has a serious problem: it displays the queue elements in the wrong format.

The body of genq::print is a single loop:

for (p = first; p != 0; p = p->next)
   cout << ' ' << p->element;
which visits each cell in a queue and prints the element in the cells. The output statement in the loop body is actually two separate function calls equivalent to

cout << ' ';
cout << p->element;
The first output expression calls ostream::operator<<(char) to display a single space. The second call selects an ostream::operator<< based on the static type of p->element. When p->element is an int (as in intq::print), the output expression 

cout << p->element;
invokes ostream::operator<<(int), which displays p->element in the equivalent of printf's %d format. When p->element is a str (as in strq::clear), the output expression invokes operator<<(ostream &, const str &) defined in str.cpp (Listing 5) , which invokes ostream::operator<<(const char *), which in turn displays
p->element in the equivalent of %s format. But when p->element has type void *, the output expression invokes ostream::operator<<(const void *), which displays the value in p->element (the pointer), not the object its points to. The output appears in the equivalent of %p format, which on most systems is some hexadecimal format.

A generic queue of void * lacks the compile-time type information it needs to print the queued objects in the right format. Since a single copy of genq::print must work for all types of objects, genq::print needs an additional argument that conveys formatting information. Passing a format string, like "%d," might be adequate for queue elements of built-in types, but not for user-defined types, like str or complex. Passing genq::print a pointer to a user-supplied function that "knows" how to print a queued object is a much more general solution.

For example, when using a genq as a queue of int, the application defines a function 

void print_int(void *p)
   {
   cout << ' ' << *(int *)p;
   }
that writes the object addressed by p (assumed to be an int) to cout using ostream::operator<<(int). The application can then print the int objects in queue qi by calling

qi.print(print_int);
which invokes print_int for each element in the queue.

The definition for this new genq::print function is:

void genq::print(void (*f)(void *))
   {
   cell *p = first;
   for (p = first; p != 0; p = p->next)
      (*f)(p->element);
   }
The parameter f has type "pointer to function with parameter void * returning void," which is the same type as print_int above. genq::print simply visits each cell in the queue and applies the function addressed by f to the element in that cell.

As written above, you can use genq::print for more than just printing. genq::print is actually a general-purpose tool for applying any function with the appropriate type to each element in a queue. For example, you can define

static int total = 0;

void sum(void *p)
   {
   total += *(int *)p;
   }
so that

qi.print(sum);
computes the sum of the int values in queue qi.

As such, the name print is really inappropriate. I think apply is a better name. Others prefer the name foreach. (The container classes supplied with Borland C++ 4.0 use foreach.) Whatever its name, a function that applies another function to each object in a container is generally known as an iteration function.

Many Problems Yet to Solve

Listing 10 shows the test program from Listing 6 adapted to test genq (with an iteration function) used as a queue of int. This program shows that this version of genq is not nearly as convenient to use as the single-purpose intq and strq classes.

When using a special-purpose queue (as in Listing 6) , you add element qe to queue q[qn] by simply calling

q[qn].append(qe);
With a generic queue, you must dynamically allocate a copy of the object and pass the address of the copy to the queue, as in

q[qn].append(new int(qe));
Removing an element from a generic queue is even more complicated. In Listing 10 the code looks like: 

if (q[qn].remove(pv))
   {
   pqe = (int *)pv;
   cout << "removed "<< *pqe << '\n';
   delete pqe;
   }
genq::remove's formal pararmeter has type void *&. That is, it has type "reference to pointer to void." (C++ permits references to pointers but not pointers to references.) Thus, the argument pv passed to remove must be a void *. In essence, all objects come out of the generic container with their compile-time type information stripped away. The application must restore that type information by casting pv back to its original type, which in Listing 10, is int *. The application must also delete the pointer to discard the object removed from the queue. The delete after each remove corresponds to the new invoked with each append.

In addition to its cumbersome user interface this generic queue has other problems associated with the loss of type information that comes from using void *. First, a generic queue is a heterogeneous queue. That is, a single generic queue can hold objects of more than one type. For example, an application can place objects of type int, str, complex, and whatever in the same queue, because all it really stores is their addresses. In my experience, though an application may need to support several types of queued objects, it's almost always better for each queue to be homogeneous. That is, all the elements in any one queue should have the same type. Unfortunately, this generic queue class cannot enforce homogeneity at compile-time.

The second problem is that this queue may leak memory when releasing objects that have a non-trivial destructor. The leaks occur despite the addition of

delete p->element;
to the genq::clear. Again the problem is that p->element has type void *, so this expression lacks the information it needs to call the appropriate destructor. This is not a problem when the queued objects are primitive types, like int, but is a problem when they are types that use additional dynamically allocated resources (str is such a type).

But all hope is not lost. These problems have solutions which are the topic of next month's column.

Errata Errata

In an addendum to my article "Rewriting and Reconsidering" (CUJ, September 1993), I posted errata for a string class I presented in an earlier column "Function Name Overloading" (CUJ, November 1991). Well, I didn't quite get it right. R. Seshadri from Madras, India caught the bug and suggested a repair.

The string class in question had much the same structure as the one I used in this article (Figure 2 and Listing 4 and Listing 5) . My error was a classic "off by one" error. I forgot that the len data member in a string represents the conceptual length of the string (the number of characters excluding the terminating null), rather than the actual length of the array. My catenation functions left the len data member too long by one. Listing 11 shows the necessary corrections.

Upon further reflection, I think my real offense was inconsistent coding style. (Gasp!) Everywhere in the string class, except the cat functions, the memory allocations are in the form

new char[len + 1]
(possibly inside a call to strcpy). In the cat functions, the allocations are in the form

new char[len]
Listing 12 shows the same cat functions rewritten in a style consistent with the rest of the string class.