Chapter 8

Common Collections

Rust’s standard library includes very useful data structures called collections. Most data types represent one specific value; collections can contain multiple values. Unlike the built-in array and tuple types, the data these collections point to is stored on the heap, so its amount need not be known at compile time and can grow or shrink as the program runs. Each kind has different capabilities and costs; choosing an appropriate one is a skill you develop over time. This chapter covers how to create and update the three used most often, and what makes each special:

8.1 Storing Lists of Values with Vectors — a vector stores a variable number of values next to each other.
8.2 Storing UTF-8 Encoded Text with Strings — a string is a collection of characters (String in depth).
8.3 Storing Keys with Associated Values in Hash Maps — a hash map associates a value with a specific key; it is one implementation of the general data structure called a map.

The other collections in the standard library are described in the std::collections documentation.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Vectors, and creating an empty one

The first collection type is Vec<T>, also known as a vector. Vectors are useful when you have a list of items, such as the lines of text in a file or the prices of items in a shopping cart.

Definition 8.1 (Vector). Vec<T>: a collection that stores more than one value in a single data structure, putting all the values next to each other in memory. A vector can only store values of the same type.

To create a new, empty vector, call the Vec::new function, as shown in Listing 8.1.

Listing 8.1: Creating a new, empty vector to hold values of type i32

