Accessing Elements

Getting elements of an array, slice, or vector by index is straightforward:

// Get a reference to an element
let first_line = &lines[0];

// Get a copy of an element
let fifth_number = numbers[4];       // requires Copy
let second_line = lines[1].clone();  // requires Clone

// Get a reference to a slice
let my_ref = &buffer[4..12];

// Get a copy of a slice
let my_copy = buffer[4..12].to_vec();  // requires Clone

All of these forms panic if an index is out of bounds.

Rust is picky about numeric types, and it makes no exceptions for vectors. Vector lengths and indices are of type usize. Trying to use a u32, u64, or isize as a vector index is an error. You can use an n as usize cast to convert as needed; see “Type Casts”.

Several methods provide easy access to particular elements of a vector or slice (note that all slice methods are available on arrays and vectors too):

• slice.first() returns a reference to the first element of slice, if any.

  The return type is Option<&T>, so the return value is None if slice is empty and Some(&slice[0]) if it’s not empty.

  if let Some(item) = v.first() {
      println!("We got one! {}", item);
  }

• slice.last() is similar but returns a reference to the last element.

• slice.get(index) returns Some reference to slice[index], if it exists. If slice has fewer than index+1 elements, this returns None.

  let slice = [0, 1, 2, 3];
  assert_eq!(slice.get(2), Some(&2));
  assert_eq!(slice.get(4), None);

• slice.first_mut(), slice.last_mut(), and slice.get_mut(index) are variations of these that borrow mut references.

  let mut slice = [0, 1, 2, 3];
  {
      let last = slice.last_mut().unwrap();   // type of last: &mut i32
      assert_eq!(*last, 3);
      *last = 100;
  }
  assert_eq!(slice, [0, 1, 2, 100]);

Because returning a T by value would mean moving it, methods that access elements in place typically return those elements by reference.

An exception is the .to_vec() method, which makes copies:

