18 Standard Template Library and C++11

1. 18.1 Iterators 961

   1. using Declarations 961

   2. Iterator Basics 962

   3. Programming Tip: Use auto to Simplify Variable Declarations 966

   4. Pitfall: Compiler Problems 966

   5. Kinds of Iterators 968

   6. Constant and Mutable Iterators 972

   7. Reverse Iterators 973

   8. Other Kinds of Iterators 974

2. 18.2 Containers 975

   1. Sequential Containers 976

   2. Pitfall: Iterators and Removing Elements 980

   3. Programming Tip: Type Definitions in Containers 981

   4. Container Adapters stack and queue 981

   5. Associative Containers set and map 985

   6. Programming Tip: Use Initialization, Ranged for, and auto with Containers 992

   7. Efficiency 992

3. 18.3 Generic Algorithms 993

   1. Running Times and Big-O Notation 994

   2. Container Access Running Times 997

   3. Nonmodifying Sequence Algorithms 999

   4. Container Modifying Algorithms 1003

   5. Set Algorithms 1005

   6. Sorting Algorithms 1006

4. 18.4 C++ is Evolving 1007

   1. std::array 1007

   2. Regular Expressions 1008

   3. Threads 1013

   4. Smart Pointers 1019

1. Chapter Summary 1025

2. Answers to Self-Test Exercises 1026

3. Practice Programs 1027

4. Programming Projects 1029

Libraries are not made; they grow.

AUGUSTINE BIRRELL

Introduction

There is a large collection of standard data structures for holding data. Since they are so standard it makes sense to have standard portable implementations for them. The Standard Template Library (STL) includes libraries for such data structures. Included in the STL are implementations of the stack, queue, and many other standard data structures. When discussed in the context of the STL, these data structures are usually called container classes because they are used to hold collections of data. In Chapter 8 we presented a preview of the STL by describing the vector template class, which is one of the container classes in the STL. In this chapter we will present an overview of some of the basic classes included in the STL. We do not have room to give a comprehensive treatment of the STL here, but we will present enough to get you started using some basic STL container classes.

The STL was developed by Alexander Stepanov and Meng Lee at Hewlett-Packard and was based on research by Stepanov, Lee, and David Musser. It is a collection of libraries written in the C++ language. Although the STL is not part of the core C++ language, it is part of the C++ standard and so any implementation of C++ that conforms to the standard would include the STL. As a practical matter, you can consider the STL to be part of the C++ language.

As its name suggest, the classes in the STL are template classes. A typical container class in the STL has a type parameter for the type of data to be stored in the container class. The STL container classes make extensive use of iterators, which are objects that facilitate cycling through the data in a container. An introduction to the concept of an iterator was given in Section 13.1, where we discussed pointers used as iterators. You will find it helpful to read that section before reading this chapter. If you have not already done so, you should also read Section 8.3, which covers the vector template class of the STL.

The STL also includes implementations of many important generic algorithms, such as searching and sorting algorithms. The algorithms are implemented as template functions. After discussing the container classes, we will describe some of these algorithm implementations.

The STL differs from other C++ libraries, such as <iostream> for example, in that the classes and algorithms are generic, which is another way of saying they are template classes and template functions.

Prerequisites

This chapter uses the material from Chapters 2 through 13, 15, and Chapter 17.