Thinking In C++. Volume 2: Practical Programming

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 early in Volume 1 of 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 broad range 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 ahead of time how to store those objects. How can you know how much space to create? You don’t until run time^.

The solution to most problems in object-oriented design seems simple: you create another type of object. For the storage problem, the new type of object holds other objects or pointers to objects. 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. You don’t need to know ahead of time how many objects you’re going to place in a container; you just create a container 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 positions, and many more, so you can choose the particular type that fits your needs^.

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 for flexible element access is an iterator, 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 seen as 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 simultaneously^.