Designing components with the C++ STL

Ulrich Breymann0-201-67488-2

‘This book is the most accurate and up-to-date source of information on the STL currently available…It has an approach and appeal of its own: it explains techniques for building data structures and algorithms on top of the STL, and in this way appreciates the STL for what it is – a framework.’ – Angelika Langer, Independent Consultant and C++ Report Columnist”A superbly authored treatment of the STL…an excellent book which belongs in any serious C++ developer’s library. – Jim Armstrong, President 2112 F/X, Texas.The C++ Standard Template Library (STL) represents a breakthrough in C++ programming techniques. With it, software developers can achieve vast improvements in the reliability of their software, and increase their own productivity. Designing Components with the C++ STL has three aims: to introduce the reader to the STL to show how this powerful resource can be exploited to extend its use to the construction of new components.This revised edition is fully compliant with the new ISO/IEC C++ Standard with an associated web site containing numerous, fully up-to-date examples for downloading.The author shows how to make practical use of the STL through a wealth of examples a Unique insight into the internals of the STL takes the reader beyond simply using it, to show how the components supplied in the STL can be used to design more complex data structures and algorithms, and powerful abstract data types. Throughout, the author maintains an elegant and sophisticated coding style, adhering faithfully to the current ISO/ANSI standards, helping to ensure that your software will be even more portable, maintainable and reusable than ever.

---

Table of contents :
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