4.1 · Vec<T>: The Workhorse Collection

Domain 4 — Collections Deep Dive Duration: ~15 minutes Library components: std::vec::Vec, std::vec::IntoIter, std::vec::Drain, std::vec::Splice

Introduction

Vec<T> is the most common collection in Rust. It is a contiguous, growable array type, and its elements are on the heap. Almost every non-trivial Rust program uses it. Through Deref, a Vec also gets hundreds of methods from [T].

This tutorial shows:

• The internal layout of Vec<T> (pointer, length, capacity), and why it is always 24 bytes on 64-bit platforms for each T.
• How to divide a Vec into these three parts with Vec::into_parts, and how to build it again with Vec::from_parts (stabilized in 1.99).
• The growth strategy, and how to control allocation with with_capacity, reserve, reserve_exact, shrink_to_fit, and shrink_to.
• How to get a mutable reference to the new element with push_mut and insert_mut (stabilized in 1.95).
• How to filter in place with retain, and how to remove consecutive duplicates with dedup, dedup_by, and dedup_by_key.
• How to remove and replace many elements in one call with drain, splice, and split_off.
• How Vec<T> implements Deref<Target = [T]> and thus gives you every slice method at no cost.
• The difference between extend_from_slice and extend.
• How to convert a Vec to a Box<[T]> with into_boxed_slice.

Internal Layout and Capacity Management

A Vec<T> is three machine words on the stack:

• a pointer to the heap allocation
• a usize length: the number of initialized elements
• a usize capacity: the number of elements that the allocation can contain before a reallocation

Each of these values has the size of a pointer. Thus size_of::<Vec<T>>() is always 24 bytes on a 64-bit platform. The size is the same when T is u8 and when T is i64.

Figure: Vec<T> Memory Layout

use std::mem;

// The size of the Vec value does not include the heap buffer.
assert_eq!(mem::size_of::<Vec<u8>>(), mem::size_of::<Vec<i64>>());  // both are 24 on 64-bit

Since Rust 1.99, Vec::into_parts gives you these three words as values, and Vec::from_parts builds the Vec again. The pointer has the type NonNull<T>, because a Vec pointer is never null. Code that stores a buffer as a raw pointer (an FFI boundary, a custom data structure) uses this pair:

use std::ptr::NonNull;

let mut samples: Vec<u32> = Vec::with_capacity(8);
samples.extend([10, 20, 30]);   // len 3, capacity 8

// into_parts consumes the Vec. No destructor runs, so the buffer stays allocated.
let (ptr, len, cap): (NonNull<u32>, usize, usize) = samples.into_parts();
assert_eq!((len, cap), (3, 8));

// SAFETY: index 3 is inside the allocation of 8 elements.
unsafe { ptr.add(3).write(40) };

// SAFETY: the pointer and the capacity come from into_parts, and 4 elements are initialized.
let rebuilt: Vec<u32> = unsafe { Vec::from_parts(ptr, len + 1, cap) };
assert_eq!(rebuilt, [10, 20, 30, 40]);   // `rebuilt` owns and frees the buffer

04_20_vec_into_parts.rs prints:

parts: len = 3, cap = 8
rebuilt: [10, 20, 30, 40], cap = 8
empty Vec round trip: len = 0, cap = 0

All assertions passed.

into_raw_parts and from_raw_parts are the same pair with a *mut T pointer. Tutorial 16.3 explains NonNull.

with_capacity

When you know the necessary number of elements before you start, use Vec::with_capacity(n). It allocates space for n elements and does not initialize them. The length stays at zero. Subsequent pushes that stay in that capacity never reallocate.

let mut buf: Vec<u8> = Vec::with_capacity(1024);
assert_eq!(buf.len(), 0);            // no element is initialized
assert!(buf.capacity() >= 1024);     // the capacity can be larger than the request

let ptr_before = buf.as_ptr();       // the address of the heap buffer
buf.extend_from_slice(&[0xDE, 0xAD, 0xBE, 0xEF]);   // 4 bytes: they fit in the capacity
let ptr_after = buf.as_ptr();
assert!(std::ptr::eq(ptr_before, ptr_after)); // same address: no reallocation

Growth strategy

When a Vec has no more free capacity, it reallocates. The specification does not guarantee the exact strategy, but the current implementation approximately doubles the capacity. For 20 pushes into an empty Vec<i32>, the capacity changes as follows:

len= 1, capacity grew: 0 -> 4
len= 5, capacity grew: 4 -> 8
len= 9, capacity grew: 8 -> 16
len=17, capacity grew: 16 -> 32

Because the capacity doubles, push is amortized O(1). But if you prevent those intermediate allocations with with_capacity, you save time in performance-critical loops.

