Hands-On Data Structures and Algorithms with Rust

Description

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