CONTENTS
Section 9.1 Defining a Sequential Container
Section 9.2 Iterators and Iterator Ranges
Section 9.3 Sequence Container Operations
Section 9.4 How a vector Grows
Section 9.5 Deciding Which Container to Use
Section 9.6 strings Revisited
Section 9.7 Container Adaptors
This chapter completes our discussion of the standard-library sequential container types. It expands on the material from Chapter 3, which introduced the most commonly used sequential container, the vector type. Elements in a sequential container are stored and accessed by position. The library also defines several associative containers, which hold elements whose order depends on a key. Associative containers are covered in the next chapter.
The container classes share a common interface. This fact makes the library easier to learn; what we learn about one type applies to another. Each container type offers a different set of time and functionality tradeoffs. Often a program using one type can be fine-tuned by substituting another container without changing our code beyond the need to change type declarations.
sequential container. It holds a collection of elements of a single type, making it a container. Those elements are stored and accessed by position, making it a sequential container. The order of elements in a sequential container is independent of the value of the elements. Instead, the order is determined by the order in which elements are added to the container.
The library defines three kinds of sequential containers: vector, list, and deque (short for "double-ended queue" and pronounced "deck"). These types differ in how elements are accessed and the relative run-time cost of adding or removing elements. The library also provides three container adaptors. Effectively, an adaptor adapts an underlying container type by defining a new interface in terms of the operations provided by the original type. The sequential container adaptors are stack, queue, and priority_queue.
Containers define only a small number of operations. Many additional operations are provided by the algorithms library, which we'll cover in Chapter 11. For those operations that are defined by the containers, the library imposes a common interface. The containers vary as to which operations they provide, but if two containers provide the same operation, then the interface (name and number of arguments) will be the same for both container types. The set of operations on the container types form a kind of hierarchy:
Some operations are supported by all container types.
Other operations are common to only the sequential or only the associative containers.
Still others are common to only a subset of either the sequential or associative containers.
In the remainder of this chapter, we look at the sequential container types and their operations in detail.
Sequential Containers
vector
Supports fast random access
list
Supports fast insertion/deletion
deque
Double-ended queue
Sequential Container Adaptors
stack
Last in/First out stack
queue
First in/First out queue
priority_queue
Priority-managed queue