reserve, reserve_exact, shrink_to_fit, shrink_to

• reserve(n) makes sure that there is space for at least n more elements. The allocator may give more.
• reserve_exact(n) requests a capacity of exactly len + n. This value is still only a lower bound, because the allocator may round it up.
• shrink_to_fit() releases all unused capacity. The capacity becomes as near to the length as the allocator permits.
• shrink_to(min) releases capacity but keeps space for at least min elements. Use it when you know that the Vec will grow again to a moderate size.

let mut data = vec![1, 2, 3];
data.reserve(100);                      // space for 100 more elements
assert!(data.capacity() >= 103);        // len (3) + requested (100)

let mut bloated = Vec::with_capacity(1000);
bloated.extend_from_slice(&[1, 2, 3, 4, 5]);   // len 5, capacity 1000
bloated.shrink_to_fit();                // releases the unused capacity
assert!(bloated.capacity() <= 10);      // the capacity is now near the length

let mut partial = Vec::with_capacity(200);
partial.extend(0..10);                  // len 10, capacity 200
partial.shrink_to(50);                  // keeps a capacity of at least 50
assert!(partial.capacity() >= 50 && partial.capacity() < 200);

push_mut and insert_mut: a handle to the new element

Since Rust 1.95, push_mut and insert_mut do the same work as push and insert, but they return &mut T. This value is a mutable reference to the new element. You do not need v.push(x) and then v.last_mut().unwrap() to change the new element immediately:

let mut scores: Vec<i32> = Vec::new();
let newest = scores.push_mut(10);      // newest: &mut i32, points to the new 10
*newest += 5;                          // the element is now 15
let first = scores.insert_mut(0, 1);   // inserts 1 at index 0, first: &mut i32
*first *= 100;                         // the element at index 0 is now 100
assert_eq!(scores, [100, 15]);

The returned reference borrows the Vec mutably. Thus the borrow must end before you use the Vec again. The borrow checker applies the same rule as for last_mut.

04_01_vec_layout_capacity.rs prints:

size_of::<Vec<u8>>()  = 24 bytes
size_of::<Vec<i64>>() = 24 bytes

with_capacity(1024): len=0, cap=1024
after 4 pushes: len=4, cap=1024, ptr_moved=false

Growth observation:
  len= 1, capacity grew: 0 → 4
  len= 5, capacity grew: 4 → 8
  len= 9, capacity grew: 8 → 16
  len=17, capacity grew: 16 → 32

after reserve(100): len=3, cap=103
after reserve_exact(5): len=10, cap=15

before shrink: len=5, cap=1000
after shrink_to_fit: len=5, cap=5

shrink_to(50): len=10, cap=50

push_mut/insert_mut: [100, 15]

All assertions passed.

retain and dedup

retain: filtering in place

retain examines each element of the Vec and keeps only the elements for which the predicate returns true. It operates in place, with no new allocation. It keeps the relative order of the elements that stay.

// -999.0 is a sentinel value that represents a sensor error.
let mut readings = vec![22.1, -999.0, 23.4, -999.0, 24.0, 22.8];
readings.retain(|&x| x > -100.0);   // keeps the values above -100.0
assert_eq!(readings, [22.1, 23.4, 24.0, 22.8]);

The closure receives an immutable reference to each element. But the closure can capture mutable state from the surrounding scope. For example, it can count the elements that retain removes:

let mut nums = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let mut removed = 0;
nums.retain(|&x| {
    // For a multiple of 3: count it, and return false to remove it.
    if x % 3 == 0 { removed += 1; false } else { true }
});
// nums is now [1, 2, 4, 5, 7, 8, 10]
assert_eq!(removed, 3);   // 3, 6, and 9

dedup: collapsing consecutive duplicates

dedup() removes consecutive equal elements and keeps the first element of each run. It compares only adjacent pairs. Thus dedup removes all duplicates only if the Vec is sorted (or grouped in some other way).

let mut sorted = vec![1, 1, 2, 3, 3, 3, 4, 4, 5];
sorted.dedup();   // equal values are adjacent, so dedup removes all duplicates
assert_eq!(sorted, [1, 2, 3, 4, 5]);

// In unsorted data, the duplicates that are not adjacent stay.
let mut unsorted = vec![1, 2, 1, 3, 2, 3];
unsorted.dedup();
assert_eq!(unsorted, [1, 2, 1, 3, 2, 3]); // dedup removed nothing

dedup_by: custom equality

With dedup_by, you define when two consecutive elements are "the same". The closure receives mutable references to the pair (a, b). a is the current element, and b is the previous element that dedup_by kept.

