This twelve-part tutorial discusses the C++ Standard Template Library
(STL) and its three key componentscontainers, iterators and
algorithms. We begin with an overview of the STL's seven first-class
containers and three container adapters, then we present the common functionality
provided by most of these containers. Next, we discuss the five categories of STL iterators and the
capabilities provided for each category.
Finally, we overview STL algorithms. Using iterators with STL algorithms
enables you to perform complex operations on the elements of various STL
containers (and standard arrays), often without regard for the underlying container's
implementation. For example, using iterators and the STL's
you can copy the elements of a container to another container (possibly of
an unrelated container type), to a file or to the standard output with a
single line of code! In a subsequent tutorial, we'll introduce the
container, iterators and the
Before You Begin: Download the code examples for this tutorial
[Note: This tutorial is an excerpt (Sections
23.1) of Chapter 23, Standard Template Library (STL), from our textbook C++ How to Program, 5/e. These
tutorials may refer to other chapters or sections of the book that are not included here. Permission Information: Deitel, Harvey M. and Paul J., C++ HOW TO PROGRAM, ©2005, pp.1112-1123. Electronically reproduced by permission of Pearson Education, Inc., Upper Saddle River, New Jersey.]
We have repeatedly emphasized the importance of software reuse. Recognizing that many data structures and algorithms commonly are used by C++ programmers, the C++ standard committee added the Standard Template Library (STL) to the C++ Standard Library. The STL defines powerful, template-based, reusable components that implement many common data structures, and algorithms used to process those data structures. The STL offers proof of concept for generic programming with templates—introduced in Chapter 14, Templates, and demonstrated in detail in Chapter 21, Data Structures. [Note: In industry, the features presented in this chapter are commonly referred to as the Standard Template Library or STL. However, these terms are not used in the C++ standard document, because these features are simply considered to be part of the C++ Standard Library.]
The STL was developed by Alexander Stepanov and Meng Lee at Hewlett-Packard and is based on their research in the field of generic programming, with significant contributions from David Musser. As you will see, the STL was conceived and designed for performance and flexibility.
This chapter introduces the STL and discusses its three key components—containers (popular templatized data structures), iterators and algorithms. The STL containers are data structures capable of storing objects of any data type. We will see that there are three container categories—first-class containers, adapters and near containers.
Performance Tip 23.1
|For any particular application, several different STL containers might be appropriate. Select the most appropriate container that achieves the best performance (i.e., balance of speed and size) for that application. Efficiency was a crucial consideration in STL’s design.|
Performance Tip 23.2
|Standard Library capabilities are implemented to operate efficiently across many applications. For some applications with unique performance requirements, it might be necessary to write your own customized implementations.|
Each STL container has associated member functions. A subset of these member functions is defined in all STL containers. We illustrate most of this common functionality in our examples of STL containers
vector (a dynamically resizable array which we introduced in Chapter 7, Arrays and Vectors),
list (a linked list) and
deque (a double-ended queue, pronounced “deck”). We introduce container-specific functionality in examples for each of the other STL containers.
STL iterators, which have properties similar to those of pointers, are used by programs to manipulate the STL-container elements. In fact, standard arrays can be manipulated as STL containers, using standard pointers as iterators. We will see that manipulating containers with iterators is convenient and provides tremendous expressive power when combined with STL algorithms—in some cases, reducing many lines of code to a single statement. There are five categories of iterators, each of which we discuss in Section 23.1.2 and use throughout this chapter.