Abstract Container Structures: The Taxonomy

A container data structure (or container in the sequel) is an object which serves to store and access collections of objects, called the items of the container. All classes describing containers are descendants of the deferred class CONTAINER.

A container can be studied from three viewpoints: access, storage and traversal.

• The access criterion affects how the clients of a container can access its items. For example, in a stack or queue, only one item is accessible at any given time, and clients do not choose that item; in contrast, clients of an array or hash table must provide an index, or more generally a key, to access an item.
• The storage criterion affects how the items are put together. For example some containers are finite, others potentially infinite; among finite structures, some are bounded, others unbounded.
• The traversal criterion affects how, if in any way, the items of a container can be traversed. A traversal is a mechanism which makes it possible to examine each item of a container once, in a clearly specified order. For example some containers can be traversed sequentially, in one direction or two; tree structures lend themselves to preorder, postorder and breadth-first traversals.

For each of these criteria the Base library offers a single-inheritance hierarchy of deferred classes. The top of the access hierarchy is class COLLECTION; the top of the storage hierarchy is class BOX; the top of the traversal hierarchy is class TRAVERSABLE. These three classes are heirs of the most general class, CONTAINER.