let mut temps: Vec<f64> = vec![20.0, 20.3, 20.1, 21.5, 21.7, 23.0];
// If the closure returns true, dedup_by removes `a` and keeps `b`.
temps.dedup_by(|a, b| (*a - *b).abs() < 0.5);
// 20.3 and 20.1 are less than 0.5 from 20.0. 21.7 is less than 0.5 from 21.5.
assert_eq!(temps, [20.0, 21.5, 23.0]);

dedup_by_key: extract a comparison key

dedup_by_key gets a key from each element and removes the consecutive elements that have equal keys:

let mut words = vec!["Hello".to_string(), "hello".to_string(),
                     "HELLO".to_string(), "world".to_string(),
                     "World".to_string()];
words.dedup_by_key(|w| w.to_lowercase());   // the key ignores the letter case
assert_eq!(words.len(), 2); // "Hello" and "world" stay

04_02_vec_retain_dedup.rs prints:

before retain: [22.1, -999.0, 23.4, -999.0, 24.0, 22.8]
after retain:  [22.1, 23.4, 24.0, 22.8]

kept (not divisible by 3): [1, 2, 4, 5, 7, 8, 10], removed 3

before dedup: [1, 1, 2, 3, 3, 3, 4, 4, 5]
after dedup:  [1, 2, 3, 4, 5]

unsorted after dedup: [1, 2, 1, 3, 2, 3]

before dedup_by: [20.0, 20.3, 20.1, 21.5, 21.7, 23.0]
after dedup_by (Δ<0.5): [20.0, 21.5, 23.0]

before dedup_by_key: ["Hello", "hello", "HELLO", "world", "World"]
after dedup_by_key:  ["Hello", "world"]

All assertions passed.

drain, splice, and split_off

These three methods remove and replace many elements in one call. The same operations with individual remove calls are difficult to write and prone to errors.

Figure: drain, splice, and split_off Operations

drain: extract a range

drain(range) removes the elements in the specified range and returns a Drain iterator that yields them. The remaining elements move to close the gap, but the Vec keeps its allocation.

let mut queue = vec!["a", "b", "c", "d", "e", "f"];
// Remove indices 1, 2, and 3. The end of the range is exclusive.
let drained: Vec<&str> = queue.drain(1..4).collect();
assert_eq!(drained, ["b", "c", "d"]);
assert_eq!(queue, ["a", "e", "f"]);   // "e" and "f" moved to close the gap

A common pattern is drain(..), which removes all the elements and keeps the allocation for the next use. It is equivalent to a clear() that also gives you the removed elements:

// `queue` is the Vec<&str> from the previous snippet: ["a", "e", "f"].
let cap_before = queue.capacity();
let all: Vec<&str> = queue.drain(..).collect();   // all is ["a", "e", "f"]
assert!(queue.is_empty());
assert_eq!(queue.capacity(), cap_before);         // the allocation stays

splice: replace a range with new elements

splice(range, iter) does three things:

• It removes the elements in range.
• It inserts all the items of iter at that position.
• It returns a Splice iterator that yields the removed elements.

The length of the replacement can be different from the length of the removed range.

let mut colors = vec!["red", "green", "blue", "yellow"];
// Replace the 2 elements at indices 1..3 with 3 new elements.
let replaced: Vec<&str> = colors.splice(1..3, ["cyan", "magenta", "black"]).collect();
assert_eq!(replaced, ["green", "blue"]);   // the removed elements
assert_eq!(colors, ["red", "cyan", "magenta", "black", "yellow"]);

Two special cases extend the use of splice:

• Insertion with no removal: use an empty range at the insertion point.

  let mut nums = vec![1, 2, 5, 6];
  // The range 2..2 is empty: splice removes nothing and inserts at index 2.
  nums.splice(2..2, [3, 4]);
  assert_eq!(nums, [1, 2, 3, 4, 5, 6]);

• Removal with no insertion: use an empty iterator as the replacement.

  let mut letters = vec!['a', 'b', 'c', 'd', 'e'];
  // The replacement `[]` is empty: splice only removes indices 1..4.
  let cut: Vec<char> = letters.splice(1..4, []).collect();
  assert_eq!(cut, ['b', 'c', 'd']);
  assert_eq!(letters, ['a', 'e']);

split_off: divide a vec at an index

split_off(mid) divides the Vec into two. The original Vec keeps the elements 0..mid, and the returned Vec gets the elements mid..len. Each Vec owns its allocation.

let mut front = vec![10, 20, 30, 40, 50];
let back = front.split_off(3);     // back: Vec<i32>, the elements from index 3
assert_eq!(front, [10, 20, 30]);   // front keeps indices 0..3
assert_eq!(back, [40, 50]);

04_03_vec_drain_splice.rs prints:

