The Container Zoo

In the previous two chapters, we introduced the ideas of iterators and ranges (Chapter 2, Iterators and Ranges) and the vast library of standard generic algorithms that operate on ranges of data elements defined by pairs of those iterators (Chapter 3, The Iterator-Pair Algorithms). In this chapter, we'll look at where those data elements themselves are allocated and stored. That is, now that we know all about how to iterate, the question gains urgency: what is it that we are iterating over?

In the Standard Template Library, the answer to that question is generally: We are iterating over some sub-range of the elements contained in a container. A container is simply a C++ class (or class template) which, by its nature, contains (or owns) a homogeneous range of data elements, and exposes that range for iteration by generic algorithms.

Topics we will cover in this chapter are:

• The notion of one object owning another (this being the essential difference between a container and a range)
• The sequence containers (array, vector, list, and forward_list)
• The pitfalls of iterator invalidation and reference invalidation
• The container adaptors (stack, queue, and priority_queue)
• The associative containers (set, map, and friends)
• When it is appropriate to provide a comparator, hash function, equality comparator, or allocator as additional template type parameters