Search icon CANCEL
Subscription
0
Cart icon
Your Cart (0 item)
Close icon
You have no products in your basket yet
Arrow left icon
Explore Products
Best Sellers
New Releases
Books
Videos
Audiobooks
Learning Hub
Newsletter Hub
Free Learning
Arrow right icon
timer SALE ENDS IN
0 Days
:
00 Hours
:
00 Minutes
:
00 Seconds
Hands-On Data Structures and Algorithms with Rust
Hands-On Data Structures and Algorithms with Rust

Hands-On Data Structures and Algorithms with Rust: Learn programming techniques to build effective, maintainable, and readable code in Rust 2018

eBook
$23.99 $29.99
Paperback
$35.19 $43.99
Subscription
Free Trial
Renews at $12.99p/m

What do you get with a Packt Subscription?

Free for first 7 days. $15.99 p/m after that. Cancel any time!
Product feature icon Unlimited ad-free access to the largest independent learning library in tech. Access this title and thousands more!
Product feature icon 50+ new titles added per month, including many first-to-market concepts and exclusive early access to books as they are being written.
Product feature icon Innovative learning tools, including AI book assistants, code context explainers, and text-to-speech.
Product feature icon Thousands of reference materials covering every tech concept you need to stay up to date.
Subscribe now
View plans & pricing
Table of content icon View table of contents Preview book icon Preview Book

Hands-On Data Structures and Algorithms with Rust

Cargo and Crates

Rust is a rather young language that has been designed from scratch to be a practical and useful tool for programmers. This is a great situation to be in: there are no legacy applications to care about, and many lessons learned from other languages have been incorporated in Rust—especially around tooling.

Integrating and managing third-party packages has been an issue in the past for a lot of languages, and there are a few different approaches out there:

  • NPM: The package manager for Node, which has been very popular with the JavaScript community
  • Maven: Enterprise-grade Java package management, based on the XML format
  • NuGet: .NET's package management
  • PyPI: The Python package index

Each of these has different styles of configuration, naming guidelines, publishing infrastructure, features, plugins, and so on. The Rust team learned from all of these...

Cargo

The basic Rust tooling is composed of three programs:

  • cargo: The Rust package manager
  • rustc: The Rust compiler
  • rustup: The Rust toolchain manager

Most users will never touch (or even see) rustc directly, but will usually use rustup to install it and then let cargo orchestrate the compilation.

Running cargo without any arguments reveals the subcommands it provides:

$ cargo
Rust's package manager

USAGE:
cargo [OPTIONS] [SUBCOMMAND]

OPTIONS:
-V, --version Print version info and exit
--list List installed commands
--explain <CODE> Run `rustc --explain CODE`
-v, --verbose Use verbose output (-vv very verbose/build.rs output)
-q, --quiet No output printed to stdout
--color <WHEN> Coloring: auto, always, never
--frozen Require Cargo.lock and cache are up to date
--locked Require Cargo.lock is up to date
-Z <FLAG>... Unstable...

Project configuration

In order to recognize a Rust project, cargo requires its manifest to be present, where most of the other aspects (metadata, source code location, and so on) can be configured. Once this has been done, building the project will create another file: Cargo.lock. This file contains the dependency tree of a project with library versions and locations in order to speed up future builds. Both of these files are essential to a Rust project.

The manifest Cargo.toml

The Cargo.toml file follows—as the name suggests—the TOML structure. It's handwritten and contains metadata about the project as well as dependencies, links to other resources, build profiles, examples, and much more. Most of them are optional and have reasonable defaults. In fact, the cargo new command generates the minimal version of a manifest:

[package]
name = "ch2"
version = "0.1.0"
authors = ["Claus Matzinger"]
edition = "2018"

[dependencies]

There are many more sections and properties, and we will present a few important ones here.

Package

