next up previous
Next: Performance Up: The GNU C++ Library Previous: Inheritance and Overloading

Containers

The first option (not supporting many constructive operations) was indeed taken for libg++ container classes including sets, maps, lists, and queues. These classes mainly support standard ``object semantics''. For example, there is a Set::operator |=(Set& b) to union all of the elements of b into the receiver, but not a Set operator |(Set& a, Set& b) to construct a new Set by unioning two others. There were a number of reasons for this decision. The simplest is that mutative operations are most typically needed in applications using such classes.

There is also a technical reason. It is a common (if not always defensible) policy to tie the interfaces of classes like String and Complex to particular representations. However, classes like Set really must be abstract base classes. They provide interfaces without providing implementations. There are countless ways of implementing Sets (lists, arrays, trees, tables, and so on). It is a terrible idea to settle on any one particular strategy. The many libg++ classes that implement this functionality in particular ways are defined as subclasses. But one cannot construct (direct) instances of abstract base classes. Thus, it is impossible to declare a constructive version of operator |() that covers all cases in the first place, regardless of whether other overloading versus inheritance issues could be settled. (A workaround would be to define this operator to return a pointer or reference. But this interferes with value semantics and leads to storage management responsibility problems.)

Inheritance and Parameterization

Container classes may be used in two slightly different roles:

Collections.
Classes that keep track of groups of objects that are all related in some way or are all to be manipulated in a certain fashion.

Repositories.
Classes that ``house'' groups of objects while also providing structured access.

The basic implementation difference is that collections hold pointers to objects that ``live'' elsewhere, while repositories hold and internally manage the objects themselves. Luckily, the low-level mechanics do not so much that these two forms cannot be combined via the convention that any object used as an element in a repository must support a copy constructor, an assignment operator, and, in some classes, a default constructor, an equality function, and/or a magnitude comparison function.

There are two reasonable stances in designing and using pointer-based collections. For example, for Stacks, one may either define a single class that holds pointers to Any object, or design a special class for each different element type. In the latter case, parameterization mechanisms avoid the need to write so many special classes that differ only with respect to element pointer type information. Libg++ does not provide policy about this issue, only mechanism. One may define a Stack that holds pointers to anything as:

typedef void* AnyPtr;
AnyPtrSLStack mystack;

( Libg++ containers were designed long before C++ templates were defined and implemented. They still rely on the use of a manual expansion tool rather than template mechanisms. As support for paramterized types in C++ improves, the distributed versions are being modified accordingly. Dependence on simple manual tools resulted in other minor trade-offs as well. For example, even though desirable, different collection classes are not linked to, say, a Collection superclass and/or other intervening abstract classes. The two-level abstract/concrete organization was hard enough to use as it was. This, in turn led to unnecessary code duplication within the library.)

These declarations define a stack that may hold instances of any kind of class whatsoever. This is OK for putting things into a stack, but sometimes less so when they are pulled out. Unless it somehow happens to have additional information, a client looking at the top element does not know anything at all about its capabilities. As far as type information is concerned, it could be anything.

On the other hand, if a client has a WindowPtrStack (i.e., a stack holding pointers to objects of class Window), it knows that all elements are Windows. The objects might still be of any subclass of Window; perhaps Bordered Window, Scrollable Window or whatever. But they are surely at least Windows. This guarantees that clients can perform window-based operations on all of the objects without having to bother with type tests, downcasting, or error-handling details.

Parameterized collection classes are thus generally safer than unrestricted classes and lead to simpler use by clients. However, because this is a matter of relative safety, there is much room for judgment and disagreement about designs. For example, in a particular application operation, one may really require that all objects are in fact BorderedWindows, in which case type testing, etc., would still be warranted whether stacks of Any or Window were accepted as arguments. Given this, along with the fact that parameterization can generate wasteful multiple versions of the same code but with different type contraints, a library must provide both options.

Moreover, only the parameterization option is viable in the case of repositories. Even though the high-level source code is identicial, each version of a parameterized class maintains storage space, arranges construction, etc., specialized for a particular element type. Thus, both types and executable code are different for each kind of element. In fact, while very useful, the resulting code is slightly dangerous. For example, the type information in a repository set, s, of Windows does not indicate that if s.add(b) for a BorderedWindow b, then only a ``chopped copy'' of b is actually held in s (i.e., the internally held copy of b will act only as a Window on access).


next up previous
Next: Performance Up: The GNU C++ Library Previous: Inheritance and Overloading


Doug Lea@Sun Apr 16 06:37:14 EDT 1995