• slice.to_vec() clones a whole slice, returning a new vector.

  let v = [1, 2, 3, 4, 5, 6, 7, 8, 9];
  assert_eq!(v.to_vec(),
             vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
  assert_eq!(v[0..6].to_vec(),
             vec![1, 2, 3, 4, 5, 6]);

  This method is available only if the elements are cloneable, that is, where T: Clone.

Iteration

Vectors and slices are iterable, either by value or by reference, following the pattern described in “IntoIterator Implementations”:

• Iterating over a Vec<T> produces items of type T. The elements are moved out of the vector one by one, consuming it.

• Iterating over a value of type &[T; N], &[T], or &Vec<T>—that is, a reference to an array, slice, or vector—produces items of type &T, references to the individual elements, which are not moved.

• Iterating over a value of type &mut [T; N], &mut [T], or &mut Vec<T> produces items of type &mut T.

Arrays, slices, and vectors also have .iter() and .iter_mut() methods (described in “iter and iter_mut Methods”) for creating iterators that produce references to their elements.

We’ll cover some fancier ways to iterate over a slice in “Splitting”.

Growing and Shrinking Vectors

The length of an array, slice, or vector is the number of elements it contains.

• slice.len() returns a slice’s length, as a usize.

• slice.is_empty() is true if slice contains no elements (that is, slice.len() == 0).

The remaining methods in this section are about growing and shrinking vectors. They are not present on arrays and slices, which can’t be resized once created.

All of a vector’s elements are stored in a contiguous, heap-allocated chunk of memory. The capacity of a vector is the maximum number of elements that would fit in this chunk. Vec normally manages the capacity for you, automatically allocating a larger buffer and moving the elements into it when more space is needed. There are also a few methods for managing capacity explicitly:

• Vec::with_capacity(n) creates a new, empty vector with capacity n.

• vec.capacity() returns vec’s capacity, as a usize. It’s always true that vec.capacity() >= vec.len().

• vec.reserve(n) makes sure the vector has at least enough spare capacity for n more elements: that is, vec.capacity() is at least vec.len() + n. If there’s already enough room, this does nothing. If not, this allocates a larger buffer and moves the vector’s contents into it.

• vec.reserve_exact(n) is like vec.reserve(n), but tells vec not to allocate any extra capacity for future growth, beyond n. Afterward, vec.capacity() is exactly vec.len() + n.

• vec.shrink_to_fit() tries to free up the extra memory if vec.capacity() is greater than vec.len().

Vec<T> has many methods that add or remove elements, changing the vector’s length. Each of these takes its self argument by mut reference.

These two methods add or remove a single value at the end of a vector:

• vec.push(value) adds the given value to the end of vec.

• vec.pop() removes and returns the last element. The return type is Option<T>. This returns Some(x) if the popped element is x and None if the vector was already empty.

Note that .push() takes its argument by value, not by reference. Likewise, .pop() returns the popped value, not a reference. The same is true of most of the remaining methods in this section. They move values in and out of vectors.

These two methods add or remove a value anywhere in a vector:

• vec.insert(index, value) inserts the given value at vec[index], sliding any existing values in vec[index..] one spot to the right to make room.

  Panics if index > vec.len().

• vec.remove(index) removes and returns vec[index], sliding any existing values in vec[index+1..] one spot to the left to close the gap.

  Panics if index >= vec.len(), since in that case there is no element vec[index] to remove.

  The longer the vector, the slower this operation gets. If you find yourself doing vec.remove(0) a lot, consider using a VecDeque (explained in “VecDeque<T>”) instead of a Vec.

Both .insert() and .remove() are slower the more elements have to be shifted.

Three methods change the length of a vector to a specific value:

• vec.resize(new_len, value) sets vec’s length to new_len. If this increases vec’s length, copies of value are added to fill the new space. The element type must implement the Clone trait.

• vec.truncate(new_len) reduces the length of vec to new_len, dropping any elements that were in the range vec[new_len..].

  If vec.len() is already less than or equal to new_len, nothing happens.

• vec.clear() removes all elements from vec. It’s the same as vec.truncate(0).

Four methods add or remove many values at once:

• vec.extend(iterable) adds all items from the given iterable value at the end of vec, in order. It’s like a multivalue version of .push(). The iterable argument can be anything that implements IntoIterator<Item=T>.

  This method is so useful that there’s a standard trait for it, the Extend trait, which all standard collections implement. Unfortunately, this causes rustdoc to lump .extend() with other trait methods in a big pile at the bottom of the generated HTML, so it’s hard to find when you need it. You just have to remember it’s there! See “The Extend Trait” for more.

• vec.split_off(index) is like vec.truncate(index), except that it returns a Vec<T> containing the values removed from the end of vec. It’s like a multivalue version of .pop().

• vec.append(&mut vec2), where vec2 is another vector of type Vec<T>, moves all elements from vec2 into vec. Afterward, vec2 is empty.

  This is like vec.extend(vec2) except that vec2 still exists afterward, with its capacity unaffected.

• vec.drain(range), where range is a range value, like .. or 0..4, removes the range vec[range] from vec and returns an iterator over the removed elements.

There are also a few oddball methods for selectively removing some of a vector’s elements:

• vec.retain(test) removes all elements that don’t pass the given test. The test argument is a function or closure that implements FnMut(&T) -> bool. For each element of vec, this calls test(&element), and if it returns false, the element is removed from the vector and dropped.

  Apart from performance, this is like writing:

  vec = vec.into_iter().filter(test).collect();

• vec.dedup() drops repeated elements. It’s like the Unix uniq shell utility. It scans vec for places where adjacent elements are equal and drops the extra equal values, so that only one is left:

  let mut byte_vec = b"Misssssssissippi".to_vec();
  byte_vec.dedup();
  assert_eq!(&byte_vec, b"Misisipi");

  Note that there are still two 's'’s in the output. This method only removes adjacent duplicates. To eliminate all duplicates, you have three options: sort the vector before calling .dedup(); move the data into a set; or (to keep the elements in their original order) use this .retain() trick:

  let mut byte_vec = b"Misssssssissippi".to_vec();
  
  let mut seen = HashSet::new();
  byte_vec.retain(|r| seen.insert(*r));
  
  assert_eq!(&byte_vec, b"Misp");

  This works because .insert() returns false when the set already contains the item we’re inserting.

• vec.dedup_by(same) is the same as vec.dedup(), but it uses the function or closure same(&mut elem1, &mut elem2), instead of the == operator, to check whether two elements should be considered equal.

• vec.dedup_by_key(key) is the same as vec.dedup(), but it treats two elements as equal if key(&mut elem1) == key(&mut elem2).

  For example, if errors is a Vec<Box<Error>>, you can write:

  // Remove errors with redundant messages.
  errors.dedup_by_key(|err| err.description().to_string());

Of all the methods covered in this section, only .resize() ever clones values. The others work by moving values from one place to another.

Joining

Two methods work on arrays of arrays, by which we mean any array, slice, or vector whose elements are themselves arrays, slices, or vectors.

• slices.concat() returns a new vector made by concatenating all the slices.

  assert_eq!([[1, 2], [3, 4], [5, 6]].concat(),
             vec![1, 2, 3, 4, 5, 6]);

• slices.join(&separator) is the same, except a copy of the value separator is inserted between slices:

  assert_eq!([[1, 2], [3, 4], [5, 6]].join(&0),
             vec![1, 2, 0, 3, 4, 0, 5, 6]);

Swapping

There’s a convenience method for swapping two elements:

• slice.swap(i, j) swaps the two elements slice[i] and slice[j].

Vectors have a related method for efficiently removing any element:

• vec.swap_remove(i) removes and returns vec[i]. This is like vec.remove(i) except that instead of sliding the rest of the vector’s elements over to close the gap, it simply moves vec’s last element into the gap. It’s useful when you don’t care about the order of the items left in the vector.

Sorting and Searching

Slices offer three methods for sorting:

• slice.sort() sorts the elements into increasing order. This method is present only when the element type implements Ord.

• slice.sort_by(cmp) sorts the elements of slice using a function or closure cmp to specify the sort order. cmp must implement Fn(&T, &T) -> std::cmp::Ordering.

  Hand-implementing cmp is a pain, unless you delegate to a .cmp() method:

  students.sort_by(|a, b| a.last_name.cmp(&b.last_name));

  To sort by one field, using a second field as a tiebreaker, compare tuples:

  students.sort_by(|a, b| {
      let a_key = (&a.last_name, &a.first_name);
      let b_key = (&b.last_name, &b.first_name);
      a_key.cmp(&b_key)
  });

• slice.sort_by_key(key) sorts the elements of slice into increasing order by a sort key, given by the function or closure key. The type of key must implement Fn(&T) -> K where K: Ord.

  This is useful when T contains one or more ordered fields, so that it could be sorted multiple ways.

  // Sort by grade point average, lowest first.
  students.sort_by_key(|s| s.grade_point_average());

  Note that these sort-key values are not cached during sorting, so the key function may be called more than n times.

  For technical reasons, key(element) can’t return any references borrowed from the element. This won’t work:

  students.sort_by_key(|s| &s.last_name);  // error: can't infer lifetime

  Rust can’t figure out the lifetimes. But in these cases, it’s easy enough to fall back on .sort_by().

All three methods perform a stable sort.

To sort in reverse order, you can use sort_by with a cmp closure that swaps the two arguments. Taking arguments |b, a| rather than |a, b| effectively produces the opposite order. Or, you can just call the .reverse() method after sorting:

• slice.reverse() reverses a slice in place.

Once a slice is sorted, it can be efficiently searched:

• slice.binary_search(&value), slice.binary_search_by(&value, cmp), and slice.binary_search_by_key(&value, key) all search for value in the given sorted slice. Note that value is passed by reference.

  The return type of these methods is Result<usize, usize>. They return Ok(index) if slice[index] equals value under the specified sort order. If there is no such index, then they return Err(insertion_point) such that inserting value at insertion_point would preserve the order.

Of course, a binary search only works if the slice is in fact sorted in the specified order. Otherwise, the results are arbitrary—garbage in, garbage out.

Since f32 and f64 have NaN values, they do not implement Ord, and can’t be used directly as keys with the sorting and binary search methods. To get similar methods that work on floating-point data, use the ord_subset crate.

There’s one method for searching a vector that is not sorted:

• slice.contains(&value) returns true if any element of slice is equal to value. This simply checks each element of the slice until a match is found. Again, value is passed by reference.

To find the location of a value in a slice, like array.indexOf(value) in JavaScript, use an iterator:

slice.iter().position(|x| *x == value)

This returns an Option<usize>.

Comparing Slices

If a type T supports the == and != operators (the PartialEq trait, described in “Equality Tests”), then arrays [T; N], slices [T], and vectors Vec<T> support them too. Two slices are equal if they’re the same length and their corresponding elements are equal. The same goes for arrays and vectors.

If T supports the operators <, <=, >, and >= (the PartialOrd trait, described in “Ordered Comparisons”), then arrays, slices, and vectors of T do too. Slice comparisons are lexicographical.

Two convenience methods perform common slice comparisons:

• slice.starts_with(other) returns true if slice starts with a sequence of values that are equal to the elements of the slice other:

  assert_eq!([1, 2, 3, 4].starts_with(&[1, 2]), true);
  assert_eq!([1, 2, 3, 4].starts_with(&[2, 3]), false);

• slice.ends_with(other) is similar but checks the end of slice:

  assert_eq!([1, 2, 3, 4].ends_with(&[3, 4]), true);

Random Elements

Random numbers are not built into the Rust standard library. The rand crate, which provides them, offers these two methods for getting random output from an array, slice, or vector:

• rng.choose(slice) returns a reference to a random element of a slice. Like slice.first() and slice.last(), this returns an Option<&T> that is None only if the slice is empty.

• rng.shuffle(slice) randomly reorders the elements of a slice in place. The slice must be passed by mut reference.

These are methods of the rand::Rng trait, so you need a Rng, a random number generator, in order to call them. Fortunately it’s easy to get one by calling rand::thread_rng(). To shuffle the vector my_vec, we can write:

use rand::{Rng, thread_rng};

thread_rng().shuffle(&mut my_vec);

Rust Rules Out Invalidation Errors

Most mainstream programming languages have collections and iterators, and they all have some variation on this rule: don’t modify a collection while you’re iterating over it. For example, the Python equivalent of a vector is a list:

my_list = [1, 3, 5, 7, 9]

Suppose we try to remove all values greater than 4 from my_list:

for index, val in enumerate(my_list):
    if val > 4:
        del my_list[index]  # bug: modifying list while iterating

print(my_list)

(The enumerate function is Python’s equivalent of Rust’s .enumerate() method, described in “enumerate”.)

This program, surprisingly, prints [1, 3, 7]. But seven is greater than four. How did that slip through? This is an invalidation error: the program modifies data while iterating over it, invalidating the iterator. In Java, the result would be an exception; in C++, undefined behavior. In Python, while the behavior is well-defined, it’s unintuitive: the iterator skips an element. val is never 7.

Let’s try to reproduce this bug in Rust:

fn main() {
    let mut my_vec = vec![1, 3, 5, 7, 9];

    for (index, &val) in my_vec.iter().enumerate() {
        if val > 4 {
            my_vec.remove(index);  // error: can't borrow `my_vec` as mutable
        }
    }
    println!("{:?}", my_vec);
}

Naturally, Rust rejects this program at compile time. When we call my_vec.iter(), it borrows a shared (non-mut) reference to the vector. The reference lives as long as the iterator, to the end of the for loop. We can’t modify the vector by calling my_vec.remove(index) while a non-mut reference exists.

Having an error pointed out to you is nice, but of course, you still need to find a way to get the desired behavior! The easiest fix here is to write:

my_vec.retain(|&val| val <= 4);

Or, you can do what you’d do in Python or any other language: create a new vector using a filter.

Entries

Both HashMap and BTreeMap have a corresponding Entry type. The point of entries is to eliminate redundant map lookups. For example, here’s some code to get or create a student record:

// Do we already have a record for this student?
if !student_map.contains_key(name) {
    // No: create one.
    student_map.insert(name.to_string(), Student::new());
}
// Now a record definitely exists.
let record = student_map.get_mut(name).unwrap();
...

This works fine, but it accesses student_map two or three times, doing the same lookup each time.

The idea with entries is that we do the lookup just once, producing an Entry value that is then used for all subsequent operations. This one-liner is equivalent to all the code above, except that it only does the lookup once:

let record = student_map.entry(name.to_string()).or_insert_with(Student::new);

The Entry value returned by student_map.entry(name.to_string()) acts like a mutable reference to a place within the map that’s either occupied by a key-value pair, or vacant, meaning there’s no entry there yet. If vacant, the entry’s .or_insert_with() method inserts a new Student. Most uses of entries are like this: short and sweet.

All Entry values are created by the same method:

• map.entry(key) returns an Entry for the given key. If there’s no such key in the map, this returns a vacant Entry.

  This method takes its self argument by mut reference and returns an Entry with a matching lifetime:

  pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>

  The Entry type has a lifetime parameter 'a because it’s effectively a fancy kind of borrowed mut reference to the map. As long as the Entry exists, it has exclusive access to the map.

  Back in “Structs Containing References”, we saw how to store references in a type, and how that affects lifetimes. Now we’re seeing what that looks like from a user’s perspective. That’s what’s going on with Entry.

  Unfortunately, it is not possible to pass a reference of type &str to this method if the map has String keys. The .entry() method, in that case, requires a real String.

Entry values provide two methods for filling in vacant entries:

• map.entry(key).or_insert(value) ensures that map contains an entry with the given key, inserting a new entry with the given default value if needed. It returns a mut reference to the new or existing value.

  Suppose we need to count votes. We can write:

  let mut vote_counts: HashMap<String, usize> = HashMap::new();
  for name in ballots {
      let count = vote_counts.entry(name).or_insert(0);
      *count += 1;
  }

  .or_insert() returns a mut reference, so the type of count is &mut usize.

• map.entry(key).or_insert_with(default_fn) is the same, except that if it needs to create a new entry, it calls default_fn() to produce the default value. If there’s already an entry for key in the map, then default_fn is not used.

  Suppose we want to know which words appear in which files. We can write:

  // This map contains, for each word, the set of files it appears in.
  let mut word_occurrence: HashMap<String, HashSet<String>> =
      HashMap::new();
  for file in files {
      for word in read_words(file)? {
          let set = word_occurrence
              .entry(word)
              .or_insert_with(HashSet::new);
          set.insert(file.clone());
      }
  }

The Entry type is an enum, defined like this for HashMap (and similarly for BTreeMap):

// (in std::collections::hash_map)
pub enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>)
}

