Search icon CANCEL
Subscription
0
Cart icon
Your Cart (0 item)
Close icon
You have no products in your basket yet
Save more on your purchases! discount-offer-chevron-icon
Savings automatically calculated. No voucher code required.
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
€26.99
Paperback
€32.99
Subscription
Free Trial
Renews at €11.99p/m

What do you get with eBook?

Product feature icon Instant access to your Digital eBook purchase
Product feature icon Download this book in EPUB and PDF formats
Product feature icon Access this title in our online reader with advanced features
Product feature icon DRM FREE - Read whenever, wherever and however you want
Product feature icon AI Assistant (beta) to help accelerate your learning
OR
Modal Close icon
Payment Processing...
tick Completed

Billing Address

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 : 9781788991490
Category :
Languages :

What do you get with eBook?

Product feature icon Instant access to your Digital eBook purchase
Product feature icon Download this book in EPUB and PDF formats
Product feature icon Access this title in our online reader with advanced features
Product feature icon DRM FREE - Read whenever, wherever and however you want
Product feature icon AI Assistant (beta) to help accelerate your learning
OR
Modal Close icon
Payment Processing...
tick Completed

Billing Address

Product Details

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

Packt Subscriptions

See our plans and pricing
Modal Close icon
€11.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
€119.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
€169.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 111.97
Hands-On Data Structures and Algorithms with Rust
€32.99
Hands-On Microservices with Rust
€36.99
Mastering Rust
€41.99
Total 111.97 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

How do I buy and download an eBook? Chevron down icon Chevron up icon

Where there is an eBook version of a title available, you can buy it from the book details for that title. Add either the standalone eBook or the eBook and print book bundle to your shopping cart. Your eBook will show in your cart as a product on its own. After completing checkout and payment in the normal way, you will receive your receipt on the screen containing a link to a personalised PDF download file. This link will remain active for 30 days. You can download backup copies of the file by logging in to your account at any time.

If you already have Adobe reader installed, then clicking on the link will download and open the PDF file directly. If you don't, then save the PDF file on your machine and download the Reader to view it.

Please Note: Packt eBooks are non-returnable and non-refundable.

Packt eBook and Licensing When you buy an eBook from Packt Publishing, completing your purchase means you accept the terms of our licence agreement. Please read the full text of the agreement. In it we have tried to balance the need for the ebook to be usable for you the reader with our needs to protect the rights of us as Publishers and of our authors. In summary, the agreement says:

  • You may make copies of your eBook for your own use onto any machine
  • You may not pass copies of the eBook on to anyone else
How can I make a purchase on your website? Chevron down icon Chevron up icon

If you want to purchase a video course, eBook or Bundle (Print+eBook) please follow below steps:

  1. Register on our website using your email address and the password.
  2. Search for the title by name or ISBN using the search option.
  3. Select the title you want to purchase.
  4. Choose the format you wish to purchase the title in; if you order the Print Book, you get a free eBook copy of the same title. 
  5. Proceed with the checkout process (payment to be made using Credit Card, Debit Cart, or PayPal)
Where can I access support around an eBook? Chevron down icon Chevron up icon
  • If you experience a problem with using or installing Adobe Reader, the contact Adobe directly.
  • To view the errata for the book, see www.packtpub.com/support and view the pages for the title you have.
  • To view your account details or to download a new copy of the book go to www.packtpub.com/account
  • To contact us directly if a problem is not resolved, use www.packtpub.com/contact-us
What eBook formats do Packt support? Chevron down icon Chevron up icon

Our eBooks are currently available in a variety of formats such as PDF and ePubs. In the future, this may well change with trends and development in technology, but please note that our PDFs are not Adobe eBook Reader format, which has greater restrictions on security.

You will need to use Adobe Reader v9 or later in order to read Packt's PDF eBooks.

What are the benefits of eBooks? Chevron down icon Chevron up icon
  • You can get the information you need immediately
  • You can easily take them with you on a laptop
  • You can download them an unlimited number of times
  • You can print them out
  • They are copy-paste enabled
  • They are searchable
  • There is no password protection
  • They are lower price than print
  • They save resources and space
What is an eBook? Chevron down icon Chevron up icon

Packt eBooks are a complete electronic version of the print edition, available in PDF and ePub formats. Every piece of content down to the page numbering is the same. Because we save the costs of printing and shipping the book to you, we are able to offer eBooks at a lower cost than print editions.

When you have purchased an eBook, simply login to your account and click on the link in Your Download Area. We recommend you saving the file to your hard drive before opening it.

For optimal viewing of our eBooks, we recommend you download and install the free Adobe Reader version 9.

Modal Close icon
Modal Close icon