Using the STL

This book provides a comprehensive introduction and guide to the STL pitched at the level of readers already familiar with C++. It presents a thorough overview of the capabilities of the STL, detailed discussions of the use of containers, descriptions of the algorithms and how they may be used, and how the STL may be extended. An appendix provides an alphabetical reference to the entire STL. As a result, programmers of C++ and students coming to the STL for the first time will find this an extremely useful hands-on text.

Table of contents

Preface
1 Introduction
1.1 What Is STL?
1.2 History
1.3 STL Components
1.4 Generic Algorithms
1.4.1 C++ Templates
1.5 Iterators
1.6 Complexity
1.6.1 Analyzing Complexity
1.7 Overview of this Book
2 Iterators
2.1 Introduction
2.2 Pointers as Iterators
2.3 Iterator Classes
2.3.1 Input Iterators
2.3.2 Output Iterators
2.3.3 Forward Iterators
2.3.4 Bidirectional Iterators
2.3.5 Random Access Iterators
2.4 Using Iterators
2.4.1 Stream Iterators
2.4.2 Forward Iterators
2.4.3 Bidirectional Iterators
2.4.4 Random Access Iterators
2.5 Iterator Functions
3 The STL Algorithms
3.1 Introduction
3.2 Operators
3.3 Function Objects
3.4 The STL Algorithms
3.4.1 Algorithm Categories
4 Sequence Algorithms
4.1 Introduction
4.2 Preliminaries
4.3 Non-Mutating Sequence Algorithms
4.3.1 Counting
4.3.2 Finding
4.3.3 Finding Adjacent Values
4.3.4 ForEach
4.3.5 Mismatching Values
4.3.6 Sequence Equality
4.3.7 Searching
4.4 Mutating Sequence Algorithms
4.4.1 Copy
4.4.2 Swapping
4.4.3 Filling
4.4.4 Generate
4.4.5 Replace
4.4.6 Transform
4.4.7 Remove
4.4.8 Unique
4.4.9 Reverse
4.4.10 Rotate
4.4.11 Random Shuffle
4.4.12 Partitioning
5 Sorting and Related Algorithms
5.1 Introduction
5.2 Preliminaries
5.3 Sorting
5.3.1 Nth Element
5.4 Searching Algorithms
5.4.1 Binary Search
5.4.2 Lower Bound
5.4.3 Upper Bound
5.4.4 EqualRange
5.4.5 Merge
5.5 Set Algorithms
5.5.1 Includes
5.5.2 Set Union
5.5.3 Set Intersection
5.5.4 Set Difference
5.5.5 Symmetric Set Difference
5.6 Heap Algorithms
5.7 Miscellaneous Algorithms
5.7.1 Maximum and Minimum
5.7.2 Lexicographical Comparison
5.7.3 Permutations
6 Generalized Numeric Algorithms
6.1 Numeric Algorithms
6.2 Accumulation
6.3 Inner Product
6.4 Partial Sum
6.5 Adjacent Difference
7 Sequence Containers
7.1 Introduction
7.2 Container Operations
7.3 Vectors
7.3.1 Bit Vectors
7.4 Lists
7.4.1 List Implementation
7.4.2 List Examples
7.4.3 List Operations
7.5 Deques
7.5.1 Deque Implementation
7.6 Choosing a Sequence Container
8 Associative Containers
8.1 Introduction
8.2 Associative Container Operations
8.3 Sets
8.4 Multisets
8.5 Maps
8.5.1 Multimaps
8.6 Associative Container Implementation
8.6.1 Trees
8.6.2 Hash Tables
8.7 Experimental Hash Table Implementation
8.8 Container Selection
9 Adaptors
9.1 Introduction
9.2 Container Adaptors
9.3 The Stack
9.4 Queues
9.5 Priority Queues
9.6 Iterator Adaptors
9.6.1 Reverse Iterators
9.6.2 Insert Iterators
9.6.3 Raw Storage Iterators
9.7 Summary
10 Allocators
10.1 Introduction
10.2 The PC Memory Model
10.3 The Allocator Solution
10.3.1 The Allocator Interface
10.4 Summary
11 Putting the STL to Work
11.1 Introduction
11.2 A Banking Problem
11.3 Symbol Tables
11.3.1 A Cross-Reference Generator
11.3.2 Hierarchical Symbol Tables
11.4 Reversing Sequences
Chapter 12: The Story Continues
12.1 Introduction
12.2 The Future
12.2.1 Persistence
12.2.2 Safety
12.3 Summary
References
Appendix A: The STL Reference
Index