Designing components with the C++ STL

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 and by drawing on his extensive experience and knowledge gained working with the C++ Standardization Committee. 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 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