Contents of the book Designing Components with the C++ STL
ISBN 0-201-67488-2 (revised edition), copyright 2000 Addison Wesley Longman

Foreword vii 
Preface ix 
Part I Introduction
1 The concept of the C++ Standard Template Library (STL)
1.1 Genericity of components
1.2 Abstract and implicit data types
1.3 The fundamental concept
1.3.1 Containers
1.3.2 Iterators
1.3.3 Algorithms
1.3.4 Interplay
1.4 Internal functioning
1.5 Complexity 14 
1.5.1 O notation 15 
1.5.2 Omega notation 18 
1.6 Auxiliary classes and functions 19 
1.6.1 Pairs 19 
1.6.2 Comparison operators 20 
1.6.3 Function objects 25 
1.6.4 Function adapters 25 
1.7 Some conventions 28 
1.7.1 Namespaces 28 
1.7.2 Header files 28 
1.7.3 Allocators 28 
2 Iterators 29 
2.1 Iterator properties 30 
2.1.1 States 30 
2.1.2 Standard iterator and traits classes 30 
2.1.3 Distances 32 
2.1.4 Categories 33 
2.1.5 Reverse iterators 35 
2.1.6 Tag classes 36 
2.2 Stream iterators 37 
2.2.1 Istream iterator 37 
2.2.2 Ostream iterator 40 
3 Containers 47 
3.1 Data type interface 47 
3.2 Container methods 48 
3.2.1 Reversible containers 49 
3.3 Sequences 50 
3.3.1 Vector 51 
3.3.2 List 55 
3.3.3 Deque 59 
3.3.4 showSequence 59 
3.4 Iterator categories and containers 60 
3.4.1 Derivation of value and distance types 63 
3.4.2 Inheriting iterator properties 65 
3.5 Iterators for insertion into containers 66 
4 Abstract data types 73 
4.1 Stack 73 
4.2 Queue 74 
4.3 Priority queue 76 
4.4 Sorted associative containers 78 
4.4.1 Set 79 
4.4.2 Multiset 82 
4.4.3 Map 83 
4.4.4 Multimap 86 
Part II Algorithms 95 
5 Standard algorithms 89 
5.1 Copying algorithms 89 
5.2 Algorithms with predicates 90 
5.2.1 Algorithms with binary predicates 91 
5.3 Nonmutating sequence operations 91 
5.3.1 for_each 92 
5.3.2 find und find_if 93 
5.3.3 find_end 94 
5.3.4 find_first_of 95 
5.3.5 adjacent_find 96 
5.3.6 count and count_if 98 
5.3.7 mismatch 99 
5.3.8 equal 101 
5.3.9 search 102 
5.3.10 search_n 104 
5.4 Mutating sequence operations 105 
5.4.1 iota 105 
5.4.2 copy and copy_backward 106 
5.4.3 copy_if 117 
5.4.4 swap, iter_swap and swap_ranges 109 
5.4.5 transform 111 
5.4.6 replace and variants 113 
5.4.7 fill and fill_n 115 
5.4.8 generate and generate_n 116 
5.4.9 remove and variants 117 
5.4.10 unique 119 
5.4.11 reverse 120 
5.4.12 rotate 121 
5.4.13 random_shuffle 123 
5.4.14 partition 125 
5.5 Sorting, merging, and related operations 126 
5.5.1 sort 127 
5.5.2 nth_element 130 
5.5.3 Binary search 132 
5.5.4 Merging 135 
5.6 Set operations on sorted structures 139 
5.6.1 includes 139 
5.6.2 set_union 140 
5.6.3 set_intersection 141 
5.6.4 set_difference 142 
5.6.5 set_symmetric_difference 143 
5.6.6 Conditions and limitations 144 
5.7 Heap algorithms 146 
5.7.1 pop_heap 147 
5.7.2 push_heap 150 
5.7.3 make_heap 152 
5.7.4 sort_heap 153 
5.8 Minimum and maximum 155 
5.9 Lexikographical comparison 156 
5.10 Permutations 157 
5.11 Numeric algorithms 158 
5.11.1 accumulate 159 
5.11.2 inner_product 159 
5.11.3 partial_sum 161 
5.11.4 adjacent_difference 162 
Part III Beyond the STL: components and applications 165 
6 Set operations on associative containers 167 
6.1 Subset relation 168 
6.2 Union 168 
6.3 Intersection 169 
6.4 Difference 170 
6.5 Symmetric difference 170 
6.6 Example 171 
7 Fast associative containers 175 
7.1 Fundamentals 175 
7.1.1 Collision handling 176 
7.2 Map 177 
7.2.1 Example 186 
7.3 Set 188 
7.4 Overloaded operators for sets 188 
7.4.1 Union 189 
7.4.2 Intersection 189 
7.4.3 Difference 190 
7.4.4 Symmetric difference 190 
7.4.5 Example 190 
8 Various applications 193 
8.1 Cross-reference 193 
8.2 Permuted index 195 
8.3 Thesaurus 198 
9 Vectors and matrices 203 
9.1 Checked vectors 203 
9.2 Matrices as nested containers 205 
9.2.1 Two-dimensional matrices 206 
9.2.2 Three-dimensional matrices 209 
9.2.3 Generalization 212 
9.3 Matrices for different memory models 212 
9.3.1 C memory layout 215 
9.3.2 FORTRAN memory layout 216 
9.3.3 Memory layout for symmetric matrices 217 
9.4 Sparse matrices 218 
9.4.1 Index operator and assignment 222 
9.4.2 Hash function for index pairs 223 
9.4.3 Class MatrixElement 224 
9.4.4 Class sparseMatrix 226 
9.4.5 Run time measurements 229 
10 External sorting 231 
10.1 External sorting by merging 231 
10.2 External sorting with accelerator 238 
11 Graphs 243 
11.1 Class Graph 246 
11.1.1 Insertion of vertices and edges 248 
11.1.2 Analysis of a graph 249 
11.1.3 Input and output tools 253 
11.2 Dynamic priority queue 255 
11.2.1 Data structure 256 
11.2.2 Class dynamic_priority_queue 257 
11.3 Graph algorithms 263 
11.3.1 Shortest paths 264 
11.3.2 Topological sorting of a graph 269 
A Appendix 275 
A.1 Auxiliary programs 275 
A.1.1 Reading the thesaurus file roget.dat 275 
A.1.2 Reading a graph file 276 
A.1.3 Creation of vertices with random coordinates 277 
A.1.4 Connecting neighboring vertices 278 
A.1.5 Creating a LaTeX file 279 
A.2 Sources and comments 281 
A.3 Solutions to selected exercises 282 
A.4 Overview of the sample files 287 
References 291 
Index 293 

back