Vectors

RecipeCrates
Store Homogeneous Data in a Contiguous, Growable Array with Vecstd
Vec Memory Allocationstd

Store Homogeneous Data in a Contiguous, Growable Array with Vec

std

The vector type Vec↗ is the go-to, general-purpose data structure, when you need a collection of elements that can change in size.

  • It is a contiguous, growable, owned, heap-allocated array.
  • It can only store values that are the same type.
  • It has O(1) indexing, amortized O(1) push↗ (to the end) and O(1) pop (from the end).
  • Many other data structures are built upon or interact with Vec.

The following example demonstrates common operations:

fn main() {
    // Vectors are resizable arrays.

    // Create a `Vec` with a macro:
    let _numbers: Vec<i32> = vec![1, 2, 3];

    // The above is a shortcut for:
    let mut numbers: Vec<i32> = Vec::new(); // Empty vector.
    numbers.push(1); // Add an element.
    numbers.push(2);
    numbers.push(3);

    assert_eq!(numbers.len(), 3);

    // For large vectors, reserve capacity when creating the `Vec`:
    let mut vec: Vec<i32> = Vec::with_capacity(10);
    vec.push(86);
    assert!(vec.capacity() >= 10);

    // Create a `Vec` with a macro - with repeated elements.
    // In this case, ten zeroes:
    let mut zeroes: Vec<u8> = vec![0u8; 10];

    // Read a value at a given index:
    // 1. Panics if out of bounds.
    let _third: &i32 = &numbers[2];
    // 2. Returns `None` if out of bounds.
    let _third: Option<&i32> = numbers.get(2);

    // Write at a given index:
    numbers[0] = 1;

    // Extend with an array:
    numbers.extend([4, 5, 6]);

    // Use a Vec<T> as a stack:
    // - Add an element to the end.
    numbers.push(4);
    // - Remove the last element.
    numbers.pop();

    // Iterate over a `Vec`:
    println!("Iterate using a `for` loop:");
    for num in &numbers {
        println!("{num}");
    }

    println!("Iterate using `iter()`:");
    numbers.iter().for_each(|num| println!("{num}"));

    // Modify a vector while iterating (requires `let mut`):
    for num in &mut zeroes {
        *num += 5; // Use the dereference operator to access the value.
    }

    // Search in the `Vec` using `position`:
    if let Some(index) = numbers.iter().position(|&x| x == 2) {
        println!("Found the value `2` at index: {index}");
    } else {
        println!("Not found.");
    }

    // Sort:
    let mut sorted_numbers = numbers.clone();
    sorted_numbers.sort();
    println!("Sorted numbers: {sorted_numbers:?}");

    // Filter elements (keep only even numbers):
    let even_numbers: Vec<i32> =
        numbers.iter().filter(|&x| x % 2 == 0).cloned().collect();
    println!("Even numbers: {even_numbers:?}");

    // Map elements (square each number).
    // Collect the results into a new `Vec`.
    let squared_numbers: Vec<i32> = numbers.iter().map(|&x| x * x).collect();
    println!("Squared numbers: {squared_numbers:?}");

    // Reduce:
    let sum: i32 = numbers.iter().sum();
    println!("Sum: {sum}");

    // Fold:
    let product: i32 = numbers.iter().fold(1, |acc, &x| acc * x);
    println!("Product: {product}");

    // Get a slice of the `Vec`, using `&` and `[n..m]`:
    let slice: &[i32] = &numbers[1..3]; // Second and third elements.
    println!("Slice: {slice:?}");

    // Slice over the entire array:
    let _whole_cake: &[_] = &numbers[..];

    // In Rust, it's common to use slices, rather than vectors, as
    // arguments, when you just want to provide read access:
    fn read_vec(v: &[i32]) {
        println!("Inside read_vec: {v:?}");
    }
    // `Vec` coerces to a slice.
    read_vec(&numbers);

    // Iterate over a slice:
    println!("Iterate over a slice:");
    for num in slice.iter() {
        println!("{num}");
    }

    // Mutable slices:
    let mut mutable_numbers = vec![1, 2, 3, 4, 5];
    let mutable_slice: &mut [i32] = &mut mutable_numbers[1..4];

    // Iterate over a mutable slice and modify elements:
    for num in mutable_slice.iter_mut() {
        *num *= 2;
    }
    println!("After slice mutation: {mutable_numbers:?}");

    // Chain iterators for complex operations:
    let numbers2: Vec<i32> = vec![10, 20, 30, 40, 50];
    let filtered_squared_sum: i32 =
        numbers2.iter().filter(|&x| x > &20).map(|&x| x * x).sum();

    println!("Filtered squared sum: {filtered_squared_sum}");

    // Use `enumerate` to get both index and value during iteration:
    println!("Enumerate:");
    for (index, value) in numbers2.iter().enumerate() {
        println!("Index: {index}, Value: {value}");
    }

    // Use `zip` to combine two iterators (numbers and letters):
    let letters = vec!['a', 'b', 'c'];
    println!("Zip:");
    for (number, letter) in numbers2.iter().zip(letters.iter()) {
        println!("Number: {number}, Letter: {letter}");
    }
}

Vec Memory Allocation

Vec allocates memory on the heap (using the global allocator in std::alloc) to store its elements. Vec maintains a capacity (how many elements it can hold without reallocating) and a length (how many elements it currently holds).

When you push elements and exceed the current capacity, Vec↗ reallocates memory - usually by doubling the capacity. This amortized growth strategy ensures that pushing elements remains efficient over time. The old memory is deallocated, and the contents are copied to the new, larger allocation.

If allocation fails, Rust will abort the program using alloc::handle_alloc_error. For zero-sized types (like ()), Vec avoids actual allocation.

Use the following suggestions to optimize memory usage:

// If you know the size in advance, using `Vec::with_capacity(n)` can avoid multiple reallocations:
let mut v = Vec::with_capacity(100);
// Shrink after removing elements or if the vector has grown significantly beyond what you need:
v.shrink_to_fit();
// Cloning large vectors or their elements can be costly:
// - Prefer borrowing (`&T`) or moving (`T`) when possible.
// - Use slices when you don't need ownership:
fn process(_data: &[T]) { }
// Reuse vectors: Instead of creating new vectors in a loop, clear and reuse them to keep the capacity:
v.clear();

For fixed-size collections, use arrays. For small collections, using stack-allocated vectors may be more efficient by avoiding heap allocation altogether.

Read Implementing Vec↗ for more details about Vec memory management.

Other Data Structures

  • B-trees.
  • Binary Heaps.
  • Hashmaps.
  • Heapless data structures.
  • Other Maps.
  • Slices.
  • Stack Allocated Arrays.
  • Stacks and Queues.
  • Strings.
  • Algorithms.
  • Encoding.
  • Rust Patterns.
  • Sorting.
  • Typecasts.