Rust provides a very broad set of collections to use. We will look at most of them, see how they're used, discuss how they're implemented, and when to use and choose them. A big part of this chapter focuses on iterators. Much of Rust's flexibility comes from them, as all collections (and more!) can be used as iterators. Learning how to use them is crucial.

Throughout this chapter, we are going to use the big O notation to show how effective certain algorithms are. In case you don't know it yet, it is a way of telling how much longer an algorithm takes when working with more elements. Let's look at it briefly.

means that an algorithm is going to take the same time, no matter how much data is stored in a collection. It doesn't tell us how fast exactly it is, just that it's not going to slow down with size. This is the realistic ideal for a function. A practical example for this is accessing the first number in an infinite list of numbers...

The most basic collection is the vector, or Vec for short. It is essentially a variable-length array with a very low overhead. As such, it is the collection that you will use most of the time.

1. In the command line, jump one folder up with cd .. so you're not in chapter-one anymore. In the next chapters, we are going to assume that you always started with this step.

2. Create a Rust project to work on during this chapter with cargo new chapter-two.

3. Navigate into the newly-created chapter-two folder. For the rest of this chapter, we will assume that your command line is currently in this directory.
4. Inside the folder src, create a new folder called bin.
5. Delete the generated lib.rs file, as we are not creating a library.
6. In the folder src/bin, create a file called vector.rs.
7. Add the following code blocks to the file and run them with cargo run --bin vector:

1  fn main() {
2    // Create a vector with some elements
3    let fruits = vec!["apple", "tomato", "pear"];
4    // A vector cannot be directly printed
5    // But we can debug-print it
6    println!("fruits: {:?}", fruits);
7
8    // Create an empty vector and fill it
9...

This recipe is going to be a bit longer than the others, because:

• The vector is the most important collection
• Many of its core principles, like preallocation, apply to other collections as well
• It includes methods used on slices, which are also usable by many other collections

Let's start at the beginning.

A vector can be created [9] by using the constructor pattern we mentioned earlier (Chapter 1, Learning the Basics, Using the Constructor Pattern), and filled by calling push on it for every element we want to store [10]. Because this is such a common pattern, Rust provides you with a convenient macro called vec![3]. While its end effect is the same, the macro is implemented with some nice performance optimizations.

If you want to initialize a vector by repeating an element over and over...

The vector should always be your go-to collection. Internally, it is implemented as a continuous chunk of memory stored on the heap:

The important keyword here is continuous, which means that the memory is very cache-friendly. In other words, the vector is pretty fast! The vector even allocates a bit of extra memory in case you want to extend it. Be careful, though, when inserting a lot of data at the beginning of the vector: the entire stack will have to be moved.

At the end, you can see a bit of extra capacity. This is because Vec and many other collections preallocate a bit of extra memory each time you have to move the block, because it has grown too large. This is done in order to prevent as many reallocations as possible. You can check the exact amount of total space of a vector by calling capacity[140] on it. You can influence the preallocation by initializing your vector with with_capacity[137]. Use it when you have a rough idea about how many elements you...

Rust provides an unusually large functionality for its string. Knowing it can save you quite some headache when dealing with raw user input.

1. In the folder src/bin, create a file called string.rs.
2. Add the following code, and run it with cargo run --bin string:

1   fn main() {
2     // As a String is a kind of vector,
3     // you can construct them the same way
4     let mut s = String::new();
5     s.push('H');
6     s.push('i');
7     println!("s: {}", s);
8
9     // The String however can also be constructed
10    // from a string slice (&str)
11    // The next two ways of doing to are equivalent
12    let s = "Hello".to_string();
13    println!("s: {}", s);
14    let s = String::from("Hello");
15    println!("s: {}", s);
16
17    // A String in Rust will always be valid UTF-8
18    let s = " Þjóðhildur  ".to_string();
19    println!("s: {}", s);
20
21    // Append strings to each other
22    let mut s = "Hello ".to_string();
23    s.push_str("World");
24
25    // Iterate over the character
26    // A...

Essentially, being a kind of vector, a string can be created the same way by combining new and push; however, because this is really inconvenient, a string, which is an owned chunk of memory, can be created from a string slice (&str), which is either a borrowed string or a literal. Both of the ways to do it, that are shown in this recipe, are equivalent:

    let s = "Hello".to_string();
    println!("s: {}", s);
    let s = String::from("Hello");
    println!("s: {}", s);

Out of pure personal preference, we will use the first variant.

All strings in Rust are valid Unicode in UTF-8 encoding. This can lead to some surprises, as a character...

The implementation of String should not be much of a surprise—it's just a kind of vector:

Welcome to one of the most flexible parts of the Rust standard library. Iterators are, as the name suggests, a way of applying actions of items in a collection. If you come from C#, you will already be familiar with iterators because of Linq. Rust's iterators are kind of similar, but come with a more functional approach to things.

Because they are an extremely fundamental part of the standard library, we are going to dedicate this recipe entirely to a showcase of all the different things you can do with them in isolation. For real-world use cases, you can simply continue reading the book, as a big portion of the other recipes features iterators in some way or another.

1. In the folder src/bin, create a file called iterator.rs.
2. Add the following code, and run it with cargo run --bin iterator:

1   fn main() {
2     let names = vec!["Joe", "Miranda", "Alice"];
3     // Iterators can be accessed in many ways.
4     // Nearly all collections implement .iter() for this purpose
5     let mut iter = names.iter();
6     // A string itself is not iterable, but its characters are
7     let mut alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".chars();
8     // Ranges are also (limited) iterators
9     let nums = 0..10;
10    // You can even create infinite iterators!
11    let all_nums = 0..;
12
13    // As the name says, you can iterate over iterators
14    // This will consume the iterator
15    for num in nums {
16        print!("{} ", num);
17    }
18    // nums is no longer usable
19    println!();
20
21    // Get the index of the current item
22    for (index, letter) in "abc".chars().enumerate() {
23      println...

This recipe is incredibly important. No matter what you do, or which library you use, it's going to use iterators somewhere. All of the operations presented can be used on any collection and all types that implement the iterator trait.

In the first section, we looked at different ways to create iterators. I mention that ranges are limited because, in order to be iterable, the range-type has to implement Step. char doesn't, so you wouldn't be able to use 'A'..'D' as an iterator. For this reason, in line [209], we iterate over the characters as bytes:

    let alphabet: Vec<_> = (b'A' .. b'z' + 1) // Start as u8
        .map(|c| c as char)            // Convert all to chars
        .filter(|c| c.is_alphabetic()) // Filter only alphabetic chars
        .collect(); // Collect as Vec<char>

We have to set the limit of the range to b'z' + 1, because ranges are non-inclusive. You might have noticed that...

iter() creates an iterator that borrows items. If you want to create an iterator that consumes items—for example, takes ownership of them by moving them – you can use into_iter().

• The Iterating over an inclusive range recipe in Chapter 10, Using Experimental Nightly Features

When you need to insert or remove elements regularly into or from the beginning of the vector, your performance might take quite a hit, as it will force the vector to reallocate all data that comes after it. This is especially bothersome when implementing a queue. For this reason, Rust provides you with the VecDeque.

1. In the folder src/bin, create a file called vecdeque.rs.
2. Add the following code, and run it with cargo run --bin vecdeque:

1   use std::collections::VecDeque;
2 
3   fn main() {
4     // A VecDeque is best thought of as a
5     // First-In-First-Out (FIFO) queue
6 
7     // Usually, you will use it to push_back data
8     // and then remove it again with pop_front
9     let mut orders = VecDeque::new();
10    println!("A guest ordered oysters!");
11    orders.push_back("oysters");
12 
13    println!("A guest ordered fish and chips!");
14    orders.push_back("fish and chips");
15 
16    let prepared = orders.pop_front();
17    if let Some(prepared) = prepared {
18      println!("{} are ready", prepared);
19    }
20 
21    println!("A guest ordered mozarella sticks!");
22    orders.push_back("mozarella sticks");
23 
24    let prepared = orders.pop_front();
25    if let Some(prepared) = prepared {
26      println!("{} are...

Most of the interface of VecDeque is identical to Vec. You can even optimize them the same way with with_capacity and its swap_remove equivalents. The differences come from the fact that VecDeque is more oriented around access from both ends. As such, multiple methods from Vec that implicitly affect the last element have two equivalents in VecDeque: one for the front, and one for the back. These are:

• push, which becomes push_front [46] and push_back [11]
• pop, which becomes pop_front [16] and pop_back [55]
• swap_remove, which becomes remove_front [78] and remove_back [73]

A VecDeque has the ability to freely append or remove elements from both ends in a performant way, which makes it an ideal candidate for a First In, First Out (FIFO) queue [24]. In fact, this is how it's nearly always used.

When you see yourself in a situation where you want to respond to any kind of requests in the order they arrive in and remove them again afterwards, a VecDeque is an ideal tool...

Internally, the VecDeque is implemented as a ring buffer, also known as a circular buffer. It's called like this because it behaves like a circle: the end touches the beginning.

It works by allocating a continuous block of memory, like the Vec; however, where the Vec always leaves its extra capacity at the end of the block, the VecDeque has nothing against leaving spots inside the block empty. It follows that when you remove the first element, the VecDeque doesn't move all elements to the left, but simply leaves the first spot empty. If you then push an element into the beginning via push_front, it will take the spot freed earlier while leaving the elements after it untouched.

The circular catch in the story is that if you have some capacity in the front of the block but none in the back while using push_back, the VecDeque will simply use that space to allocate the extra element, leading to the following situation:

This is great, because you will not...

If you imagine a Vec as a collection that assigns an index (0, 1, 2, and so on) to data, the HashMap is a collection that assigns any data to any data. It allows you to map arbitrary, hashable data to other arbitrary data. Hashing and mapping, that's where the name comes from!

1. In the folder src/bin, create a file called hashmap.rs.
2. Add the following code, and run it with cargo run --bin hashmap:

1   use std::collections::HashMap; 
2 
3   fn main() {
4     // The HashMap can map any hashable type to any other
5     // The first type is called the "key"
6     // and the second one the "value"
7     let mut tv_ratings = HashMap::new();
8     // Here, we are mapping &str to i32
9     tv_ratings.insert("The IT Crowd", 8);
10    tv_ratings.insert("13 Reasons Why", 7);
11    tv_ratings.insert("House of Cards", 9);
12    tv_ratings.insert("Stranger Things", 8);
13    tv_ratings.insert("Breaking Bad", 10);
14 
15    // Does a key exist?
16    let contains_tv_show = tv_ratings.contains_key("House of
        Cards");
17    println!("Did we rate House of Cards? {}", contains_tv_show);
18    let contains_tv_show = tv_ratings.contains_key("House");
19    println!(&quot...

As mentioned earlier, a HashMap is a collection to map one type of data to another. You do this by calling insert, and passing your key and its value [9]. If the key already had a value, it will be overwritten. This is why insert returns an Option: if there was a value before, it returns the old value [27], or otherwise None. If you want to make sure that you're not overwriting anything, make sure to check the result of contains_key [16] before inserting your value.

Both get and remove won't crash when called with an invalid key. Instead, they return a Result. In the case of remove, said Result contains the removed value.

As with most collections, you have the options to iterate over your data, by borrowing the key-value pairs[43], borrowing the keys while mutating the values [49], or moving them all [55]. Due to its nature, HashMap additionally allows you three more options: borrowing all values [74], mutating all values [80], or borrowing all keys [68]. You...

Internally, you can imagine the HashMap as being implemented as two vectors: a table, and a buffer. Of course, we're simplifying here; there are actually no vectors in the implementation. But this analogy is accurate enough.

In the background, the buffer stores our values in a sequential fashion. In the front, we have a table storing buckets that don't do much more than point to the element they stand for. When you insert a key-value pair, what happens is:

1. The value gets put in the buffer.
2. The key goes through a hashing function and becomes an index.
3. The table creates a bucket at said index that points to the actual value:

The best way to describe a HashSet is by describing how it's implemented: HashMap<K, ()>. It's just a HashMap without any values!

The two best reasons to choose a HashSet are:

• You don't want to deal with duplicate values at all, as it doesn't even include them.
• You plan on doing a lot (and I mean a lot) of item lookup - that is the question, Does my collection contain this particular item?. In a vector, this is done in , while a HashSet can do it in .

1. In the folder src/bin, create a file called hashset.rs.
2. Add the following code, and run it with cargo run --bin hashset:

1   use std::collections::HashSet;
2 
3   fn main() {
4     // Most of the interface of HashSet
5     // is the same as HashMap, just without
6     // the methods that handle values
7     let mut books = HashSet::new();
8     books.insert("Harry Potter and the Philosopher's Stone");
9     books.insert("The Name of the Wind");
10    books.insert("A Game of Thrones");
11 
12    // A HashSet will ignore duplicate entries
13    // but will return if an entry is new or not
14    let is_new = books.insert("The Lies of Locke Lamora");
15    if is_new {
16      println!("We've just added a new book!");
17    }
18 
19    let is_new = books.insert("A Game of Thrones");
20    if !is_new {
21      println!("Sorry, we already had that book in store");
22    }
23 
24    // Check if it contains a key
25    if...

As a HashSet is a kind of HashMap, most of its interface is pretty similar. The major difference is that the methods that would return a key's value in the HashMap instead simply return a bool on the HashSet in order to tell if a key already existed or not [14].

Additionally, HashSet brings a few methods for analyzing two sets [46 to 92] and joining them [96 to 131]. If you've ever heard of set theory or Venn diagrams, or done a bit of SQL, you're going to recognize it all. Otherwise, I advise you to run the example, and study the outputs in combination with the relevant comments.

Some illustrations might help you. For the analytical methods, the dark green part is the object of reference:

For the selecting methods, the dark green part is the one that is returned:

No big surprises in the implementation of the HashSet, since it's exactly the same as the HashMap, just without any values!

When you create an infinitely applicable algorithm or a collection-like structure, it's really nice to have the dozens of methods that an iterator provides at your disposal. For this, you will have to know how to tell Rust to implement them for you.

1. In the folder src/bin, create a file called own_iterator.rs.
2. Add the following code, and run it with cargo run --bin own_iterator:

1   fn main() {
2     let fib: Vec<_> = fibonacci().take(10).collect();
3     println!("First 10 numbers of the fibonacci sequence: {:?}", 
        fib);
4 
5     let mut squared_vec = SquaredVec::new();
6     squared_vec.push(1);
7     squared_vec.push(2);
8     squared_vec.push(3);
9     squared_vec.push(4);
10    for (index, num) in squared_vec.iter().enumerate() {
11      println!("{}^2 is {}", index + 1, num);
12    }
13  }
14 
15 
16  fn fibonacci() -> Fibonacci {
17    Fibonacci { curr: 0, next: 1 }
18  }
19  struct Fibonacci {
20  curr: u32,
21  next: u32,
22  }
23  // A custom iterator has to implement
24  // only one method: What comes next
25  impl Iterator for Fibonacci {
26    type Item = u32;
27    fn next(&mut self) -> Option<u32> {
28      let old = self.curr;
29      self.curr = self.next;
30      self.next +...

In our little example here, we are going to look at two different uses for an iterator:

• fibonacci(), which returns an infinite range of the Fibonacci sequence
• SquaredVec, which implements a (very) small subset of a Vec with a twist: it squares all items

An algorithm can be turned into an iterator by implementing the Iterator trait. This is pretty simple, as it only expects you to provide the type you're iterating over and a single method, next, which fetches the next item. If the iterator doesn't have any items left, it should return None, otherwise Some. Our Fibonacci iterator always returns Some item...

If you have a lot of complex logic to perform in the iterator and want to separate it a bit from your collection, you can do so by providing your collection with the IntoIterator trait instead. This would allow you to return a struct specifically made for your iteration, which itself provides the Iterator trait.

Some algorithms require you to hold access tokens to data that may or may not exist. This could be solved in Rust by using  Vec<Option<T>>, and treating the index of your data as a token. But we can do better! slab is an optimized abstraction of exactly this concept.

While it is not meant as a general-purpose collection, slab can help you a lot if you use it in the right places.

1. Open the Cargo.toml file that has been generated earlier for you.

2. Under [dependencies], add the following line:

slab = "0.4.0"

3. If you want, you can go to slab's crates.io page (https://crates.io/crates/slab) to check for the newest version, and use that one instead.

4. In the folder bin, create a file called slab.rs.

5. Add the following code, and run it with cargo run --bin slab:

1   extern crate slab;
2   use slab::{Slab, VacantEntry};
3 
4   fn main() {
5     // A slab is meant to be used as a limited buffer
6     // As such, you should initialize it with a pre-
7     // defined capacity
8     const CAPACITY: usize = 1024;
9     let mut slab = Slab::with_capacity(CAPACITY);
10 
11    // You cannot simply access a slab's entry by
12    // index or by searching it. Instead, every
13    // insert gives you a key that you can use to
14    // access its entry
15    let hello_key = slab.insert("hello");
16    let world_key = slab.insert("world&quot...

A slab is very similar to a vector, with one quintessential difference: you don't get to choose your index. Instead, when inserting data [15], you receive the data's index as a kind of key that you can use to access it again. It is your responsibility to store this key somewhere; otherwise, the only way to retrieve your data is by iterating over your slab. The flipside is that you don't have to provide any key either. In contrast to a HashMap, you don't need any hashable objects at all.

A situation in which this is useful is in a connection pool: if you have multiple clients who want to access individual resources, you can store said resources in a slab and provide the clients with their key as a kind of token.

This example suits the second use case of a slab really well. Suppose you only accept a certain amount of connections at a given time. When accepting a connection, you don't care about the exact index, or the way it is stored. Instead, you...

A slab is backed by a Vec<Entry>. You might remember the Entry from our recipe about the HashMap earlier. It is the same as an Option, with the difference that its variants are not called Some(...) and None, but Occupied(...) and Vacant. This means that, in a nutshell, a slab is implemented as a vector with holes in it:

Additionally, in order to guarantee fast occupation of vacant spots, the slab keeps a linked list of all vacant entries.