before drain: ["a", "b", "c", "d", "e", "f"]
drained:      ["b", "c", "d"]
after drain:  ["a", "e", "f"]

drain(..): removed ["a", "e", "f"], len=0, cap=6

before splice: ["red", "green", "blue", "yellow"]
replaced:      ["green", "blue"]
after splice:  ["red", "cyan", "magenta", "black", "yellow"]

insert via splice: [1, 2, 3, 4, 5, 6], removed: []
delete via splice: ['a', 'e'], cut: ['b', 'c', 'd']

before split_off(3): [10, 20, 30, 40, 50]
front: [10, 20, 30]
back:  [40, 50]

All assertions passed.

Deref to Slice, extend, and into_boxed_slice

Vec<T> as Deref<Target = [T]>

Vec<T> implements Deref<Target = [T]>. Thus, where the code expects a &[T], the compiler automatically coerces a &Vec<T>. In practice, this is how Vec "inherits" every slice method and does not implement them again. Examples are contains, first, last, iter, windows, chunks, and binary_search, and there are hundreds more.

// The parameter is a slice, not a Vec.
fn sum_of(data: &[i32]) -> i32 {
    data.iter().sum()
}

let v = vec![10, 20, 30, 40];
let total = sum_of(&v);          // &Vec<i32> coerces to &[i32]
assert_eq!(total, 100);

assert!(v.contains(&20));        // a slice method, called on a Vec
assert_eq!(v.first(), Some(&10));
assert_eq!(v.last(), Some(&40));

The same function accepts arrays, because arrays also coerce to slices:

// `sum_of` is the function from the previous snippet.
let arr = [1, 2, 3];
assert_eq!(sum_of(&arr), 6);     // &[i32; 3] coerces to &[i32]

The design rule: write functions that take &[T], not &Vec<T>. Then a caller with a Vec, an array, or a different contiguous buffer can pass its data.

extend_from_slice vs. extend

The two methods append elements to a Vec, but from different sources:

• extend_from_slice(&[T]) copies from a contiguous slice. For Copy types, the compiler can emit one memcpy. Thus it is the fastest method to append many elements from a slice.
• extend(iter) accepts any IntoIterator<Item = T>. It is more flexible: it accepts ranges, other Vec values, hash maps, and all other iterable values. But the compiler may not always optimize it to a memcpy.

let mut a = vec![1, 2, 3];
a.extend_from_slice(&[4, 5, 6]);   // copies the three values from the slice
assert_eq!(a, [1, 2, 3, 4, 5, 6]);

let mut b = vec![1, 2];
b.extend([3, 4, 5]);   // an array implements IntoIterator
b.extend(6..=8);        // a range implements IntoIterator too
assert_eq!(b, [1, 2, 3, 4, 5, 6, 7, 8]);

When you have a slice, prefer extend_from_slice because it is clear and fast. When you must append from sources of different types, use extend.

into_boxed_slice

into_boxed_slice() converts a Vec<T> into a Box<[T]> and releases all excess capacity. The result is a slice on the heap with no capacity field: only a pointer and a length. Use it when the collection is complete and you want to keep it at its exact size.

let mut big = Vec::with_capacity(1000);
big.extend(0..5);                                 // len 5, capacity 1000
let boxed: Box<[i32]> = big.into_boxed_slice();   // releases the unused capacity
assert_eq!(&*boxed, &[0, 1, 2, 3, 4]);

// Convert the box to a Vec again if the collection must grow.
let restored: Vec<i32> = boxed.into_vec();
assert_eq!(restored, [0, 1, 2, 3, 4]);

Slice indexing on Vec

Because Vec derefs to [T], all the slice indexing syntax is available on a Vec:

let v = vec!['a', 'b', 'c', 'd', 'e'];
let middle = &v[1..4];               // middle: &[char], borrows indices 1, 2, and 3
assert_eq!(middle, ['b', 'c', 'd']);

// get() returns an Option, so an index that is out of range does not panic.
assert_eq!(v.get(2), Some(&'c'));
assert_eq!(v.get(99), None);

04_04_vec_deref_slice.rs prints:

sum_of(&v) = 100
v.contains(&20) = true, first = Some(10), last = Some(40)
sum_of(&[1,2,3]) = 6

after extend_from_slice: [1, 2, 3, 4, 5, 6]
after extend: [1, 2, 3, 4, 5, 6, 7, 8]

before into_boxed_slice: len=5, cap=1000
boxed slice len = 5
restored vec: [0, 1, 2, 3, 4]

v[1..4] = ['b', 'c', 'd']
v.get(2) = Some('c'), v.get(99) = None

All assertions passed.

Summary

Code Examples