| Foreword | vii | ||
| Preface | ix | ||
| Part I Introduction | 1 | ||
| 1 The concept of the C++ Standard Template Library (STL) | 3 | ||
| 1.1 Genericity of components | 4 | ||
| 1.2 Abstract and implicit data types | 4 | ||
| 1.3 The fundamental concept | 5 | ||
| 1.3.1 Containers | 5 | ||
| 1.3.2 Iterators | 5 | ||
| 1.3.3 Algorithms | 6 | ||
| 1.3.4 Interplay | 6 | ||
| 1.4 Internal functioning | 9 | ||
| 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 | ||