fn main() {
    let v: Vec<i32> = Vec::new();
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Type annotations and the vec! macro

Listing 8.1 needs a type annotation: because no values are inserted, Rust doesn’t know what kind of elements we intend to store. This is an important point. Vectors are implemented using generics (Chapter 10 covers using generics with your own types). For now, know that the standard library’s Vec<T> can hold any type, and the specific type goes within angle brackets: in Listing 8.1, the Vec<T> in v holds elements of the i32 type.

More often you create a Vec<T> with initial values and Rust infers the element type, so you rarely need the annotation. The vec! macro creates a new vector holding the values you give it. Listing 8.2 creates a Vec<i32> holding 1, 2 and 3; the type is i32 because that is the default integer type (“Data Types”, Chapter 3).

Listing 8.2: Creating a new vector containing values

fn main() {
    let v = vec![1, 2, 3];
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Updating a vector with push

Because Listing 8.2 gives initial i32 values, Rust infers that the type of v is Vec<i32>, and no annotation is needed. To create a vector and then add elements to it, use the push method (Listing 8.3).

Listing 8.3: Using the push method to add values to a vector

fn main() {
    let mut v = Vec::new();
 
    v.push(5);
    v.push(6);
    v.push(7);
    v.push(8);
}

As with any variable, to change its value we make it mutable with the mut keyword (Chapter 3).
The numbers placed inside are all of type i32; Rust infers this from the data, so the Vec<i32> annotation isn’t needed.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Reading elements: indexing or get

There are two ways to reference a value stored in a vector: via indexing or by using the get method. Listing 8.4 shows both; the types of the returned values are annotated for extra clarity.

Listing 8.4: Using indexing syntax and using the get method to access an item in a vector

fn main() {
    let v = vec![1, 2, 3, 4, 5];
 
    let third: &i32 = &v[2];
    println!("The third element is {third}");
 
    let third: Option<&i32> = v.get(2);
    match third {
        Some(third) => println!("The third element is {third}"),
        None => println!("There is no third element."),
    }
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Reading past the end of a vector

In Listing 8.4, the index value 2 gets the third element, because vectors are indexed by number, starting at zero.
Using & and [] gives a reference to the element at the index value.
The get method, with the index passed as an argument, gives an Option<&T> that we can use with match.

Rust provides both ways so you can choose how the program behaves when an index is outside the range of existing elements. Listing 8.5 takes a vector of five elements and tries to access index 100 with each technique.

Listing 8.5: Attempting to access the element at index 100 in a vector containing five elements

fn main() {
    let v = vec![1, 2, 3, 4, 5];
 
    let does_not_exist = &v[100];
    let does_not_exist = v.get(100);
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Panic with [] or None with get

Indexing with []

When Listing 8.5 runs, the first, [] method causes the program to panic, because it references a nonexistent element.

This method is best used when you want your program to crash if there’s an attempt to access an element past the end of the vector.

The get method

Passed an index outside the vector, get returns None without panicking. Use it if accessing an element beyond the range of the vector may happen occasionally under normal circumstances. Your code then has logic to handle either Some(&element) or None (Chapter 6).

Example 8.2. The index could come from a person entering a number. If they accidentally enter a number that’s too large and the program gets a None value, you could tell the user how many items are in the current vector and give them another chance to enter a valid value. That is more user-friendly than crashing the program due to a typo!

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Holding a reference while pushing

When the program has a valid reference, the borrow checker enforces the ownership and borrowing rules (Chapter 4) to ensure that this reference and any other references to the contents of the vector remain valid. Recall the rule that you can’t have mutable and immutable references in the same scope. Listing 8.6 holds an immutable reference to the first element and tries to add an element to the end; this won’t work if we also refer to that element later in the function.

Listing 8.6: Attempting to add an element to a vector while holding a reference to an item

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];
 
    let first = &v[0];
 
    v.push(6);
 
    println!("The first element is: {first}");
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

The E0502 borrow error

Compiling the code in Listing 8.6 results in this error:

$ cargo run
   Compiling collections v0.1.0 (file:///projects/collections)
error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
 --> src/main.rs:6:5
  |
4 |     let first = &v[0];
  |                  - immutable borrow occurs here
5 |
6 |     v.push(6);
  |     ^^^^^^^^^ mutable borrow occurs here
7 |
8 |     println!("The first element is: {first}");
  |                                    ----- immutable borrow later used here
 
For more information about this error, try `rustc --explain E0502`.
error: could not compile `collections` (bin "collections") due to 1 previous error

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Why the borrow checker rejects Listing 8.6

The code might look like it should work: why should a reference to the first element care about changes at the end of the vector?

The error is due to the way vectors work. Because vectors put the values next to each other in memory, adding a new element onto the end might require:

allocating new memory, if there isn’t enough room to put all the elements next to each other where the vector is currently stored, and
copying the old elements to the new space.

In that case, the reference to the first element would be pointing to deallocated memory. The borrowing rules prevent programs from ending up in that situation.

Remark. For more on the implementation details of the Vec<T> type, see “The Rustonomicon” (doc.rust-lang.org/nomicon/vec/vec.html).

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Iterating over the values in a vector

To access each element in a vector in turn, iterate through all of the elements rather than use indices to access one at a time.

A for loop gets immutable references to each element in a vector of i32 values and prints them.

Listing 8.7: Printing each element in a vector by iterating over the elements using a for loop

fn main() {
    let v = vec![100, 32, 57];
    for i in &v {
        println!("{i}");
    }
}

We can also iterate over mutable references to each element in a mutable vector to change all the elements. This loop adds 50 to each element.

Listing 8.8: Iterating over mutable references to elements in a vector

fn main() {
    let mut v = vec![100, 32, 57];
    for i in &mut v {
        *i += 50;
    }
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Dereferencing, and why iteration is safe

*i += 50;

To change the value that the mutable reference refers to, we have to use the * dereference operator to get to the value in i before we can use the += operator. The dereference operator is covered in “Following the Reference to the Value” in Chapter 15.

Iteration and the borrow checker

Iterating over a vector, whether immutably or mutably, is safe because of the borrow checker’s rules.

If we attempted to insert or remove items in the for loop bodies of Listings 8.7 and 8.8, we would get a compiler error similar to the one for Listing 8.6.
The reference to the vector that the for loop holds prevents simultaneous modification of the whole vector.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Using an enum to store multiple types

Vectors can only store values that are of the same type. This can be inconvenient: there are definitely use cases for storing a list of items of different types.

Fortunately, the variants of an enum are defined under the same enum type. So when we need one type to represent elements of different types, we can define and use an enum!

Example 8.3. Say we want to get values from a row in a spreadsheet in which some of the columns contain integers, some floating-point numbers, and some strings.

Define an enum whose variants hold the different value types.
All the enum variants are considered the same type: that of the enum.
Then create a vector to hold that enum — and so, ultimately, hold different types (Listing 8.9).

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

A vector of spreadsheet cells

Listing 8.9: Defining an enum to store values of different types in one vector

fn main() {
    enum SpreadsheetCell {
        Int(i32),
        Float(f64),
        Text(String),
    }
 
    let row = vec![
        SpreadsheetCell::Int(3),
        SpreadsheetCell::Text(String::from("blue")),
        SpreadsheetCell::Float(10.12),
    ];
}

Rust needs to know what types will be in the vector at compile time so that it knows exactly how much memory on the heap will be needed to store each element.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Explicit element types, trait objects, and the Vec API

We must also be explicit about what types are allowed in this vector. If Rust allowed a vector to hold any type, there would be a chance that one or more of the types would cause errors with the operations performed on the elements of the vector.

Using an enum plus a match expression means that Rust will ensure at compile time that every possible case is handled, as discussed in Chapter 6.

Remark. If you don’t know the exhaustive set of types a program will get at runtime to store in a vector, the enum technique won’t work. Instead, you can use a trait object, covered in Chapter 18.

Those are some of the most common ways to use vectors. Be sure to review the API documentation (std::vec::Vec) for the many useful methods the standard library defines on Vec<T>. For example, in addition to push, a pop method removes and returns the last element.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.1 Storing Lists of Values with Vectors

Dropping a vector drops its elements

Like any other struct, a vector is freed when it goes out of scope, as annotated in Listing 8.10.

Listing 8.10: Showing where the vector and its elements are dropped

fn main() {
    {
        let v = vec![1, 2, 3, 4];
 
        // do stuff with v
    } // <- v goes out of scope and is freed here
}

When the vector gets dropped, all of its contents are also dropped: the integers it holds are cleaned up.
The borrow checker ensures that any references to contents of a vector are only used while the vector itself is valid.

Next collection type: String!

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Strings, in more depth

Chapter 4 introduced strings; now we look at them in more depth. New Rustaceans commonly get stuck on strings for a combination of three reasons, which together can seem difficult when you’re coming from other programming languages:

Rust’s propensity for exposing possible errors;
strings being a more complicated data structure than many programmers give them credit for;
UTF-8.

Strings belong in a chapter on collections because they are implemented as a collection of bytes, plus some methods that provide useful functionality when those bytes are interpreted as text.

This section covers the operations on String that every collection type has — creating, updating and reading — and the ways String differs from the other collections: indexing into a String is complicated by the differences between how people and computers interpret String data.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Defining strings: str and String

First, what we mean by the term string. Rust has only one string type in the core language: the string slice str, usually seen in its borrowed form, &str.

Definition 8.4 (String slice). str / &str: a reference to some UTF-8 encoded string data stored elsewhere (Chapter 4). String literals, for example, are stored in the program’s binary and are therefore string slices.

Definition 8.5 (String). String: a growable, mutable, owned, UTF-8 encoded string type, provided by Rust’s standard library rather than coded into the core language.

When Rustaceans refer to “strings” in Rust, they might mean either the String or the string slice &str type, not just one of them.
This section is largely about String, but both types are used heavily in Rust’s standard library.
Both String and string slices are UTF-8 encoded.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Creating a new String

Many operations of Vec<T> are available with String too, because String is actually implemented as a wrapper around a vector of bytes with some extra guarantees, restrictions and capabilities. One function that works the same way for both is new, which creates an instance.

Often we want to start the string with some initial data. For that, use the to_string method, available on any type that implements the Display trait, as string literals do.

Listing 8.11: Creating a new, empty String

fn main() {
    let mut s = String::new();
}

This line creates a new, empty string called s, into which we can then load data.

Listing 8.12: Using the to_string method to create a String from a string literal

fn main() {
    let data = "initial contents";
 
    let s = data.to_string();
 
    // The method also works on a literal directly:
    let s = "initial contents".to_string();
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

String::from, or to_string

Listing 8.12 creates a string containing initial contents. We can also use the function String::from to create a String from a string literal. Listing 8.13 is equivalent to Listing 8.12, which uses to_string.

Listing 8.13: Using the String::from function to create a String from a string literal

fn main() {
    let s = String::from("initial contents");
}

Because strings are used for so many things, there are many different generic APIs for strings, giving us a lot of options. Some of them can seem redundant, but they all have their place!

Remark. String::from and to_string do the same thing, so which one you choose is a matter of style and readability.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Strings hold any UTF-8 text

Strings are UTF-8 encoded, so we can include any properly encoded data in them, as shown in Listing 8.14.

Listing 8.14: Storing greetings in different languages in strings

fn main() {
    let hello = String::from("السلام عليكم");
    let hello = String::from("Dobrý den");
    let hello = String::from("Hello");
    let hello = String::from("שלום");
    let hello = String::from("नमस्ते");
    let hello = String::from("こんにちは");
    let hello = String::from("안녕하세요");
    let hello = String::from("你好");
    let hello = String::from("Olá");
    let hello = String::from("Здравствуйте");
    let hello = String::from("Hola");
}

All of these are valid String values.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Updating a String: appending with push_str

A String can grow in size and its contents can change, just like the contents of a Vec<T>, if you push more data into it. You can also conveniently use the + operator or the format! macro to concatenate String values.

We can grow a String by using the push_str method to append a string slice, as shown in Listing 8.15.

Listing 8.15: Appending a string slice to a String using the push_str method

fn main() {
    let mut s = String::from("foo");
    s.push_str("bar");
}

After these two lines, s will contain foobar. The push_str method takes a string slice because we don’t necessarily want to take ownership of the parameter. For example, in Listing 8.16 we want to be able to use s2 after appending its contents to s1.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

push_str borrows; push adds one character

Listing 8.16: Using a string slice after appending its contents to a String

fn main() {
    let mut s1 = String::from("foo");
    let s2 = "bar";
    s1.push_str(s2);
    println!("s2 is {s2}");
}

If the push_str method took ownership of s2, we wouldn’t be able to print its value on the last line. However, this code works as we’d expect!

The push method takes a single character as a parameter and adds it to the String. Listing 8.17 adds the letter l to a String.

Listing 8.17: Adding one character to a String value using push

fn main() {
    let mut s = String::from("lo");
    s.push('l');
}

As a result, s will contain lol.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Concatenating with the + operator

Often you’ll want to combine two existing strings. One way is the + operator, as shown in Listing 8.18.

Listing 8.18: Using the + operator to combine two String values into a new String value

fn main() {
    let s1 = String::from("Hello, ");
    let s2 = String::from("world!");
    let s3 = s1 + &s2; // note s1 has been moved here and can no longer be used
}

The string s3 will contain Hello, world!. Why s1 is no longer valid after the addition, and why we used a reference to s2, has to do with the signature of the method called when we use the + operator. It uses the add method, whose signature looks something like this:

fn add(self, s: &str) -> String {

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Reading add’s signature: the &str parameter

In the standard library, add is defined using generics and associated types; here concrete types are substituted in, as happens when we call it with String values (generics: Chapter 10). This signature gives the clues to the tricky bits of the + operator.

First, s2 has an &: we add a reference of the second string to the first string. This is because of the s parameter of add: we can only add a string slice to a String; we can’t add two String values together. But wait — the type of &s2 is &String, not &str as the second parameter of add specifies. So why does Listing 8.18 compile?

Definition 8.6 (Deref coercion). A conversion the compiler applies to an argument; here it coerces the &String argument into a &str, turning &s2 into &s2[..] (covered in depth in Chapter 15).

That is why &s2 can be used in the call to add. And because add does not take ownership of the s parameter, s2 will still be a valid String after this operation.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

add takes ownership of self

Second, the signature shows that add takes ownership of self, because self does not have an &. So s1 in Listing 8.18 is moved into the add call and is no longer valid afterwards.

Although let s3 = s1 + &s2; looks like it will copy both strings and create a new one, it takes ownership of s1, appends a copy of the contents of s2, and returns ownership of the result: not a lot of copies, but an implementation more efficient than copying.

To concatenate multiple strings, the behavior of the + operator gets unwieldy:

fn main() {
    let s1 = String::from("tic");
    let s2 = String::from("tac");
    let s3 = String::from("toe");
 
    let s = s1 + "-" + &s2 + "-" + &s3;
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Concatenating with format!

At this point, s will be tic-tac-toe. With all of the + and " characters, it’s difficult to see what’s going on. For combining strings in more complicated ways, use the format! macro instead:

fn main() {
    let s1 = String::from("tic");
    let s2 = String::from("tac");
    let s3 = String::from("toe");
 
    let s = format!("{s1}-{s2}-{s3}");
}

This code also sets s to tic-tac-toe.
The format! macro works like println!, but instead of printing the output to the screen, it returns a String with the contents.
The format! version is much easier to read, and the code it generates uses references, so the call doesn’t take ownership of any of its parameters.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Indexing into strings

In many other programming languages, accessing individual characters in a string by referencing them by index is a valid and common operation. However, if you try to access parts of a String using indexing syntax in Rust, you’ll get an error. Consider the invalid code in Listing 8.19.

Listing 8.19: Attempting to use indexing syntax with a String

fn main() {
    let s1 = String::from("hi");
    let h = s1[0];
}

This code results in the error E0277, shown in full on the next slide. Its key lines:

the type `str` cannot be indexed by `{integer}`
string indices are ranges of `usize`
you can use `.chars().nth()` or `.bytes().nth()`

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

The E0277 error: a String cannot be indexed

$ cargo run
   Compiling collections v0.1.0 (file:///projects/collections)
error[E0277]: the type `str` cannot be indexed by `{integer}`
 --> src/main.rs:3:16
  |
3 |     let h = s1[0];
  |                ^ string indices are ranges of `usize`
  |
  = help: the trait `SliceIndex<str>` is not implemented for `{integer}`
  = note: you can use `.chars().nth()` or `.bytes().nth()`
          for more information, see chapter 8 in The Book:
            <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>
help: `usize` implements trait `SliceIndex<T>`
...
  = note: required for `String` to implement `Index<{integer}>`
 
For more information about this error, try `rustc --explain E0277`.
error: could not compile `collections` (bin "collections") due to 1 previous error

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Internal representation: a Vec<u8>

The error tells the story: Rust strings don’t support indexing. But why not? To answer, we need to discuss how Rust stores strings in memory. A String is a wrapper over a Vec<u8>. Look at some of the properly encoded UTF-8 strings from Listing 8.14. First, this one:

let hello = String::from("Hola");

Here len will be 4: the vector storing the string "Hola" is 4 bytes long, because each of these letters takes 1 byte when encoded in UTF-8. The following line, however, may surprise you (the string begins with the capital Cyrillic letter Ze, not the number 3):

let hello = String::from("Здравствуйте");

Asked how long the string is, you might say 12. In fact, Rust’s answer is 24: the number of bytes it takes to encode “Здравствуйте” in UTF-8, because each Unicode scalar value in that string takes 2 bytes of storage. So an index into the string’s bytes will not always correlate to a valid Unicode scalar value.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Why a byte index is rejected

To demonstrate, consider this invalid Rust code:

let hello = "Здравствуйте";
let answer = &hello[0];

You already know that answer will not be З, the first letter.
In UTF-8 the first byte of З is 208 and the second is 151, so answer would seem to be 208 — but 208 is not a valid character on its own.
Returning 208 is likely not what a user asking for the first letter wants; however, it is the only data Rust has at byte index 0.
Users generally don’t want the byte value, even for Latin letters: if &"hi"[0] were valid code returning the byte value, it would return 104, not h.

So, to avoid returning an unexpected value and causing bugs that might not be discovered immediately, Rust doesn’t compile this code at all, and prevents misunderstandings early in the development process.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Bytes, scalar values, and grapheme clusters

From Rust’s perspective there are three relevant ways to look at strings. Take the Hindi word “नमस्ते”, written in the Devanagari script.

Bytes — stored as a vector of u8 values: 18 bytes, how computers ultimately store this data

[224, 164, 168, 224, 164, 174, 224, 164, 184, 224, 165, 141, 224, 164, 164,
224, 165, 135]

Unicode scalar values (Rust’s char type): six char values, but the fourth and sixth are not letters — they’re diacritics that don’t make sense on their own

['न', 'म', 'स', '्', 'त', 'े']

Grapheme clusters: what a person would call the four letters that make up the Hindi word

["न", "म", "स्", "ते"]

Definition 8.7 (Grapheme cluster). The way of looking at a string that comes closest to what we would call its letters.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

No O(1) indexing; be specific with slices

Rust provides different ways of interpreting the raw string data that computers store, so that each program can choose the interpretation it needs, no matter what human language the data is in.

A final reason Rust doesn’t allow indexing into a String to get a character: indexing operations are expected to always take constant time (O(1)). That performance can’t be guaranteed with a String, because Rust would have to walk through the contents from the beginning to the index to determine how many valid characters there were.

Slicing strings

Indexing into a string is often a bad idea because it’s not clear what the return type of the string-indexing operation should be: a byte value, a character, a grapheme cluster, or a string slice. If you really need to use indices to create string slices, therefore, Rust asks you to be more specific: rather than indexing using [] with a single number, use [] with a range to create a string slice containing particular bytes.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Slicing by byte range, and its panic

let hello = "Здравствуйте";
 
let s = &hello[0..4];

Here, s will be a &str that contains the first 4 bytes of the string. Each of these characters is 2 bytes, which means s will be Зд.

Slicing only part of a character’s bytes, with something like &hello[0..1], makes Rust panic at runtime, in the same way as if an invalid index were accessed in a vector:

$ cargo run
   Compiling collections v0.1.0 (file:///projects/collections)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.43s
     Running `target/debug/collections`
 
thread 'main' (6017738) panicked at src/main.rs:4:19:
end byte index 1 is not a char boundary; it is inside 'З' (bytes 0..2 of string)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Iterating over strings: chars and bytes

Use caution when creating string slices with ranges, because doing so can crash your program. The best way to operate on pieces of strings is to be explicit about whether you want characters or bytes.

For individual Unicode scalar values, use chars. On “Зд” it separates out and returns two values of type char; iterate over the result to access each one:

for c in "Зд".chars() {
    println!("{c}");
}

This code prints:

З
д

Alternatively, the bytes method returns each raw byte, which might be appropriate for your domain:

for b in "Зд".bytes() {
    println!("{b}");
}

This prints the 4 bytes that make up this string:

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.2 Storing UTF-8 Encoded Text with Strings

Handling the complexities of strings

Be sure to remember that valid Unicode scalar values may be made up of more than 1 byte.
Getting grapheme clusters from strings, as with the Devanagari script, is complex, so the standard library does not provide this functionality. Crates are available on crates.io if you need it.

To summarize, strings are complicated. Different programming languages make different choices about how to present this complexity to the programmer. Rust has chosen to make the correct handling of String data the default behavior for all Rust programs, which means programmers have to put more thought into handling UTF-8 data up front.

This trade-off exposes more of the complexity of strings than is apparent in other programming languages, but it prevents you from having to handle errors involving non-ASCII characters later in your development life cycle.

The good news: the standard library offers a lot of functionality built off the String and &str types to handle these complex situations correctly. Check the documentation for useful methods like contains, for searching in a string, and replace, for substituting parts of a string with another string. Next, something a bit less complex: hash maps!

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Hash maps

The last of our common collections is the hash map. Many programming languages support this kind of data structure, often under a different name: hash, map, object, hash table, dictionary or associative array, to name a few.

Definition 8.8 (Hash map). The type HashMap<K, V> stores a mapping of keys of type K to values of type V using a hashing function, which determines how it places these keys and values into memory.

Hash maps are useful when you want to look up data not by using an index, as you can with vectors, but by using a key that can be of any type.

Example 8.9. In a game, you could keep track of each team’s score in a hash map in which each key is a team’s name and the values are each team’s score. Given a team name, you can retrieve its score.

This section covers the basic API of hash maps; many more goodies hide in the functions the standard library defines on HashMap<K, V>. As always, check the standard library documentation for more information.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Creating a new hash map

One way to create an empty hash map is new, adding elements with insert. Listing 8.20 tracks the scores of two teams, Blue (starting with 10 points) and Yellow (starting with 50).

Listing 8.20: Creating a new hash map and inserting some keys and values

fn main() {
    use std::collections::HashMap;
 
    let mut scores = HashMap::new();
 
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
}

We first use the HashMap from the collections portion of the standard library. As the least often used of the three common collections, it isn’t brought into scope automatically in the prelude, and it has less standard-library support: there’s no built-in macro to construct one, for example.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Homogeneous keys and values; get

This HashMap has keys of type String and values of type i32. Just like vectors, hash maps store their data on the heap, and they are homogeneous: all of the keys must have the same type, and all of the values must have the same type.

We get a value out of the hash map by providing its key to the get method, as in Listing 8.21.

Listing 8.21: Accessing the score for the Blue team stored in the hash map

fn main() {
    use std::collections::HashMap;
 
    let mut scores = HashMap::new();
 
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
 
    let team_name = String::from("Blue");
    let score = scores.get(&team_name).copied().unwrap_or(0);
}

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

What get returns

let score = scores.get(&team_name).copied().unwrap_or(0);

Here, score will have the value associated with the Blue team, and the result will be 10.

Table 8.1: How Listing 8.21 handles the Option that get returns

Step	Result
get(&team_name)	Option<&V>: None if there’s no value for that key
.copied()	Option<i32> rather than Option<&i32>
.unwrap_or(0)	sets score to zero if scores has no entry for the key

Iterating over a hash map

We can iterate over each key-value pair in a hash map in a similar manner as we do with vectors, using a for loop — shown on the next slide.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Iterating over key-value pairs

fn main() {
    use std::collections::HashMap;
 
    let mut scores = HashMap::new();
 
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
 
    for (key, value) in &scores {
        println!("{key}: {value}");
    }
}

This code will print each pair in an arbitrary order:

Yellow: 50
Blue: 10

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Managing ownership in hash maps

Types that implement the Copy trait, like i32, are copied into the hash map. Owned values like String are moved, and the hash map becomes their owner (Listing 8.22).

Listing 8.22: Showing that keys and values are owned by the hash map once they’re inserted

fn main() {
    use std::collections::HashMap;
 
    let field_name = String::from("Favorite color");
    let field_value = String::from("Blue");
 
    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    // field_name and field_value are invalid at this point, try using them and
    // see what compiler error you get!
}

field_name and field_value can’t be used after being moved into the hash map by the call to insert.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

References as values; updating a hash map

If we insert references to values into the hash map, the values won’t be moved into the hash map. The values that the references point to must be valid for at least as long as the hash map is valid (more in “Validating References with Lifetimes”, Chapter 10).

Updating a hash map

Although the number of key and value pairs is growable, each unique key can only have one value associated with it at a time. Not vice versa: both the Blue team and the Yellow team could have the value 10 stored in the scores hash map.

To change the data, you must decide how to handle the case when a key already has a value assigned. You could:

replace the old value with the new value, completely disregarding the old value;
keep the old value and ignore the new one, only adding the new value if the key doesn’t already have a value;
combine the old value and the new value.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Overwriting a value

Inserting a key and value, then the same key with a different value, replaces the value associated with that key. Listing 8.23 calls insert twice, but the hash map will only contain one key-value pair, because both times we insert the value for the Blue team’s key.

Listing 8.23: Replacing a value stored with a particular key

fn main() {
    use std::collections::HashMap;
 
    let mut scores = HashMap::new();
 
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);
 
    println!("{scores:?}");
}

This code will print {"Blue": 25}. The original value of 10 has been overwritten.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Adding a key and value only if the key isn’t present

It’s common to check whether a particular key already exists in the hash map with a value, and then to act as follows:

if the key does exist in the hash map, the existing value should remain the way it is;
if the key doesn’t exist, insert it and a value for it.

Hash maps have a special API for this called entry, which takes the key you want to check as a parameter.

Definition 8.10 (Entry). The enum returned by the entry method; it represents a value that might or might not exist.

Example 8.11. Say we want to check whether the key for the Yellow team has a value associated with it. If it doesn’t, we want to insert the value 50, and the same for the Blue team. Using the entry API, the code looks like Listing 8.24 (next slide).

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

The entry API and or_insert

Listing 8.24: Using the entry method to only insert if the key does not already have a value

fn main() {
    use std::collections::HashMap;
 
    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);
 
    scores.entry(String::from("Yellow")).or_insert(50);
    scores.entry(String::from("Blue")).or_insert(50);
 
    println!("{scores:?}");
}

The or_insert method on Entry returns a mutable reference to the value for the corresponding Entry key if that key exists; if not, it inserts the parameter as the new value for this key and returns a mutable reference to the new value. This is much cleaner than writing the logic ourselves and plays more nicely with the borrow checker.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

What Listing 8.24 prints; updating from the old value

Running the code in Listing 8.24 prints:

{"Yellow": 50, "Blue": 10}

The first call to entry inserts the key for the Yellow team with the value 50, because the Yellow team doesn’t have a value already.
The second call to entry does not change the hash map, because the Blue team already has the value 10.

Updating a value based on the old value

Another common use case for hash maps is to look up a key’s value and then update it based on the old value. Listing 8.25 counts how many times each word appears in some text: a hash map with the words as keys, whose value we increment to keep track of how many times we’ve seen that word. The first time we see a word, we first insert the value 0.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Counting words with a hash map

Listing 8.25: Counting occurrences of words using a hash map that stores words and counts

fn main() {
    use std::collections::HashMap;
 
    let text = "hello world wonderful world";
 
    let mut map = HashMap::new();
 
    for word in text.split_whitespace() {
        let count = map.entry(word).or_insert(0);
        *count += 1;
    }
 
    println!("{map:?}");
}

For each word, entry(word).or_insert(0) finds or creates the count, and *count += 1 increments it.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

What Listing 8.25 prints, and why it works

This code will print:

{"world": 2, "hello": 1, "wonderful": 1}

You might see the same key-value pairs printed in a different order: recall from “Accessing Values in a Hash Map” that iterating over a hash map happens in an arbitrary order.

The split_whitespace method returns an iterator over subslices, separated by whitespace, of the value in text.
The or_insert method returns a mutable reference (&mut V) to the value for the specified key. We store it in count, so to assign to that value we must first dereference count using the asterisk (*).
The mutable reference goes out of scope at the end of the for loop, so all of these changes are safe and allowed by the borrowing rules.

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · 8.3 Storing Keys with Associated Values in Hash Maps

Hashing functions

By default, HashMap uses a hashing function called SipHash, which can provide resistance to denial-of-service (DoS) attacks involving hash tables.

SipHash is not the fastest hashing algorithm available, but the trade-off for better security that comes with the drop in performance is worth it.
If you profile your code and find that the default hash function is too slow for your purposes, you can switch to another function by specifying a different hasher.

Definition 8.12 (Hasher). A type that implements the BuildHasher trait. Traits and how to implement them are covered in Chapter 10.

You don’t necessarily have to implement your own hasher from scratch: crates.io has libraries shared by other Rust users that provide hashers implementing many common hashing algorithms.

Remark. On SipHash, see en.wikipedia.org/wiki/SipHash (the book’s footnote).

The Rust Programming Language · Ch.8 Common Collections

Chapter 8 · Summary

Summary and exercises

Vectors, strings, and hash maps provide a large amount of the functionality programs need to store, access, and modify data. You should now be equipped to solve these exercises:

Given a list of integers, use a vector and return the median (when sorted, the value in the middle position) and mode (the value that occurs most often; a hash map will be helpful here) of the list.
Convert strings to Pig Latin. The first consonant of each word is moved to the end of the word and ay is added, so first becomes irst-fay. Words that start with a vowel have hay added to the end instead (apple becomes apple-hay). Keep in mind the details about UTF-8 encoding!
Using a hash map and vectors, create a text interface to let a user add employee names to a department in a company, e.g. “Add Sally to Engineering” or “Add Amir to Sales.” Then let the user retrieve a list of all people in a department, or all people in the company by department, sorted alphabetically.

The standard library API documentation describes methods of vectors, strings, and hash maps that will help with these exercises!

Remark. We’re getting into more complex programs in which operations can fail, so it’s a perfect time to discuss error handling — the subject of Chapter 9.

The Rust Programming Language · Ch.8 Common Collections