The OccupiedEntry and VacantEntry types have methods for inserting, removing, and accessing entries without repeating the initial lookup. You can find them in the online documentation. The extra methods can occasionally be used to eliminate a redundant lookup or two, but .or_insert() and .or_insert_with() cover the common cases.

Map Iteration

There are several ways to iterate over a map:

• Iterating by value (“for (k, v) in map”) produces (K, V) pairs. This consumes the map.

• Iterating over a shared reference (“for (k, v) in &map”) produces (&K, &V) pairs.

• Iterating over a mut reference (“for (k, v) in &mut map”) produces (&K, &mut V) pairs. (Again, there’s no way to get mut access to keys stored in a map, because the entries are organized by their keys.)

Like vectors, maps have .iter() and .iter_mut() methods which return by-reference iterators, just like iterating over &map or &mut map. In addition:

• map.keys() returns an iterator over just the keys, by reference.

• map.values() returns an iterator over the values, by reference.

• map.values_mut() returns an iterator over the values, by mut reference.

All HashMap iterators visit the map’s entries in an arbitrary order. BTreeMap iterators visit them in order by key.

Using a Custom Hashing Algorithm

The hash method is generic, so the Hash implementations shown above can feed data to any type that implements Hasher. This is how Rust supports pluggable hashing algorithms. Hash and Hasher are buddy traits, as explained in “Buddy Traits (or How rand::random() Works)”.

