Designing Components with the C++ STL: A New Approach to Programming (Revised Edition)

Foreword......Page 5
 Preface......Page 7
I Introduction......Page 17
The concept of the C++ Standard Template Library......Page 19
Abstract and implicit data types......Page 20
Iterators......Page 21
Interplay......Page 22
Internal functioning......Page 25
Complexity......Page 30
O notation......Page 31
 notation......Page 34
Pairs......Page 35
Comparison operators......Page 36
Function objects......Page 37
Function adapters......Page 40
Namespaces......Page 43
Allocators......Page 44
Iterators......Page 45
Standard iterator and traits classes......Page 46
Distances......Page 48
Categories......Page 49
Reverse iterators......Page 51
Tag classes......Page 52
Istream iterator......Page 53
Ostream iterator......Page 56
Data type interface......Page 61
Reversible containers......Page 62
Sequences......Page 63
Vector......Page 65
List......Page 68
showSequence......Page 72
Iterator categories and containers......Page 74
Derivation of value and distance types......Page 77
Iterators for insertion into containers......Page 79
Stack......Page 85
Queue......Page 86
Priority queue......Page 88
Sorted associative containers......Page 89
Set......Page 90
Map......Page 94
Multimap......Page 97
II Algorithms......Page 99
Copying algorithms......Page 101
Algorithms with predicates......Page 102
for_each......Page 103
find and find_if......Page 105
find_end......Page 106
find_first_of......Page 108
adjacent_find......Page 109
count and count_if......Page 110
mismatch......Page 111
equal......Page 114
search......Page 115
iota......Page 117
copy and copy_backward......Page 118
copy_if......Page 120
swap, iter_swap, and swap_ranges......Page 121
transform......Page 123
replace and variants......Page 125
fill and fill_n......Page 127
generate and generate_n......Page 128
remove and variants......Page 129
unique......Page 131
reverse......Page 132
rotate......Page 133
random_shuffle......Page 135
partition......Page 137
sort......Page 138
nth_element......Page 142
Binary search......Page 143
Merging......Page 146
includes......Page 150
set_union......Page 151
set_intersection......Page 152
set_difference......Page 153
set_symmetric_difference......Page 154
Conditions and limitations......Page 155
Heap algorithms......Page 157
pop_heap......Page 159
push_heap......Page 161
make_heap......Page 163
sort_heap......Page 164
Minimum and maximum......Page 166
Lexicographical comparison......Page 167
Permutations......Page 168
accumulate......Page 169
inner_product......Page 170
partial_sum......Page 172
adjacent_difference......Page 173
III Beyond the STL: components and applications......Page 175
Set operations on associative containers......Page 177
Union......Page 178
Intersection......Page 179
Symmetric difference......Page 180
Example......Page 181
Fundamentals......Page 185
Collision handling......Page 186
Map......Page 187
Example......Page 196
Set......Page 197
Union......Page 198
Symmetric difference......Page 199
Example......Page 200
Cross-reference......Page 201
Permuted index......Page 203
Thesaurus......Page 206
Checked vectors......Page 211
Matrices as nested containers......Page 213
Two-dimensional matrices......Page 214
Three-dimensional matrix......Page 218
Matrices for different memory models......Page 221
C memory layout......Page 224
FORTRAN memory layout......Page 225
Memory layout for symmetric matrices......Page 226
Sparse matrices......Page 227
Index operator and assignment......Page 230
Hash function for index pairs......Page 231
Class MatrixElement......Page 232
Class sparseMatrix......Page 234
Run time measurements......Page 237
External sorting by merging......Page 239
External sorting with accelerator......Page 246
Graphs......Page 251
Class Graph......Page 254
Insertion of vertices and edges......Page 256
Analysis of a graph......Page 257
Input and output tools......Page 261
Dynamic priority queue......Page 263
Class dynamic_priority_queue......Page 264
Graph algorithms......Page 270
Shortest paths......Page 272
Topological sorting of a graph......Page 276
Reading the thesaurus file roget.dat......Page 283
Reading a graph file......Page 284
Creation of vertices with random coordinates......Page 285
Connecting neighboring vertices......Page 286
Creating a LaTeX file......Page 287
Solutions to selected exercises......Page 289
Files for the standard algorithms......Page 297
Files for applications and extensions......Page 298
 Index......Page 301
 Contents......Page 11
 Index......Page 303