The C++ Standard Library: A Tutorial and Reference

The C++ Standard Library
Contents
Preface to the Second Edition
Acknowledgments for the Second Edition
Preface to the First Edition
Acknowledgments for the First Edition
1 About This Book
1.1 Why This Book
1.2 Before Reading This Book
1.3 Style and Structure of the Book
1.4 How to Read This Book
1.5 State of the Art
1.6 Example Code and Additional Information
1.7 Feedback
2 Introduction to C++ and the Standard Library
2.1 History of the C++ Standards
2.1.1 Common Questions about the C++11 Standard
2.1.2 Compatibility between C++98 and C++11
2.2 Complexity and Big-O Notation
3 New Language Features
3.1 New C++11 Language Features
3.1.1 Important Minor Syntax Cleanups
3.1.2 Automatic Type Deduction with auto
3.1.3 Uniform Initialization and Initializer Lists
3.1.4 Range-Based for Loops
3.1.5 Move Semantics and Rvalue References
3.1.6 New String Literals
3.1.7 Keyword noexcept
3.1.8 Keyword constexpr
3.1.9 New Template Features
3.1.10 Lambdas
3.1.11 Keyword decltype
3.1.12 New Function Declaration Syntax
3.1.13 Scoped Enumerations
3.1.14 New Fundamental Data Types
3.2 Old “New” Language Features
3.2.1 Explicit Initialization for Fundamental Types
3.2.2 Definition of main()
4 General Concepts
4.1 Namespace std
4.2 Header Files
4.3 Error and Exception Handling
4.3.1 Standard Exception Classes
4.3.2 Members of Exception Classes
4.3.3 Passing Exceptions with Class exception_ptr
4.3.4 Throwing Standard Exceptions
4.3.5 Deriving from Standard Exception Classes
4.4 Callable Objects
4.5 Concurrency and Multithreading
4.6 Allocators
5 Utilities
5.1 Pairs and Tuples
5.1.1 Pairs
5.1.2 Tuples
5.1.3 I/O for Tuples
5.1.4 Conversions between tuples and pairs
5.2 Smart Pointers
5.2.1 Class shared_ptr
5.2.2 Class weak_ptr
5.2.3 Misusing Shared Pointers
5.2.4 Shared and Weak Pointers in Detail
5.2.5 Class unique_ptr
5.2.6 Class unique_ptr in Detail
5.2.7 Class auto_ptr
5.2.8 Final Words on Smart Pointers
5.3 Numeric Limits
5.4 Type Traits and Type Utilities
5.4.1 Purpose of Type Traits
5.4.2 Type Traits in Detail
5.4.3 Reference Wrappers
5.4.4 Function Type Wrappers
5.5 Auxiliary Functions
5.5.1 Processing the Minimum and Maximum
5.5.2 Swapping Two Values
5.5.3 Supplementary Comparison Operators
5.6 Compile-Time Fractional Arithmetic with Class ratio<>
5.7 Clocks and Timers
5.7.1 Overview of the Chrono Library
5.7.2 Durations
5.7.3 Clocks and Timepoints
5.7.4 Date and Time Functions by C and POSIX
5.7.5 Blocking with Timers
5.8 Header Files , , and
5.8.1 Definitions in
5.8.2 Definitions in
5.8.3 Definitions in
6 The Standard Template Library
6.1 STL Components
6.2 Containers
6.2.1 Sequence Containers
6.2.2 Associative Containers
6.2.3 Unordered Containers
6.2.4 Associative Arrays
6.2.5 Other Containers
6.2.6 Container Adapters
6.3 Iterators
6.3.1 Further Examples of Using Associative and Unordered Containers
6.3.2 Iterator Categories
6.4 Algorithms
6.4.1 Ranges
6.4.2 Handling Multiple Ranges
6.5 Iterator Adapters
6.5.1 Insert Iterators
6.5.2 Stream Iterators
6.5.3 Reverse Iterators
6.5.4 Move Iterators
6.6 User-Defined Generic Functions
6.7 Manipulating Algorithms
6.7.1 “Removing” Elements
6.7.2 Manipulating Associative and Unordered Containers
6.7.3 Algorithms versus Member Functions
6.8 Functions as Algorithm Arguments
6.8.1 Using Functions as Algorithm Arguments
6.8.2 Predicates
6.9 Using Lambdas
6.10 Function Objects
6.10.1 Definition of Function Objects
6.10.2 Predefined Function Objects
6.10.3 Binders
6.10.4 Function Objects and Binders versus Lambdas
6.11 Container Elements
6.11.1 Requirements for Container Elements
6.11.2 Value Semantics or Reference Semantics
6.12 Errors and Exceptions inside the STL
6.12.1 Error Handling
6.12.2 Exception Handling
6.13 Extending the STL
6.13.1 Integrating Additional Types
6.13.2 Deriving from STL Types
7 STL Containers
7.1 Common Container Abilities and Operations
7.1.1 Container Abilities
7.1.2 Container Operations
7.1.3 Container Types
7.2 Arrays
7.2.1 Abilities of Arrays
7.2.2 Array Operations
7.2.3 Using arrays as C-Style Arrays
7.2.4 Exception Handling
7.2.5 Tuple Interface
7.2.6 Examples of Using Arrays
7.3 Vectors
7.3.1 Abilities of Vectors
7.3.2 Vector Operations
7.3.3 Using Vectors as C-Style Arrays
7.3.4 Exception Handling
7.3.5 Examples of Using Vectors
7.3.6 Class vector
7.4 Deques
7.4.1 Abilities of Deques
7.4.2 Deque Operations
7.4.3 Exception Handling
7.4.4 Examples of Using Deques
7.5 Lists
7.5.1 Abilities of Lists
7.5.2 List Operations
7.5.3 Exception Handling
7.5.4 Examples of Using Lists
7.6 Forward Lists
7.6.1 Abilities of Forward Lists
7.6.2 Forward List Operations
7.6.3 Exception Handling
7.6.4 Examples of Using Forward Lists
7.7 Sets and Multisets
7.7.1 Abilities of Sets and Multisets
7.7.2 Set and Multiset Operations
7.7.3 Exception Handling
7.7.4 Examples of Using Sets and Multisets
7.7.5 Example of Specifying the Sorting Criterion at Runtime
7.8 Maps and Multimaps
7.8.1 Abilities of Maps and Multimaps
7.8.2 Map and Multimap Operations
7.8.3 Using Maps as Associative Arrays
7.8.4 Exception Handling
7.8.5 Examples of Using Maps and Multimaps
7.8.6 Example with Maps, Strings, and Sorting Criterion at Runtime
7.9 Unordered Containers
7.9.1 Abilities of Unordered Containers
7.9.2 Creating and Controlling Unordered Containers
7.9.3 Other Operations for Unordered Containers
7.9.4 The Bucket Interface
7.9.5 Using Unordered Maps as Associative Arrays
7.9.6 Exception Handling
7.9.7 Examples of Using Unordered Containers
7.10 Other STL Containers
7.10.1 Strings as STL Containers
7.10.2 Ordinary C-Style Arrays as STL Containers
7.11 Implementing Reference Semantics
7.12 When to Use Which Container
8 STL Container Members in Detail
8.1 Type Definitions
8.2 Create, Copy, and Destroy Operations
8.3 Nonmodifying Operations
8.3.1 Size Operations
8.3.2 Comparison Operations
8.3.3 Nonmodifying Operations for Associative and Unordered Containers
8.4 Assignments
8.5 Direct Element Access
8.6 Operations to Generate Iterators
8.7 Inserting and Removing Elements
8.7.1 Inserting Single Elements
8.7.2 Inserting Multiple Elements
8.7.3 Removing Elements
8.7.4 Resizing
8.8 Special Member Functions for Lists and Forward Lists
8.8.1 Special Member Functions for Lists (and Forward Lists)
8.8.2 Special Member Functions for Forward Lists Only
8.9 Container Policy Interfaces
8.9.1 Nonmodifying Policy Functions
8.9.2 Modifying Policy Functions
8.9.3 Bucket Interface for Unordered Containers
8.10 Allocator Support
8.10.1 Fundamental Allocator Members
8.10.2 Constructors with Optional Allocator Parameters
9 STL Iterators
9.1 Header Files for Iterators
9.2 Iterator Categories
9.2.1 Output Iterators
9.2.2 Input Iterators
9.2.3 Forward Iterators
9.2.4 Bidirectional Iterators
9.2.5 Random-Access Iterators
9.2.6 The Increment and Decrement Problem of Vector Iterators
9.3 Auxiliary Iterator Functions
9.3.1 advance()
9.3.2 next() and prev()
9.3.3 distance()
9.3.4 iter_swap()
9.4 Iterator Adapters
9.4.1 Reverse Iterators
9.4.2 Insert Iterators
9.4.3 Stream Iterators
9.4.4 Move Iterators
9.5 Iterator Traits
9.5.1 Writing Generic Functions for Iterators
9.6 Writing User-Defined Iterators
10 STL Function Objects and Using Lambdas
10.1 The Concept of Function Objects
10.1.1 Function Objects as Sorting Criteria
10.1.2 Function Objects with Internal State
10.1.3 The Return Value of for_each()
10.1.4 Predicates versus Function Objects
10.2 Predefined Function Objects and Binders
10.2.1 Predefined Function Objects
10.2.2 Function Adapters and Binders
10.2.3 User-Defined Function Objects for Function Adapters
10.2.4 Deprecated Function Adapters
10.3 Using Lambdas
10.3.1 Lambdas versus Binders
10.3.2 Lambdas versus Stateful Function Objects
10.3.3 Lambdas Calling Global and Member Functions
10.3.4 Lambdas as Hash Function, Sorting, or Equivalence Criterion
11 STL Algorithms
11.1 Algorithm Header Files
11.2 Algorithm Overview
11.2.1 A Brief Introduction
11.2.2 Classification of Algorithms
11.3 Auxiliary Functions
11.4 The for_each() Algorithm
11.5 Nonmodifying Algorithms
11.5.1 Counting Elements
11.5.2 Minimum and Maximum
11.5.3 Searching Elements
11.5.4 Comparing Ranges
11.5.5 Predicates for Ranges
11.6 Modifying Algorithms
11.6.1 Copying Elements
11.6.2 Moving Elements
11.6.3 Transforming and Combining Elements
11.6.4 Swapping Elements
11.6.5 Assigning New Values
11.6.6 Replacing Elements
11.7 Removing Algorithms
11.7.1 Removing Certain Values
11.7.2 Removing Duplicates
11.8 Mutating Algorithms
11.8.1 Reversing the Order of Elements
11.8.2 Rotating Elements
11.8.3 Permuting Elements
11.8.4 Shuffling Elements
11.8.5 Moving Elements to the Front
11.8.6 Partition into Two Subranges
11.9 Sorting Algorithms
11.9.1 Sorting All Elements
11.9.2 Partial Sorting
11.9.3 Sorting According to the nth Element
11.9.4 Heap Algorithms
11.10 Sorted-Range Algorithms
11.10.1 Searching Elements
11.10.2 Merging Elements
11.11 Numeric Algorithms
11.11.1 Processing Results
11.11.2 Converting Relative and Absolute Values
12 Special Containers
12.1 Stacks
12.1.1 The Core Interface
12.1.2 Example of Using Stacks
12.1.3 A User-Defined Stack Class
12.1.4 Class stack<> in Detail
12.2 Queues
12.2.1 The Core Interface
12.2.2 Example of Using Queues
12.2.3 A User-Defined Queue Class
12.2.4 Class queue<> in Detail
12.3 Priority Queues
12.3.1 The Core Interface
12.3.2 Example of Using Priority Queues
12.3.3 Class priority_queue<> in Detail
12.4 Container Adapters in Detail
12.4.1 Type Definitions
12.4.2 Constructors
12.4.3 Supplementary Constructors for Priority Queues
12.4.4 Operations
12.5 Bitsets
12.5.1 Examples of Using Bitsets
12.5.2 Class bitset in Detail
13 Strings
13.1 Purpose of the String Classes
13.1.1 A First Example: Extracting a Temporary Filename
13.1.2 A Second Example: Extracting Words and Printing Them Backward
13.2 Description of the String Classes
13.2.1 String Types
13.2.2 Operation Overview
13.2.3 Constructors and Destructor
13.2.4 Strings and C-Strings
13.2.5 Size and Capacity
13.2.6 Element Access
13.2.7 Comparisons
13.2.8 Modifiers
13.2.9 Substrings and String Concatenation
13.2.10 Input/Output Operators
13.2.11 Searching and Finding
13.2.12 The Value npos
13.2.13 Numeric Conversions
13.2.14 Iterator Support for Strings
13.2.15 Internationalization
13.2.16 Performance
13.2.17 Strings and Vectors
13.3 String Class in Detail
13.3.1 Type Definitions and Static Values
13.3.2 Create, Copy, and Destroy Operations
13.3.3 Operations for Size and Capacity
13.3.4 Comparisons
13.3.5 Character Access
13.3.6 Generating C-Strings and Character Arrays
13.3.7 Modifying Operations
13.3.8 Searching and Finding
13.3.9 Substrings and String Concatenation
13.3.10 Input/Output Functions
13.3.11 Numeric Conversions
13.3.12 Generating Iterators
13.3.13 Allocator Support
14 Regular Expressions
14.1 The Regex Match and Search Interface
14.2 Dealing with Subexpressions
14.3 Regex Iterators
14.4 Regex Token Iterators
14.5 Replacing Regular Expressions
14.6 Regex Flags
14.7 Regex Exceptions
14.8 The Regex ECMAScript Grammar
14.9 Other Grammars
14.10 Basic Regex Signatures in Detail
15 Input/Output Using Stream Classes
15.1 Common Background of I/O Streams
15.1.1 Stream Objects
15.1.2 Stream Classes
15.1.3 Global Stream Objects
15.1.4 Stream Operators
15.1.5 Manipulators
15.1.6 A Simple Example
15.2 Fundamental Stream Classes and Objects
15.2.1 Classes and Class Hierarchy
15.2.2 Global Stream Objects
15.2.3 Header Files
15.3 Standard Stream Operators << and >>
15.3.1 Output Operator <<
15.3.2 Input Operator >>
15.3.3 Input/Output of Special Types
15.4 State of Streams
15.4.1 Constants for the State of Streams
15.4.2 Member Functions Accessing the State of Streams
15.4.3 Stream State and Boolean Conditions
15.4.4 Stream State and Exceptions
15.5 Standard Input/Output Functions
15.5.1 Member Functions for Input
15.5.2 Member Functions for Output
15.5.3 Example Uses
15.5.4 sentry Objects
15.6 Manipulators
15.6.1 Overview of All Manipulators
15.6.2 How Manipulators Work
15.6.3 User-Defined Manipulators
15.7 Formatting
15.7.1 Format Flags
15.7.2 Input/Output Format of Boolean Values
15.7.3 Field Width, Fill Character, and Adjustment
15.7.4 Positive Sign and Uppercase Letters
15.7.5 Numeric Base
15.7.6 Floating-Point Notation
15.7.7 General Formatting Definitions
15.8 Internationalization
15.9 File Access
15.9.1 File Stream Classes
15.9.2 Rvalue and Move Semantics for File Streams
15.9.3 File Flags
15.9.4 Random Access
15.9.5 Using File Descriptors
15.10 Stream Classes for Strings
15.10.1 String Stream Classes
15.10.2 Move Semantics for String Streams
15.10.3 char* Stream Classes
15.11 Input/Output Operators for User-Defined Types
15.11.1 Implementing Output Operators
15.11.2 Implementing Input Operators
15.11.3 Input/Output Using Auxiliary Functions
15.11.4 User-Defined Format Flags
15.11.5 Conventions for User-Defined Input/Output Operators
15.12 Connecting Input and Output Streams
15.12.1 Loose Coupling Using tie()
15.12.2 Tight Coupling Using Stream Buffers
15.12.3 Redirecting Standard Streams
15.12.4 Streams for Reading and Writing
15.13 The Stream Buffer Classes
15.13.1 The Stream Buffer Interfaces
15.13.2 Stream Buffer Iterators
15.13.3 User-Defined Stream Buffers
15.14 Performance Issues
15.14.1 Synchronization with C’s Standard Streams
15.14.2 Buffering in Stream Buffers
15.14.3 Using Stream Buffers Directly
16 Internationalization
16.1 Character Encodings and Character Sets
16.1.1 Multibyte and Wide-Character Text
16.1.2 Different Character Sets
16.1.3 Dealing with Character Sets in C++
16.1.4 Character Traits
16.1.5 Internationalization of Special Characters
16.2 The Concept of Locales
16.2.1 Using Locales
16.2.2 Locale Facets
16.3 Locales in Detail
16.4 Facets in Detail
16.4.1 Numeric Formatting
16.4.2 Monetary Formatting
16.4.3 Time and Date Formatting
16.4.4 Character Classification and Conversion
16.4.5 String Collation
16.4.6 Internationalized Messages
17 Numerics
17.1 Random Numbers and Distributions
17.1.1 A First Example
17.1.2 Engines
17.1.3 Engines in Detail
17.1.4 Distributions
17.1.5 Distributions in Detail
17.2 Complex Numbers
17.2.1 Class complex<> in General
17.2.2 Examples Using Class complex<>
17.2.3 Operations for Complex Numbers
17.2.4 Class complex<> in Detail
17.3 Global Numeric Functions
17.4 Valarrays
18 Concurrency
18.1 The High-Level Interface: async() and Futures
18.1.1 A First Example Using async() and Futures
18.1.2 An Example of Waiting for Two Tasks
18.1.3 Shared Futures
18.2 The Low-Level Interface: Threads and Promises
18.2.1 Class std::thread
18.2.2 Promises
18.2.3 Class packaged_task<>
18.3 Starting a Thread in Detail
18.3.1 async() in Detail
18.3.2 Futures in Detail
18.3.3 Shared Futures in Detail
18.3.4 Class std: :promise in Detail
18.3.5 Class std: :packaged_task in Detail
18.3.6 Class std: :thread in Detail
18.3.7 Namespace this_thread
18.4 Synchronizing Threads, or the Problem of Concurrency
18.4.1 Beware of Concurrency!
18.4.2 The Reason for the Problem of Concurrent Data Access
18.4.3 What Exactly Can Go Wrong (the Extent of the Problem)
18.4.4 The Features to Solve the Problems
18.5 Mutexes and Locks
18.5.1 Using Mutexes and Locks
18.5.2 Mutexes and Locks in Detail
18.5.3 Calling Once for Multiple Threads
18.6 Condition Variables
18.6.1 Purpose of Condition Variables
18.6.2 A First Complete Example for Condition Variables
18.6.3 Using Condition Variables to Implement a Queue for Multiple Threads
18.6.4 Condition Variables in Detail
18.7 Atomics
18.7.1 Example of Using Atomics
18.7.2 Atomics and Their High-Level Interface in Detail
18.7.3 The C-Style Interface of Atomics
18.7.4 The Low-Level Interface of Atomics
19 Allocators
19.1 Using Allocators as an Application Programmer
19.2 A User-Defined Allocator
19.3 Using Allocators as a Library Programmer
Bibliography
Newsgroups and Forums
Books and Web Sites
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
The C++ Standard Library: Supplementary Chapter
Contents
S.1 Bitsets
S.1.1 Examples of Using Bitsets
S.1.2 Class bitset<> in Detail
S.2 Valarrays
S.2.1 Getting to Know Valarrays
S.2.2 Valarray Subsets
S.2.3 Class valarray in Detail
S.2.4 Valarray Subset Classes in Detail
S.3 Allocators and Memory Functions in Detail
S.3.1 Scoped Allocators
S.3.2 A User-Defined Allocator for C++98
S.3.3 The Default Allocator
S.3.4 Allocators in Detail
S.3.5 Utilities for Uninitialized Memory in Detail