C++ Cookbook

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 ...