Generic containers

Container classes are the solution to a specific kind of code reuse problem. They are building blocks used to create object-oriented programs?they make the internals of a program much easier to construct. A container class describes an object that holds other objects. Container classes are so important that they were considered fundamental to early object-oriented languages. In Smalltalk, for example, programmers think of the language as the program translator together with the class library, and a critical part of that library is the container classes. So it became natural that C++ compiler vendors also include a container class library. You?ll note that the vector was so useful that it was introduced in its simplest form very early in this book.

Like many other early C++ libraries, early container class libraries followed Smalltalk?s object-based hierarchy, which worked well for Smalltalk, but turned out to be awkward and difficult to use in C++. Another approach was required.

The C++ approach to containers is based, of course, on templates. The containers in the standard C++ library represent a full complement of data structures designed to work well with the standard algorithms and to meet common software development needs.

Containers and iterators

If you don?t know how many objects you?re going to need to solve a particular problem, or how long they will last, you also don?t know how to store those objects. How can you know how much space to create? You can?t, since that information isn?t known until run time.

The solution to most problems in object-oriented design seems flippant: you create another type of object. For the storage problem, the new type of object holds other objects or pointers to objects. Of course, you can do the same thing with an array, but there?s more. This new type of object, which is typically referred to in C++ as a container (also called a collection in some languages), expands itself whenever necessary to accommodate everything you place inside it. So you don?t need to know how many objects you?re going to hold in a collection. You just create a collection object and let it take care of the details.

Fortunately, a good object-oriented programming language comes with a set of containers. In C++, it?s the Standard Template Library. In some libraries, a generic container is considered good enough for all needs, and in others (C++ in particular) the library has different types of containers for different needs: a vector for consistent access to all elements, and a linked list for consistent insertion at all elements, for example, so you can choose the particular type that fits your needs. These containers can include sets, queues, hash tables, trees, stacks, and so on.

All containers have some way to put things in and get things out. The way you place something into a container is fairly obvious. There?s a function called ?push? or ?add? or a similar name. Fetching things out of a container is not always as apparent; if an entity is array-like, such as a vector, you might be able to use an indexing operator or function. But in many situations this doesn?t make sense. Also, a single-selection function is restrictive. What if you want to manipulate or compare a group of elements in the container?

The solution, of course, is an iterator, which is an object whose job is to select the elements within a container and present them to the user of the iterator. As a class, an iterator also provides a level of abstraction, which you can use to separate the details of the container from the code that?s accessing that container. The container, via the iterator, is abstracted to be simply a sequence. The iterator lets you traverse that sequence without worrying about the underlying structure?that is, whether it?s a vector, a linked list, a set, or something else. This gives you the flexibility to easily change the underlying data structure without disturbing the code in your program that traverses the container. Separating iteration from the control of the container traversed also allows having multiple iterators that traverse the same container simultaneously.

From a design standpoint, all you really want is a sequence that can be manipulated to solve your problem. If a single type of sequence satisfied all your needs, there?d be no reason to have different kinds. You need a choice of containers for two reasons. First, containers provide different types of interfaces and external behavior. A stack has an interface and a behavior that is different from that of a queue, which is different from that of a set or a list. One of these might provide a more flexible solution to your problem than the other. Second, different containers have different efficiencies for certain operations. Compare a vector to a list, as an example. Both are simple sequences that can have nearly identical interfaces and external behaviors. But certain operations can have radically different costs. Randomly accessing elements in a vector is a constant-time operation; it takes the same amount of time regardless of the element you select. However, it is expensive to move through a linked list to randomly select an element, and it takes longer to find an element if it is farther down the list. On the other hand, if you want to insert an element in the middle of a sequence, it?s much cheaper in a list than in a vector. The efficiencies of these and other operations depend on the underlying structure of the sequence. In the design phase, you might start with a list and, when tuning for performance, change to a vector. Because of the abstraction via iterators, code that merely traverses sequences is insulated from changes in the underlying sequence implementation.

Remember that a container is only a storage cabinet in which to put objects. If that cabinet solves all your needs, it probably doesn?t really matter how it is implemented. If you?re working in a programming environment that has built-in overhead due to other factors, the cost difference between a vector and a linked list might not matter. You might need only one type of sequence. You can even imagine the ?perfect? container abstraction, which can automatically change its underlying implementation according to the way it is used.

One Comment

  1. Sorry to disappoint you, but this is actually bull. STL containers are not meant to be used as base classes. There are no virtual functions to overwrite, so you can’t alter the functionality. Data members are private, so no luck there either – these two points are make container inheritance questionable, but the fact that no virtual destructor is offered makes it just plain wrong. Deleting a derived class via a pointer to the container base class will result in undefined behaviour.

    If you want to add data members, just use composition. If you want to add functionality, write a new algorithm, but don’t inherit from STL containers.

    You might want to look this issue up, the internet is actually full of advice on this, as many novice STL users make this mistake…

Leave a Reply