Managing Data with Containers

Introduction

This chapter describes the data structures in the standard library that you can use to store data. They are generally referred to as containers, since they "contain" objects you add to them. This chapter also describes another sort of container that is not part of the standard library, although it ships with most standard library implementations, namely the hashed container.

The part of the library that comprises the containers is often referred to as the Standard Template Library, or STL, because this is what it was called before it was included in the C++ standard. The STL includes not only the containers that are the subject of this chapter, but iterators and algorithms, which are the two other building blocks of the STL that make it a flexible, generic library. Since this chapter is primarily about the standard containers and not the STL in its entirety, I will refer to containers as the "standard containers" and not "STL containers," as is done in much of the C++ literature. Although I discuss iterators and algorithms as much as necessary here, both are discussed in more detail in Chapter 7.

The C++ standard uses precise terminology to describe its collection of containers. A "container" in the C++ standard library is a data structure that has a well-defined interface described in the standard. For example, any C++ standard library class that calls itself a container must support a member function begin that has no parameters and that returns an iterator referring to the first element in that container. There are a number of required constructors and member functions that define what it is to be a container in C++ terms. There are also optional member functions only some containers implement, usually those that can be implemented efficiently.

The set of all containers is further subdivided into two different kinds of containers: sequence containers and associative containers. A sequence container (usually just called a sequence) stores objects in an order that is specified by the user, and provides a required interface (in addition to container requirements) for accessing and manipulating the elements. Associative containers store their elements in sorted order, and therefore do not permit you to insert elements at a specific location, although you can provide hints when you insert to improve efficiency. Both sequences and associative containers have a required interface they must support, but only sequences have an additional set of operations that are only supported by sequences for which they can be implemented efficiently. These additional sequence operations provide more flexibility and convenience than the required interface.

This sounds a lot like inheritance. A sequence is a container, an associative container is a container, but a container is not a sequence or an associative container. It's not inheritance, though, in the C++ sense, but it is inheritance conceptually. A vector is a sequence, but it is its own, standalone class; it doesn't inherit from a container class or some such thing (standard library implementations are allowed freedom in how they implement vector and other containers, but the standard doesn't mandate that a standard library implementation include a container base class). A great deal of thought went into the design of the containers, and if you would like to read more about it go pick up Matt Austern's Generic Programming and the STL (Addison Wesley).

This chapter has two parts. The first few recipes describe how to use vector, which is a standard sequence, since it is one of the more popular data structures. They describe how to use a vector effectively and efficiently. The rest of the recipes discuss most of the other standard containers that are widely applicable, including the two nonstandard hashed containers I mentioned earlier.