Farrier John / Фарриер Джон - Data Structures and Algorithms with the C++ STL / Структуры данных и алгоритмы на C++ STL [2024, PDF/EPUB, ENG]

Preface xxiii
Part 1: Mastering std::vector
1
The Basics of std::vector 3
Technical requirements 3
The significance of std::vector 3
A basic comparison of C-style arrays and std::vector 4
Comparison of C-style arrays and std::vector for memory management 7
Declaring and initializing std::vector 9
Declaring a vector 9
Initializing a vector 10
Accessing elements 13
Random access 13
Accessing the first and last elements 15
Vector size 15
Adding and removing elements 17
Adding elements 17
Removing elements 19
Capacity 21
Prefer using empty() when possible 22
Clearing all elements 22
Summary 24
2
Mastering Iterators with std::vector 27
Technical requirements 27
Types of iterators in the STL 27
Input iterators 28
Output iterators 28
Forward iterators 29
Reverse iterators 30
Bidirectional iterators 30
Random access iterators 31
Basic iteration techniques with std::vector 33
Iterating over std::vector 33
Basic iteration using iterators 33
Using constant iterators 34
Benefits of iteration 34
Table of Contents
Using std::begin and std::end 35
Understanding iterator requirements 37
Range-based for loops 38
Overview of range-based for loops 38
When to use range-based for loops 39
Modifying elements during iteration 39
Creating a custom iterator 40
The appeal of custom iterators 40
Core requirements 40
Iterator categories and their specialties 41
A custom iterator example 43
Custom iterator challenges and use cases 45
Illustrative use cases of custom iterators 45
Summary 49
3
Mastering Memory and Allocators with std::vector 51
Technical requirements 51
Understanding capacity versus size 51
Revisiting the basics 52
What exactly is capacity? 52
Why this distinction matters 52
Looking under the hood 53
Resizing and reserving memory 55
The power of resize() 55
Enter reserve() 57
Optimizing with shrink_to_fit() 58
Real-world relevance 60
Custom allocator basics 60
The role and responsibility of an allocator 60
Under the hood – the allocator interface 61
Trade-offs and the need for custom allocators 63
Choosing std::allocator over new, delete, and
managed pointers 64
Creating a custom allocator 65
Custom allocators – the heart of
memory flexibility 65
Understanding the motivation behind
custom allocators 66
Memory pools – a popular custom
allocator strategy 66
Unlocking the potential of custom allocators 66
Allocators and container performance 67
Why allocators matter in performance 67
The performance characteristics of
std::allocator 67
When to consider alternative allocators 68
Profiling – the key to making
informed decisions 68
Summary 68
4
Mastering Algorithms with std::vector 71
Technical requirements 71
Sorting a vector 71
Getting started with std::sort 72
The engine under the hood – introsort 72
Efficiency unparalleled – O(n log n) 72
Sorting in descending order 72
Sorting custom data types 73
Pitfalls and precautions 74
Searching elements 77
Linear search with std::find 77
Binary search techniques 77
Using std::lower_bound and std::upper_bound 78
Binary search versus linear search – efficiency
and versatility 79
Manipulating vectors 80
Transforming with std::copy 81
Reversing elements with std::reverse 81
Rotating vectors with std::rotate 81
Filling a vector with std::fill 82
Putting manipulation to use 82
Considerations in manipulation 84
Custom comparators and predicates 85
Understanding comparators 85
The power of predicates 85
Crafting effective comparators and predicates 86
User-defined structs and classes 86
Understanding container invariants
and iterator invalidation 87
Understanding iterator invalidation 87
Strategies to counteract invalidation 89
Dealing with invalidation in
multi-threaded scenarios 91
Summary 93
5
Making a Case for std::vector 95
Performance considerations 95
Comparison with other containers 96
The memory advantage 96
The takeaway 96
Practical use cases 97
A resizable dynamic array at heart 97
Data processing and analytics 97
Graphics and game development 97
Beyond just containers 97
Versatility and efficiency 98
A testament to versatility 98
Efficiency isn’t just about speed 98
A safe default, but not the only option 98
Summary 99
Part 2: Understanding STL Data Structures
6
Advanced Sequence Container Usage 103
Technical requirements 104
std::array 104
Purpose and suitability 104
Ideal use cases 104
Performance 105
Memory management 106
Thread safety 106
Extensions and variants 106
Sorting and searching complexity 106
Interface and member functions 106
Comparisons 106
Interactions with algorithms 106
Exceptions 106
Customization 107
Example 107
Best practices 109
std::vector 109
Purpose and suitability 110
Ideal use cases 110
Performance 111
Memory management 111
Thread safety 111
Extensions and variants 111
Sorting and searching complexity 112
Special interface and member functions 112
Comparisons 112
Interactions with algorithms 112
Exceptions 112
Customization 112
Example 112
Best practices 116
std::deque 117
Purpose and suitability 117
Ideal use cases 117
Performance 118
Memory management 118
Thread safety 118
Extensions and variants 119
Sorting and searching complexity 119
Interface and member functions 119
Comparisons 119
Interactions with algorithms 119
Exceptions 119
Customization 119
Example 120
Best practices 122
std::list 122
Purpose and suitability 123
Ideal use cases 123
Performance 124
Memory management 124
Thread safety 124
Extensions and variants 125
Sorting and searching complexity 125
Interface and member functions 125
Comparisons 125
Interactions with algorithms 125
Exceptions 125
Customization 125
Example 126
Best practices 127
std::forward_list 128
Purpose and suitability 128
Ideal use cases 129
Performance 129
Memory management 130
Thread safety 130
Extensions and variants 130
Sorting and searching complexity 130
Special interface and member functions 130
Comparisons 130
Interactions with algorithms 131
Exceptions 131
Customization 131
Example 131
Best practices 133
std::string 134
Purpose and suitability 134
Ideal use cases 135
Performance 135
Memory management 135
Thread safety 135
Extensions and variants 135
Sorting and searching complexity 135
Special interface and member functions 136
Comparisons 136
Interactions with algorithms 136
Exceptions 136
Customization 136
Example 136
Best practices 138
7
Advanced Ordered Associative Container Usage 141
Technical requirements 141
std::set 142
Purpose and suitability 142
Ideal use cases 142
Performance 143
Memory management 143
Thread safety 143
Extensions and variants 143
Sorting and searching complexity 143
Special interface and member functions 144
Comparisons 144
Interactions with algorithms 144
Exceptions 144
Customization 144
Example 144
Best practices 146
std::map 147
Purpose and suitability 147
Ideal use cases 148
Performance 148
Memory management 149
Thread safety 149
Extensions and variants 149
Sorting and searching complexity 149
Special interface and member functions 149
Comparisons 149
Interactions with algorithms 150
Exceptions 150
Customization 150
Example 150
Best practices 152
std::multiset 153
Purpose and suitability 153
Ideal use cases 153
Performance 154
Memory management 154
Thread safety 155
Extensions and variants 155
Sorting and searching complexity 155
Special interface and member functions 155
Comparisons 155
Interactions with algorithms 155
Exceptions 155
Customization 156
Example 156
Best practices 158
std::multimap 158
Purpose and suitability 158
Ideal use cases 159
Performance 160
Memory management 160
Thread safety 160
Extensions and variants 160
Sorting and searching complexity 160
Special interface and member functions 160
Comparisons 161
Interactions with algorithms 161
Exceptions 161
Customization 161
Example 161
Best practices 163
8
Advanced Unordered Associative Container Usage 165
Technical requirements 165
std::unordered_set 166
Purpose and suitability 166
Ideal use cases 166
Performance 167
Memory management 167
Thread safety 167
Extensions and variants 167
Sorting and searching complexity 167
Special interface and member functions 167
Comparisons 168
Interactions with algorithms 168
Exceptions 168
Customization 168
Example 168
Best practices 170
std::unordered_map 171
Purpose and suitability 171
Ideal use cases 172
Performance 173
Memory management 173
Thread safety 173
Extensions and variants 173
Sorting and searching complexity 173
Special interface and member functions 173
Comparisons 174
Interactions with algorithms 174
Exceptions 174
Customization 174
Example 174
Best practices 176
std::unordered_multiset 177
Purpose and suitability 177
Ideal use cases 177
Performance 178
Memory management 178
Thread safety 178
Extensions and variants 179
Sorting and searching complexity 179
Special interface and member functions 179
Comparisons 179
Interactions with algorithms 179
Exceptions 179
Customization 179
Example 180
Best practices 182
std::unordered_multimap 183
Purpose and suitability 183
Ideal use cases 183
Performance 184
Memory management 184
Thread safety 185
Extensions and variants 185
Sorting and searching complexity 185
Special interface and member functions 185
Comparisons 185
Interactions with algorithms 185
Exceptions 185
Customization 186
Example 186
Best practices 188
9
Advanced Container Adaptor Usage 191
Technical requirements 191
std::stack 191
Purpose and suitability 192
Ideal use cases 192
Performance 192
Memory management 193
Thread safety 193
Extensions and variants 193
Sorting and searching complexity 193
Special interface and member functions 193
Comparisons 193
Interactions with algorithms 193
Exceptions 193
Customization 194
Example 194
Best practices 196
std::queue 197
Purpose and suitability 197
Ideal use cases 197
Performance 198
Memory management 198
Thread safety 198
Extensions and variants 198
Sorting and searching complexity 198
Special interface and member functions 198
Comparisons 198
Interactions with algorithms 199
Exceptions 199
Customization 199
Example 199
Best practices 201
std::priority_queue 202
Purpose and suitability 202
Ideal use cases 202
Performance 202
Memory management 203
Thread safety 203
Extensions and variants 203
Sorting and searching complexity 203
Special interface and member functions 203
Comparisons 203
Interactions with algorithms 204
Exceptions 204
Customization 204
Example 204
Best practices 206
std::flat_set 207
Purpose and suitability 208
Ideal use cases 208
Performance 208
Memory management 209
Thread safety 209
Extensions and variants 209
Sorting and searching complexity 209
Special interface and member functions 209
Comparisons 209
Interactions with algorithms 209
Exceptions 210
Customization 210
Best practices 210
std::flat_map 211
Purpose and suitability 211
Ideal use cases 212
Performance 212
Memory management 212
Thread safety 212
Extensions and variants 212
Sorting and searching complexity 213
Interface and member functions 213
Comparisons 213
Interactions with algorithms 213
Exceptions 213
Customization 213
Best practices 213
std::flat_multiset 214
Purpose and suitability 214
Ideal use cases 215
Performance 215
Memory management 215
Thread safety 216
Extensions and variants 216
Sorting and searching complexity 216
Special interface and member functions 216
Comparisons 216
Interactions with algorithms 216
Exceptions 216
Customization 217
Best practices 217
std::flat_multimap 218
Purpose and suitability 218
Ideal use cases 218
Performance 219
Memory management 219
Thread safety 219
Extensions and variants 219
Sorting and searching complexity 219
Interface and member functions 219
Comparisons 220
Interactions with algorithms 220
Exceptions 220
Customization 220
Best practices 220
10
Advanced Container View Usage 223
Technical requirements 223
std::span 223
Purpose and suitability 224
Ideal use cases 224
Performance 224
Memory management 224
Thread safety 225
Extensions and variants 225
Sorting and searching complexity 225
Interface and member functions 225
Comparisons 225
Interactions with algorithms 225
Exceptions 225
Customization 225
Example 226
Best practices 228
std::mdspan 228
Purpose and suitability 229
Ideal use cases 229
Performance 229
Memory management 229
Thread safety 230
Extensions and variants 230
Sorting and searching complexity 230
Special interface and member functions 230
Comparisons 230
Interactions with algorithms 230
Exceptions 230
Customization 230
Best practices 231
Part 3: Mastering STL Algorithms
11
Fundamental Algorithms and Searching 235
Technical requirements 235
Sorting 235
Checking conditions 237
Counting and finding 240
Searching and comparison 246
Best practices 250
Summary 252
12
Manipulation and Transformation 253
Technical requirements 253
Copying and moving in
STL containers 253
Copying semantics in the STL 254
Moving semantics in the STL 254
Copying versus moving – a deliberate choice 254
Exploring return value optimization 256
Filling and generating in
STL containers 257
Populating with static assignment 257
Dynamic generation with the STL 257
Ensuring relevance and efficiency 258
Removing and replacing in STL
containers 258
The essence of removal 259
Replacement 259
A balancing act 260
Swapping and reversing in
STL containers 261
Swapping – the art of interchanging 261
Reversing – a glimpse from the end 261
Deduplication – singling out the unique 261
Sampling – a slice of the whole 261
Best practices 262
Summary 263
13
Numeric and Range-Based Operations 265
Technical requirements 265
Basic numeric operations 265
Generating sequences with std::iota 266
Summing elements with std::accumulate 267
Adjacent elements and their interactions with
std::adjacent_difference 268
Inner products with std::inner_product 270
Advanced numeric operations 271
Operations on sorted ranges 273
Best practices 276
Summary 277
14
Permutations, Partitions, and Heaps 279
Technical requirements 279
Partitioning 279
std::partition and its power 280
Checking partitions with std::is_partitioned 280
The utility of std::partition_point 280
Partitioning beyond basic sequences 280
Permutations 281
Generating permutations with std::next_
permutation 282
Predecessor permutations with std::prev_
permutation 282
Shuffling elements randomly with std::shuffle 282
Rotating sequences with std::rotate 283
Heap operations 284
Constructing heaps with std::make_heap 285
Adding and removing elements – std::push_
heap and std::pop_heap 285
Heap-based sorting – the power of std::sort_
heap 285
Checking heap validity with std::is_heap 286
The significance of heaps in today’s computing 286
Best practices 287
Summary 288
15
STL with Ranges 289
Technical requirements 289
Introduction to ranges 289
Understanding the essence of ranges 290
Why the shift to ranges? 290
A glimpse into range operations 290
Looking ahead – the power of modern STL 291
Ranges for sorting algorithms 291
Traditional STL sorting – a recap 292
Range-based sorting – the basics 292
Embracing composability in sorting 292
Advantages beyond syntax – why ranges shine
in sorting 293
The revolution of ranges in sorting 294
Ranges for searching algorithms 294
Finding elegance – range-based searching 295
Chaining and filtering – the beauty of
composability 295
Understanding views in searches 296
The extended toolkit – more than just find 296
Best practices 297
Embracing the power of chaining 297
Guarding against range pitfalls – lifetime
awareness 297
Performance considerations – laziness and
evaluation 298
Readability over brevity – striking the balance 298
Adhering to range idioms – keep it standard 298
Summary 299
Part 4: Creating STL-Compatible Types
and Algorithms
16
Creating STL-Types Containers 303
Technical requirements 303
The advantages of
STL-compatible types 303
One language, one approach 304
Reusability – the gift that keeps giving 304
Efficiency in the familiar 304
Paving the way forward 305
Interacting with STL algorithms 305
The centrality of iterators 305
Adapting to algorithmic expectations 306
Error handling and feedback mechanisms 306
Algorithmic efficiency and your type 308
Laying a solid foundation 308
Essential requirements
for compatibility 308
The cornerstones of compatibility 309
The vitality of iterators 309
Embracing value semantics 309
Operational guarantees 309
Size and capacity queries 309
Element access and manipulation 310
Consistency in exception safety 310
Looking forward to enhanced integration 312
Crafting iterators for custom types 312
Choosing the right iterator type 312
Crafting the basic components 313
Addressing iterator categories with type traits 313
End iterators – signifying the finish line 313
Considerations for const iterators 313
Performance optimizations and
advanced techniques 315
Embracing the iterative spirit 315
Effective operator overloading 316
Operator overloading in C++ 316
Considerations in overloading 316
Implementing arithmetic operators for
custom types 316
Overloading relational operators for
clear comparisons 317
Simplifying tasks with assignment and
compound assignment 319
Stream operators for efficient I/O 319
Operator precedence and associativity
in overloading 319
The role of operator overloading in C++ 319
Creating custom hash functions 319
Interoperability with STL containers 319
Custom type semantics 320
The characteristics of a good hash function 320
Example for the creation of a custom
hash function 321
Summary 323
17
Creating STL-Compatible Algorithms 325
Technical requirements 325
Template functions 325
A primer on function templates 326
Variadic templates – multiplicity in templates 326
SFINAE – fine-tuning template substitution 326
Harnessing SFINAE with std::enable_if 326
Overloading 329
Crafting multiple algorithm versions for
STL containers 329
Function resolution – navigating the intricacies 329
Overloading with care – clarity and consistency 330
Creating generic algorithms 330
Toward a type-independent approach 331
Embracing iterators – the bridge to generics 331
Predicates – customizing algorithm behavior 331
The magic of functors – enhancing flexibility 332
Customizing existing algorithms 332
Looking at the decorator pattern in action 333
Harnessing the power of lambda functions 335
Mixing patterns with lambdas for
ultimate customization 335
Summary 338
18
Type Traits and Policies 339
Technical requirements 339
Understanding and using type traits 339
Enhancing code adaptability with type traits 340
Empowering metaprogramming with
type traits 340
Toward more informed and adaptable code 340
Utilizing type traits with the STL 341
Working with data types 341
Working with algorithms 342
Understanding and using policies in
C++ 345
Benefits with respect to the STL 345
Building modular components using policies 347
Potential challenges 347
The role of policies in modern C++ 347
Using policies with the STL 348
Memory allocation policies 348
Sorting policies for versatile algorithms 348
Fine-tuning data structures with policies 349
Summary 350
Part 5: STL Data Structures and Algorithms:
Under the Hood
19
Exception Safety 355
Technical requirements 355
Basic exception safety 355
The pivotal role of program invariants in
the STL 356
Resource integrity – the guardian of
robust software 357
Harnessing the STL for basic exception safety 357
Strong exception safety 358
Navigating STL containers with
strong guarantees 358
Crafting custom STL containers with strong
guarantees 358
Infusing exception safety into custom
STL algorithms 362
Exception safety is the path to
robust applications 362
The effect of noexcept on
STL operations 363
An introduction to noexcept 363
Application to STL data types 363
Application to STL algorithms 363
Summary 364
20
Thread Safety and Concurrency with the STL 365
Technical requirements 366
Concurrency versus thread safety 366
Thread safety – a pillar for stable concurrency 366
The interplay of concurrency and thread safety 366
Challenges and rewards 367
Concurrency without thread safety – a recipe
for chaos 367
Understanding thread safety 367
Thread safety in STL containers – laying the
groundwork 367
Grasping the thread-safe nature of STL
algorithms 368
Race conditions – the ghosts in the machine 368
Safeguarding concurrency – the way forward 369
Race conditions 370
Steering clear of a silent peril – race
conditions in the STL 370
The anatomy of a race condition in the STL 370
More than meets the eye 370
Anticipating race conditions 371
Safeguarding your code – a proactive stance 371
Mutexes and locks 371
From manual to automatic – lock guards and
unique locks 372
Avoiding the stalemate – deadlock prevention 372
Incorporating mutexes with STL containers 372
STL containers and thread safety 373
When safety needs reinforcements –
concurrent modifications 373
Container iterators – the fragile bridge 373
Containers with a built-in
shield – concurrent containers 373
Specific container concerns 374
Behaviors of std::vector in multi-threading 374
Characteristics of std::list in concurrency 374
Considerations with associative containers 375
Concurrency aspects of unordered containers 375
Insights into container adaptors 375
Concurrency support within the STL 375
Introduction to threads 376
The advent of asynchronous tasks 376
Atomic operations 376
Potential concurrent challenges 377
Using the STL’s concurrency features 377
Using std::thread, std::async,
std::future, and thread-local storage 380
Initiating threads using std::thread 380
Managing asynchronous operations with
std::async and std::future 380
Preserving data consistency using threadlocal
storage 381
Integrating tools for proficient concurrency 381
Concurrent data structures in the STL 383
The STL’s concurrency-optimized containers 383
Striving for maximum efficiency in
concurrent environments 384
Best practices in action 384
Summary 387
21
STL Interaction with Concepts and Coroutines 389
Technical requirements 389
Concepts 390
A brief introduction to concepts 390
Refined constraints in STL algorithms 390
Effectively constraining templates 390
Enhanced data structures with
explicit requirements 393
Custom concepts and STL interactions 393
Potential challenges and caveats 394
Coroutines 395
Understanding coroutines – a refresher 395
STL algorithms and coroutine integration 396
Coroutines and STL data structures 396
Potential synergies with ranges and views 396
Looking ahead – a paradigm shift 399
Summary 400
22
Parallel Algorithms with the STL 401
Technical requirements 401
Introduction to execution policies 401
The <execution> header– enabling
parallelism in STL algorithms 402
Implementing parallel execution 402
Reflecting on the transition to parallel STL 402
Incorporating execution policies 403
Integrating policies with standard algorithms 403
Understanding parallel execution policies 404
Selecting the appropriate execution policy 404
The impact of constexpr on
algorithms and containers 405
Evolution of constexpr 405
Algorithms and the role of constexpr 405
Containers and constexpr integration 406
Performance considerations 407
Parallelism overhead 407
Determining optimal data size 407
Data access and synchronization challenges 407
False sharing – a subtle performance issue 408
Load balancing 408
The importance of profiling 408
Summary 409
Index 411
Other Books You May Enjoy 426