This manifest section is all about metadata for the package, such as name, version, and authors, but also a link to the documentation that defaults to the corresponding page (https://docs.rs/). While many of these fields are there to support crates.io and display various indicators (categories, badges, repository, homepage, and so on), some fields should be filled regardless of whether they are published there, such as license (especially with open source projects).

Another interesting section is the metadata table in package.metadata, because it's ignored by cargo. This means that projects can store their own data in the manifest for project- or publishing-related properties—for example, for publishing on Android's Google Play Store, or information to generate Linux packages.

Profiles

When you run cargo build, cargo build --release, or cargo test, cargo uses profiles to determine individual settings for each stage. While these have reasonable defaults, you might want to customize some settings. The manifest provides these switches with the [profile.dev], [profile.release], [profile.test], and [profile.bench] sections:

[profile.release] 
opt-level = 3
debug = false
rpath = false
lto = false
debug-assertions = false
codegen-units = 16
panic = 'unwind'
incremental = false
overflow-checks = false

These values are the defaults (as of writing this book) and are already useful for most users.

Dependencies

This is probably the most important section for most developers. The dependencies section contains a list of values that represent crate names on crates.io (or your configured private registry) as keys along with the version as values.

Instead of the version string, it's equally possible to provide an inline table as a value that specifies optionality or other fields:

[dependencies]
hyper = "*"
rand
= { version = "0.5", optional = true }

Interestingly, since this is an object, TOML allows us to use it like a section:

[dependencies]
hyper
= "*"

[dependencies.rand]

version = "0.5"
features = ["stdweb"]

Since, in the 2018 edition, the extern crate declarations inside the .rs files are optional, renaming a dependency can be done inside the Cargo.toml specification by using the package property. Then, the specified key can become an alias for this package, like this:

[dependencies]
# import in Rust with "use web::*"
web...

Dependencies Cargo.lock

Here is a great quote from the cargo FAQ (https://doc.rust-lang.org/cargo/faq.html) about what the purpose of this file is and what it does:

The purpose of a Cargo.lock is to describe the state of the world at the time of a successful build. It is then used to provide deterministic builds across whatever machine is building the project by ensuring that the exact same dependencies are being compiled.

This serialized state can easily be transferred across teams or computers. Therefore, should a dependency introduce a bug with a patch update, your build should be largely unaffected unless you run cargo update. In fact, it's recommended for libraries to commit the Cargo.lock file to version control to retain a stable, working build. For debugging purposes, it's also quite handy to streamline the dependency tree.

Commands

cargo supports a wealth of commands that can be extended easily. It deeply integrates with the project and allows for additional build scripts, benchmarking, testing, and so on.

The compile and run commands

As the main build tool, cargo does compile and run by way of creating and then executing the output binary (usually found in target/<profile>/<target-triple>/).

What if a library written in a different language is required to precede the Rust build? This is where build scripts come in. As mentioned in the Project configuration section, the manifest provides a field called build which takes a path or name to a build script.

The script itself can be a regular Rust binary that generates output in a designated folder, and can even have dependencies specified in Cargo.toml ([build-dependencies], but nothing else). Any required information (target architecture, output, and so on) is passed into the program using environment variables, and any output for cargo is required to have the cargo:key=value format. Those are picked up by cargo to configure further steps. While the most popular is building native dependencies, it's entirely possible to generate...

Testing

As far as commands go, cargo supports test and bench to run a crate's tests. These tests are specified in the code by creating a "module" inside a module and annotating it with #[cfg(test)]. Furthermore, each test also has to be annotated with either #[test] or #[bench], whereas the latter takes an argument to the Bencher, a benchmark runner class that allows us to collect stats on each run:

#![feature(test)] 
extern crate test;

pub fn my_add(a: i32, b: i32) -> i32 {
a + b
}

#[cfg(test)]
mod tests {
use super::*;
use test::Bencher;

#[test]
fn this_works() {
assert_eq!(my_add(1, 1), 2);
}

#[test]
#[should_panic(expected = "attempt to add with overflow")]
fn this_does_not_work() {
assert_eq!(my_add(std::i32::MAX, std::i32::MAX), 0);
}

#[bench]
fn how_fast(b: &mut Bencher) {
b.iter(|| my_add(42, 42))
}
}

After running cargo test, the output is as expected:

Finished dev [unoptimized...

Third-party subcommands

cargo allows the extension of its command-line interface with subcommands. These subcommands are binaries that are called when invoking cargo <command> (for example, cargo clippy for the popular linter).

In order to install a new command (for a particular toolchain), run cargo +nightly install clippy, which will download, compile, and install a crate called cargo-clippy and then put it into the .cargo directory in your home folder. In fact, this will work with any binary that is called cargo-<something> and is executable from any command line. The cargo project keeps an updated list of some useful subcommands in the repository at https://github.com/rust-lang/cargo/wiki/Third-party-cargo-subcommands.

Crates

Rust's modules (crates) can easily be packaged and distributed once all the compilation and testing is done, regardless of whether they are libraries or executables. First, let's take a look at Rust binaries in general.

Rust libraries and binaries

There are executable binaries and libraries in Rust. When these Rust programs use dependencies, they rely on the linker to integrate those so it will work on—at least—the current platform. There are two major types of linking: static and dynamic—both of which are somewhat dependent on the operating system.

Static and dynamic libraries

Generally, Rust dependencies have two types of linking:

  • Static: Via the rlib format.
  • Dynamic: Via shared libraries (.so or .dll).

The preference—if a corresponding rlib can be found—is to link statically and therefore include all dependencies into the output binary, making the file a lot larger (to the dismay of embedded programmers). Therefore, if multiple Rust programs use the same dependency, each comes with its own built-in version. It's all about the context though, since, as Go's success has shown, static linking can simplify complex deployments since only a single file has to be rolled out.

There are drawbacks to the static linking approach beyond size: for static libraries, all dependencies have to be of the rlib type, which is Rust's native package format, and cannot contain a dynamic library since the formats (for example, .so (dynamic) and .a (static) on ELF systems) aren't convertible.

For Rust, dynamic linking...

Linking and interoperability

Rust compiles to native code like many other languages, which is great because it expands the available libraries and lets you choose the best technology to solve a problem. "Playing nice with others" has always been a major design goal of Rust.

Interoperability on that level is as simple as declaring the function that you want to import and dynamically linking a library that exports this function. This process is largely automated: the only thing required is to create and declare a build script that compiles the dependency and then tells the linker where the output is located. Depending on what type of library you built, the linker does what is necessary to include it into the Rust program: static or dynamic linking (the default).

If there is only one native library that is to be linked dynamically, the manifest file offers a links property to specify that. Programmatically, it's very easy to interact with these included libraries by using...

FFI

The Foreign Function Interface (FFI) is Rust's way of calling into other native libraries (and vice versa) using a simple keyword: extern. By declaring an extern function, the compiler knows that, either an outside interface needs to be bound via the linker (import) or, that the declared function is to be exported so other languages can make use of it (export).

In addition to the keyword, the compiler and linker have to get a hint of what type of binary layout is expected. That's why the usual extern declaration looks as follows:

extern "C" {
fn imported_function() -> i32;
}

#[no_mangle]
pub extern "C" fn exported_function() -> i32 {
42
}

This allows a C library function to be called from within Rust. However, there's one caveat: the calling part has to be wrapped in an unsafe section. The Rust compiler cannot guarantee the safety of an external library so it makes sense to be pessimistic about its memory management. The exported function...

Wasm

Wasm, which WebAssembly is now commonly called, is a binary format meant to complement JavaScript that Rust can be compiled to. The format is designed to run as a stack machine inside several sandboxed execution environments (such as web browsers, or the Node.js runtime) for performance-critical applications (https://blog.x5ff.xyz/blog/azure-functions-wasm-rust/). While this is—as of this writing—in its early stages, Rust and the Wasm target have been used in real-time frontend settings (such as browser games), and in 2018 there was a dedicated working group seeking to improve this integration.

Similar to other targets, such as ARM, the Wasm target is an LLVM (the compiler technology Rust is built on) backend so it has to be installed using rustup target add wasm32-unknown-unknown. Furthermore, it isn't necessary to declare the binary layout (the "C" in extern "C") and a different bindgen tool does the rest: wasm-bindgen, available at https...

The main repository crates.io

The crates.io website (https://crates.io/) provides a huge repository of crates to be used with Rust. Along with discoverability functions, such as tags and search, it allows Rust programmers to offer their work to others.

The repository itself provides APIs to interact with and a wealth of documentation pointers for cargo, crates in general, and so on. The source code is available on GitHub—we recommend checking out the repository for more information: https://github.com/rust-lang/crates.io.

Publishing

For developers to get their crate into this repository, cargo harbors a command: cargo publish. The command is actually doing more things behind the scenes: first it runs the cargo package to create a *.crate file that contains everything that is uploaded. Then it verifies the contents of the package by essentially running cargo test and checks whether there are any uncommitted files in the local repository. Only if these checks pass does cargo upload the contents of the *.crate file to the repository. This requires a valid account on crates.io (available with your GitHub login) to acquire your personal secret API token, and the crate has to follow certain rules.

With the previously-mentioned Wasm target, it's even possible to publish Rust packages to the famous JavaScript package repository: npm Keep in mind that Wasm support is still very new, but once a crate compiles to Wasm it can be packed into an npm package using Wasm-pack: https://github.com/rustwasm/wasm-pack...

Summary

cargo is Rust's package manager and build tool that is configurable with a manifest called Cargo.toml. The file is used by cargo to build the desired binary with the specified dependencies, profiles, workspaces, and package metadata. During this process, the package state is saved in a file called Cargo.lock. Thanks to its LLVM frontend, Rust compiles to native code on various platforms including the web (using Wasm)—thus keeping a high degree of interoperabilty. Successfully-built packages can be published on a repository called crates.io, a website that is a central hub for available Rust libraries and binaries.

Before we dive into data structures (starting with lists), the next chapter will introduce the ways Rust stores variables and data in memory, whether to copy or to clone, and what sized and unsized types are.

Questions

  • What does cargo do?
  • Does cargo provide linting support?
  • In which cases is the Cargo.lock file important to publish?
  • What are the requirements to publish to crates.io?
  • What is Wasm and why should you care?
  • How are tests organized in a Rust project?

Further reading

Left arrow icon Right arrow icon
Download code icon Download Code

Key benefits

  • Use data structures such as arrays, stacks, trees, lists and graphs with real-world examples
  • Learn the functional and reactive implementations of the traditional data structures
  • Explore illustrations to present data structures and algorithms, as well as their analysis, in a clear, visual manner

Description

Rust has come a long way and is now utilized in several contexts. Its key strengths are its software infrastructure and resource-constrained applications, including desktop applications, servers, and performance-critical applications, not forgetting its importance in systems' programming. This book will be your guide as it takes you through implementing classic data structures and algorithms in Rust, helping you to get up and running as a confident Rust programmer. The book begins with an introduction to Rust data structures and algorithms, while also covering essential language constructs. You will learn how to store data using linked lists, arrays, stacks, and queues. You will also learn how to implement sorting and searching algorithms. You will learn how to attain high performance by implementing algorithms to string data types and implement hash structures in algorithm design. The book will examine algorithm analysis, including Brute Force algorithms, Greedy algorithms, Divide and Conquer algorithms, Dynamic Programming, and Backtracking. By the end of the book, you will have learned how to build components that are easy to understand, debug, and use in different applications.

Who is this book for?

This book is for developers seeking to use Rust solutions in a practical/professional setting; who wants to learn essential Data Structures and Algorithms in Rust. It is for developers with basic Rust language knowledge, some experience in other programming languages is required.

What you will learn

  • Design and implement complex data structures in Rust
  • Analyze, implement, and improve searching and sorting algorithms in Rust
  • Create and use well-tested and reusable components with Rust
  • Understand the basics of multithreaded programming and advanced algorithm design
  • Become familiar with application profiling based on benchmarking and testing
  • Explore the borrowing complexity of implementing algorithms

Product Details

Country selected
Publication date, Length, Edition, Language, ISBN-13
Publication date : Jan 25, 2019
Length: 316 pages
Edition : 1st
Language : English
ISBN-13 : 9781788995528
Category :
Languages :

What do you get with a Packt Subscription?

Free for first 7 days. $15.99 p/m after that. Cancel any time!
Product feature icon Unlimited ad-free access to the largest independent learning library in tech. Access this title and thousands more!
Product feature icon 50+ new titles added per month, including many first-to-market concepts and exclusive early access to books as they are being written.
Product feature icon Innovative learning tools, including AI book assistants, code context explainers, and text-to-speech.
Product feature icon Thousands of reference materials covering every tech concept you need to stay up to date.
Subscribe now
View plans & pricing

Product Details

Publication date : Jan 25, 2019
Length: 316 pages
Edition : 1st
Language : English
ISBN-13 : 9781788995528
Category :
Languages :

Packt Subscriptions

See our plans and pricing
Modal Close icon
$12.99 billed monthly
Feature tick icon Unlimited access to Packt's library of 6,500+ practical books and videos
Feature tick icon Constantly refreshed with 50+ new titles a month
Feature tick icon Exclusive Early access to books as they're written
Feature tick icon Solve problems while you work with advanced search and reference features
Feature tick icon Offline reading on the mobile app
Feature tick icon Simple pricing, no contract
$129.99 billed annually
Feature tick icon Unlimited access to Packt's library of 6,500+ practical books and videos
Feature tick icon Constantly refreshed with 50+ new titles a month
Feature tick icon Exclusive Early access to books as they're written
Feature tick icon Solve problems while you work with advanced search and reference features
Feature tick icon Offline reading on the mobile app
Feature tick icon Choose a DRM-free eBook or Video every month to keep
Feature tick icon PLUS own as many other DRM-free eBooks or Videos as you like for just $5 each
Feature tick icon Exclusive print discounts
$179.99 billed in 18 months
Feature tick icon Unlimited access to Packt's library of 6,500+ practical books and videos
Feature tick icon Constantly refreshed with 50+ new titles a month
Feature tick icon Exclusive Early access to books as they're written
Feature tick icon Solve problems while you work with advanced search and reference features
Feature tick icon Offline reading on the mobile app
Feature tick icon Choose a DRM-free eBook or Video every month to keep
Feature tick icon PLUS own as many other DRM-free eBooks or Videos as you like for just $5 each
Feature tick icon Exclusive print discounts

Frequently bought together


Stars icon
Total $ 118.37 147.97 29.60 saved
Hands-On Data Structures and Algorithms with Rust
$35.19 $43.99
Hands-On Microservices with Rust
$39.19 $48.99
Mastering Rust
$43.99 $54.99
Total $ 118.37 147.97 29.60 saved Stars icon
Visually different images

Table of Contents

14 Chapters
Hello Rust! Chevron down icon Chevron up icon
Cargo and Crates Chevron down icon Chevron up icon
Storing Efficiently Chevron down icon Chevron up icon
Lists, Lists, and More Lists Chevron down icon Chevron up icon
Robust Trees Chevron down icon Chevron up icon
Exploring Maps and Sets Chevron down icon Chevron up icon
Collections in Rust Chevron down icon Chevron up icon
Algorithm Evaluation Chevron down icon Chevron up icon
Ordering Things Chevron down icon Chevron up icon
Finding Stuff Chevron down icon Chevron up icon
Random and Combinatorial Chevron down icon Chevron up icon
Algorithms of the Standard Library Chevron down icon Chevron up icon
Assessments Chevron down icon Chevron up icon
Other Books You May Enjoy Chevron down icon Chevron up icon

Customer reviews

Rating distribution
Full star icon Full star icon Half star icon Empty star icon Empty star icon 2.7
(3 Ratings)
5 star 33.3%
4 star 0%
3 star 0%
2 star 33.3%
1 star 33.3%
RICHARD Jun 09, 2019
Full star icon Full star icon Full star icon Full star icon Full star icon 5
I really enjoyed this book for a lot of reasons. It's a great book for intermediate Rust developers looking to see more complex examples of the language with context most of us understand. I found a lot of the examples easy to follow because I already had a solid grasp of what datastructures there were, and was able to focus seeing how Rust was used for the implementation. This book does a great job at exploring the tradeoffs of various datastructures in a nicely ordered fashion without getting too lost in the weeds of computer science. This book does not deep dive into the Rust language, but rather shows you application of some of its very common features toward non-trivial structures.I found the author of this book very friendly in their writing and not dry at all. I see this as a great addition to any rustaceans library. I would love to see a book by the same author on gang of 4 design patterns.
Amazon Verified review Amazon
Anonymous Mar 29, 2020
Full star icon Full star icon Empty star icon Empty star icon Empty star icon 2
Not at all clear. 75. Pages into this book, I can't see any value. The explanations require extensive use of third party resources to make sense of the source material. The section on Skip Lists was ultimately incomprehensible. I would believe someone finding value in the book. Just not me. Author tried at least.
Amazon Verified review Amazon
Customer Jan 02, 2021
Full star icon Empty star icon Empty star icon Empty star icon Empty star icon 1
The half of the book has nothing to do with the algorithms. The other half has some data structures but they are not tested, not fully implemented in Rust and taken out of context.You get code snippets that not really usable, not step-by-step walk through of the algorithms as well.
Amazon Verified review Amazon
Get free access to Packt library with over 7500+ books and video courses for 7 days!
Start Free Trial

FAQs

What is included in a Packt subscription? Chevron down icon Chevron up icon

A subscription provides you with full access to view all Packt and licnesed content online, this includes exclusive access to Early Access titles. Depending on the tier chosen you can also earn credits and discounts to use for owning content

How can I cancel my subscription? Chevron down icon Chevron up icon

To cancel your subscription with us simply go to the account page - found in the top right of the page or at https://subscription.packtpub.com/my-account/subscription - From here you will see the ‘cancel subscription’ button in the grey box with your subscription information in.

What are credits? Chevron down icon Chevron up icon

Credits can be earned from reading 40 section of any title within the payment cycle - a month starting from the day of subscription payment. You also earn a Credit every month if you subscribe to our annual or 18 month plans. Credits can be used to buy books DRM free, the same way that you would pay for a book. Your credits can be found in the subscription homepage - subscription.packtpub.com - clicking on ‘the my’ library dropdown and selecting ‘credits’.

What happens if an Early Access Course is cancelled? Chevron down icon Chevron up icon

Projects are rarely cancelled, but sometimes it's unavoidable. If an Early Access course is cancelled or excessively delayed, you can exchange your purchase for another course. For further details, please contact us here.

Where can I send feedback about an Early Access title? Chevron down icon Chevron up icon

If you have any feedback about the product you're reading, or Early Access in general, then please fill out a contact form here and we'll make sure the feedback gets to the right team. 

Can I download the code files for Early Access titles? Chevron down icon Chevron up icon

We try to ensure that all books in Early Access have code available to use, download, and fork on GitHub. This helps us be more agile in the development of the book, and helps keep the often changing code base of new versions and new technologies as up to date as possible. Unfortunately, however, there will be rare cases when it is not possible for us to have downloadable code samples available until publication.

When we publish the book, the code files will also be available to download from the Packt website.

How accurate is the publication date? Chevron down icon Chevron up icon

The publication date is as accurate as we can be at any point in the project. Unfortunately, delays can happen. Often those delays are out of our control, such as changes to the technology code base or delays in the tech release. We do our best to give you an accurate estimate of the publication date at any given time, and as more chapters are delivered, the more accurate the delivery date will become.

How will I know when new chapters are ready? Chevron down icon Chevron up icon

We'll let you know every time there has been an update to a course that you've bought in Early Access. You'll get an email to let you know there has been a new chapter, or a change to a previous chapter. The new chapters are automatically added to your account, so you can also check back there any time you're ready and download or read them online.

I am a Packt subscriber, do I get Early Access? Chevron down icon Chevron up icon

Yes, all Early Access content is fully available through your subscription. You will need to have a paid for or active trial subscription in order to access all titles.

How is Early Access delivered? Chevron down icon Chevron up icon

Early Access is currently only available as a PDF or through our online reader. As we make changes or add new chapters, the files in your Packt account will be updated so you can download them again or view them online immediately.

How do I buy Early Access content? Chevron down icon Chevron up icon

Early Access is a way of us getting our content to you quicker, but the method of buying the Early Access course is still the same. Just find the course you want to buy, go through the check-out steps, and you’ll get a confirmation email from us with information and a link to the relevant Early Access courses.

What is Early Access? Chevron down icon Chevron up icon

Keeping up to date with the latest technology is difficult; new versions, new frameworks, new techniques. This feature gives you a head-start to our content, as it's being created. With Early Access you'll receive each chapter as it's written, and get regular updates throughout the product's development, as well as the final course as soon as it's ready.We created Early Access as a means of giving you the information you need, as soon as it's available. As we go through the process of developing a course, 99% of it can be ready but we can't publish until that last 1% falls in to place. Early Access helps to unlock the potential of our content early, to help you start your learning when you need it most. You not only get access to every chapter as it's delivered, edited, and updated, but you'll also get the finalized, DRM-free product to download in any format you want when it's published. As a member of Packt, you'll also be eligible for our exclusive offers, including a free course every day, and discounts on new and popular titles.

Modal Close icon
Modal Close icon