Hands-On Data Structures and Algorithms with Rust

Title Page......Page 2
Copyright and Credits......Page 3
Hands-On Data Structures and Algorithms with Rust......Page 4
About Packt......Page 5
Why subscribe?......Page 6
Packt.com......Page 7
Foreword......Page 8
Contributors......Page 10
About the author......Page 11
About the reviewer......Page 12
Packt is searching for authors like you......Page 13
Preface......Page 26
Who this book is for......Page 27
What this book covers......Page 28
To get the most out of this book......Page 30
Download the color images......Page 31
Download the example code files......Page 32
Conventions used......Page 33
Get in touch......Page 34
Reviews......Page 35
Hello Rust!......Page 36
Rust in 2018......Page 37
The 2018 edition......Page 38
The Rust language......Page 39
Objects and behavior......Page 40
Going wrong......Page 42
Macros......Page 44
Unsafe......Page 46
Borrowing and ownership......Page 48
Exceptional lifetimes......Page 53
Multiple owners......Page 55
Concurrency and mutability......Page 57
Immutable variables......Page 58
Shadowing......Page 59
Interior mutability......Page 60
Moving data......Page 62
Sharing data......Page 64
Send and Sync......Page 66
Deeper into Rust......Page 67
Requests for Comments (RFCs)......Page 68
Summary......Page 69
Questions......Page 70
Further reading......Page 71
Cargo and Crates......Page 72
Cargo......Page 73
Project configuration......Page 75
The manifest – Cargo.toml......Page 76
Package......Page 77
Profiles......Page 78
Dependencies......Page 79
Dependencies – Cargo.lock......Page 81
Commands......Page 82
The compile and run commands......Page 83
Testing......Page 84
Third-party subcommands......Page 87
Crates......Page 88
Rust libraries and binaries......Page 89
Static and dynamic libraries......Page 90
Linking and interoperability......Page 91
FFI......Page 92
Wasm......Page 93
The main repository – crates.io......Page 94
Publishing......Page 95
Summary......Page 96
Questions......Page 97
Further reading......Page 98
Storing Efficiently......Page 99
Heaps and stacks......Page 100
Sized and unsized......Page 101
Generics......Page 102
Accessing the box......Page 104
Copying and cloning......Page 106
Immutable storage......Page 107
States and reasoning......Page 108
Concurrency and performance......Page 109
Summary......Page 111
Questions......Page 112
Further reading......Page 113
Lists, Lists, and More Lists......Page 114
Linked lists......Page 115
A transaction log......Page 116
Adding entries......Page 119
Log replay......Page 121
After use......Page 123
Wrap up......Page 124
Upsides......Page 125
Downsides......Page 126
Doubly linked list......Page 127
A better transaction log......Page 129
Examining the log......Page 130
Reverse......Page 131
Wrap up......Page 132
Upsides......Page 135
Downsides......Page 136
Skip lists......Page 137
The best transaction log......Page 140
The list......Page 141
Adding data......Page 142
Leveling up......Page 144
Jumping around......Page 145
Thoughts and discussion......Page 147
Upsides......Page 150
Downsides......Page 151
Dynamic arrays......Page 152
Favorite transactions......Page 154
Internal arrays......Page 155
Quick access......Page 156
Wrap up......Page 158
Upsides......Page 159
Downsides......Page 160
Summary......Page 161
Questions......Page 163
Further reading......Page 164
Robust Trees......Page 165
Binary search tree......Page 166
IoT device management......Page 168
More devices......Page 169
Finding the right one......Page 171
Finding all devices......Page 172
Wrap up......Page 174
Upsides......Page 175
Downsides......Page 176
Red-black tree......Page 177
Better IoT device management......Page 182
Even more devices......Page 183
Balancing the tree......Page 185
Finding the right one, now......Page 188
Wrap up......Page 189
Upsides......Page 190
Downsides......Page 191
Heaps......Page 192
A huge inbox......Page 194
Getting messages in......Page 195
Taking messages out......Page 196
Wrap up......Page 197
Upsides......Page 198
Downsides......Page 199
Trie......Page 200
More realistic IoT device management......Page 202
Adding paths......Page 203
Walking......Page 204
Wrap up......Page 206
Upsides......Page 207
Downsides......Page 208
B-Tree......Page 209
An IoT database......Page 212
Adding stuff......Page 214
Searching for stuff......Page 217
Walking the tree......Page 218
Wrap up......Page 219
Upsides......Page 222
Downsides......Page 223
Graphs......Page 224
The literal Internet of Things......Page 228
Neighborhood search......Page 230
The shortest path......Page 232
Wrap up......Page 238
Upsides......Page 239
Downsides......Page 240
Summary......Page 241
Questions......Page 243
Exploring Maps and Sets......Page 244
Hashing......Page 245
Create your own......Page 247
Message digestion......Page 250
Wrap up......Page 252
Maps......Page 256
A location cache......Page 259
The hash function......Page 260
Adding locations......Page 261
Fetching locations......Page 262
Wrap up......Page 263
Upsides......Page 265
Downsides......Page 266
Sets......Page 267
Storing network addresses......Page 270
Networked operations......Page 272
Union......Page 274
Intersection......Page 275
Difference......Page 276
Wrap up......Page 277
Upsides......Page 278
Downsides......Page 279
Summary......Page 280
Questions......Page 282
Further reading......Page 283
Collections in Rust......Page 284
Sequences......Page 285
Vec and VecDeque......Page 286
Architecture......Page 287
Insert......Page 289
Look up......Page 290
Remove......Page 294
LinkedList......Page 295
Architecture......Page 297
Insert......Page 298
Look up......Page 300
Remove......Page 302
Wrap up......Page 303
Maps and sets......Page 304
HashMap and HashSet......Page 305
Architecture......Page 306
Insert......Page 307
Lookup......Page 309
Remove......Page 310
BTreeMap and BTreeSet......Page 311
Architecture......Page 312
Insert......Page 313
Look up......Page 315
Remove......Page 316
Wrap up......Page 317
Summary......Page 319
Questions......Page 320
Further reading......Page 321
Algorithm Evaluation......Page 322
The Big O notation......Page 323
Other people's code......Page 324
The Big O......Page 325
Asymptotic runtime complexity......Page 326
Making your own......Page 327
Loops......Page 328
Recursion......Page 329
Complexity classes......Page 330
O(1)......Page 331
O(log(n))......Page 332
O(n)......Page 333
O(n log(n))......Page 334
O(n²)......Page 335
O(2n)......Page 336
Comparison......Page 337
In the wild......Page 338
Data structures......Page 339
Everyday things......Page 340
Exotic things......Page 341
Summary......Page 342
Questions......Page 343
Further reading......Page 344
Ordering Things......Page 345
From chaos to order......Page 346
Bubble sort......Page 347
Shell sort......Page 352
Heap sort......Page 356
Merge sort......Page 359
Quicksort......Page 363
Summary......Page 369
Questions......Page 371
Further reading......Page 372
Finding Stuff......Page 373
Finding the best......Page 374
Linear searches......Page 375
Jump search......Page 376
Binary searching......Page 378
Wrap up......Page 380
Summary......Page 383
Questions......Page 384
Further reading......Page 385
Random and Combinatorial......Page 386
Pseudo-random numbers......Page 387
LCG......Page 393
Wichmann-Hill......Page 397
The rand crate......Page 401
Back to front......Page 402
Packing bags or the 0-1 knapsack problem......Page 403
N queens......Page 406
Advanced problem solving......Page 411
Dynamic programming......Page 412
The knapsack problem improved......Page 413
Metaheuristic approaches......Page 418
Example metaheuristic – genetic algorithms......Page 419
Summary......Page 422
Questions......Page 423
Further reading......Page 424
Algorithms of the Standard Library......Page 425
Slicing and iteration......Page 426
Iterator......Page 427
Slices......Page 429
Search......Page 430
Linear search......Page 431
Binary search......Page 432
Sorting......Page 434
Stable sorting......Page 435
Unstable sorting......Page 439
Summary......Page 442
Questions......Page 443
Further reading......Page 444
Assessments......Page 445
Chapter 1......Page 446
Chapter 2......Page 448
Chapter 3......Page 450
Chapter 4......Page 451
Chapter 5......Page 453
Chapter 6......Page 455
Chapter 7......Page 457
Chapter 8......Page 458
Chapter 9......Page 459
Chapter 10......Page 460
Chapter 11......Page 462
Chapter 12......Page 463
Other Books You May Enjoy......Page 464
Leave a review - let other readers know what you think......Page 466