A third trait, std::hash::BuildHasher, is the trait for types that represent the initial state of a hashing algorithm. Each Hasher is single-use, like an iterator: you use it once and throw it away. A BuildHasher is reusable.

Every HashMap contains a BuildHasher that it uses each time it needs to compute a hash code. The BuildHasher value contains the key, initial state, or other parameters that the hashing algorithm needs every time it runs.

The complete protocol for computing a hash code looks like this:

use std::hash::{Hash, Hasher, BuildHasher};

fn compute_hash<B, T>(builder: &B, value: &T) -> u64
    where B: BuildHasher, T: Hash
{
    let mut hasher = builder.build_hasher();  // 1. start the algorithm
    value.hash(&mut hasher);                  // 2. feed it data
    hasher.finish()                           // 3. finish, producing a u64
}

HashMap calls these three methods every time it needs to compute a hash code. All the methods are inlineable, so it’s very fast.

Rust’s default hashing algorithm is a well-known algorithm called SipHash-1-3. SipHash is fast, and it’s very good at minimizing hash collisions. In fact, it’s a cryptographic algorithm: there’s no known efficient way to generate SipHash-1-3 collisions. As long as a different, unpredictable key is used for each hash table, Rust is secure against a kind of denial-of-service attack called HashDoS, where attackers deliberately use hash collisions to trigger worst-case performance in a server.

But perhaps you don’t need that for your application. If you’re storing many small keys, such as integers or very short strings, it is possible to implement a faster hash function, at the expense of HashDoS security. The fnv crate implements one such algorithm, the Fowler-Noll-Vo hash. To try it out, add this line to your Cargo.toml:

[dependencies]
fnv = "1.0"

Then import the map and set types from fnv:

extern crate fnv;

use fnv::{FnvHashMap, FnvHashSet};

You can use these two types as drop-in replacements for HashMap and HashSet. A peek inside the fnv source code reveals how they’re defined:

/// A `HashMap` using a default FNV hasher.
pub type FnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;

/// A `HashSet` using a default FNV hasher.
pub type FnvHashSet<T> = HashSet<T, FnvBuildHasher>;

The standard HashMap and HashSet collections accept an optional extra type parameter specifying the hashing algorithm; FnvHashMap and FnvHashSet are generic type aliases for HashMap and HashSet, specifying an FNV hasher for that parameter.