CONTENTS
Chapter 9 Sequential Containers
Chapter 10 Associative Containers
Chapter 11 Generic Algorithms
We’ve said that C++ is about efficient programming with abstractions. The Standard Library is a good example: The library defines a number of container classes and a family of generic algorithms that let us write programs that are succinct, abstract, and efficient. The library worries about bookkeeping details—in particular, taking care of memory management—so that our programs can worry about the actual problems we need to solve.
In Chapter 3 we introduced the vector
container type. We’ll learn more in Chapter 9 about vector
and the other sequential container types provided by the library. We’ll also cover more operations provided by the string
type. We can think of a string
as a special kind of container that contains only characters. The string
type supports many, but not all, of the container operations.
The library also defines several associative containers. Elements in an associative container are ordered by key rather than sequentially. The associative containers share many operations with the sequential containers and also define operations that are specific to the associative containers. The associative containers are covered in Chapter 10.
Chapter 11 introduces the generic algorithms. The algorithms typically operate on a range of elements from a container or other sequence. The algorithms library offers efficient implementations of various classical algorithms, such as searching, sorting, and other common tasks. For example, there is a copy
algorithm, which copies elements from one sequence to another; find
, which looks for a given element; and so on. The algorithms are generic in two ways: They they can be applied to different kinds of containers, and those containers may contain elements of most types.
The library is designed so that the container types provide a common interface: If two containers offer a similar operation, then that operation will be defined identically for both containers. For example, all the containers have an operation to return the number of elements in the container. All the containers name that operation size
, and they all define a type named size_type
that is the type of the value returned by size
. Similarly, the algorithms have a consistent interface. For example, most algorithms operate on a range of elements specified by a pair of iterators.
Because the container operations and algorithms are defined consistently, learning the library becomes easier: Once you understand how an operation works, you can apply that same operation to other containers. More importantly, this commonality of interface leads to more flexible programs. It is often possible to take a program written to use one container type and change it to use a different container without having to rewrite code. As we’ll see, the containers offer different performance tradeoffs, and the ability to change container types can be valuable when fine-tuning the performance of a system.