Vec::swap_remove

Vec methods · Collections

Level: reference · for working programmers

One line: Take the element at index out in O(1), by moving the last one into its place.

pub fn swap_remove(&mut self, index: usize) -> T

Stable since 1.0.0.

No shifting: the last element fills the hole. That makes it constant time, and it changes the order — the element that was last is now at index.

That trade is the whole method. Use it wherever position carries no meaning: a pool of jobs, a set of particles, a free list. Draining such a bag with swap_remove(0) is linear overall, where remove(0) in the same loop is quadratic.

Removing the last element is identical either way.

Panics if index >= len().

Concretely: on a five-element vector, remove(0) shifts four elements and swap_remove(0) moves exactly one.

Example

vec_swap_remove.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.

fn main() {
    // O(1): the last element is moved into the hole instead of shifting.
    let mut v = vec!["a", "b", "c", "d"];
    println!("removed {:?}, left {v:?}", v.swap_remove(1));

    // So the order changes. That is the whole trade against `remove`.
    let mut ordered = vec![0, 1, 2, 3, 4];
    let mut fast = ordered.clone();
    ordered.remove(1);
    fast.swap_remove(1);
    println!("remove      {ordered:?}");
    println!("swap_remove {fast:?}");

    // Removing the last element is the same either way.
    let mut v = vec![1, 2, 3];
    println!("{:?} {v:?}", v.swap_remove(2));

    // Where it belongs: a bag where position carries no meaning.
    let mut pool = vec!["job1", "job2", "job3", "job4"];
    let mut done = vec![];
    while !pool.is_empty() {
        done.push(pool.swap_remove(0));       // always O(1)
    }
    println!("drained a pool of jobs in {} steps: {done:?}", done.len());

    // Cost, measured in element moves rather than in time: removing the front
    // of a 5-element vector shifts 4 with `remove` and moves exactly 1 here.
    println!("remove(0) on len 5 shifts 4; swap_remove(0) moves 1");

    let hook = std::panic::take_hook();
    std::panic::set_hook(Box::new(|_| {}));
    let caught = std::panic::catch_unwind(|| { let mut v = vec![1]; v.swap_remove(9); });
    std::panic::set_hook(hook);
    println!("out-of-bounds swap_remove panicked: {}", caught.is_err());
}

Verified output of vec_swap_remove.rs — regenerated by tools/run_examples.py, never hand-typed.

removed "b", left ["a", "d", "c"]
remove      [0, 2, 3, 4]
swap_remove [0, 4, 2, 3]
3 [1, 2]
drained a pool of jobs in 4 steps: ["job1", "job4", "job3", "job2"]
remove(0) on len 5 shifts 4; swap_remove(0) moves 1
out-of-bounds swap_remove panicked: true

See also

• Vec::remove — order-preserving, and O(n)
• Vec::pop — the same O(1) removal, at the end
• Vec::retain — order-preserving bulk removal in one pass

Vec::swap_remove in the standard library ↗