104. Vec::swap_remove — O(1) Removal When Order Doesn't Matter

Calling Vec::remove(i) shifts every element after i left by one — that’s O(n) per call. If you don’t care about order, swap_remove does the same job in O(1).

The hidden cost of Vec::remove

remove takes the value out of the vector, but to keep the rest in order it has to shift every following element left by one slot. On a long vector, removing near the front is a giant memcpy:

1
2
3
4
5

let mut v = vec![1, 2, 3, 4, 5];
let removed = v.remove(1);

assert_eq!(removed, 2);
assert_eq!(v, [1, 3, 4, 5]);

Inside a loop — “remove every item that matches X” — that O(n) cost compounds into O(n²). A tight loop that should be linear silently becomes quadratic.

swap_remove: trade order for speed

swap_remove(i) removes the element at index i by swapping it with the last element, then popping the tail. No shifting, no memcpy chain — just one swap and a pop:

1
2
3
4
5
6

let mut v = vec![1, 2, 3, 4, 5];
let removed = v.swap_remove(1);

assert_eq!(removed, 2);
// 5 took 2's spot — order is gone, but the op was O(1).
assert_eq!(v, [1, 5, 3, 4]);

If your Vec is really a set — entities in a game world, pending jobs in a worker pool, items keyed by id elsewhere — order rarely matters. swap_remove is free.

Removing many items in place

The classic mistake: iterate forward calling remove. swap_remove lets you do it without the O(n²) blow-up. Walk by index and don’t bump the cursor when you remove:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

let mut nums = vec![1, 2, 3, 4, 5, 6, 7, 8];

let mut i = 0;
while i < nums.len() {
    if nums[i] % 2 == 0 {
        nums.swap_remove(i);
        // Don't increment — a new element is now at position i.
    } else {
        i += 1;
    }
}

nums.sort(); // canonicalize for the assert
assert_eq!(nums, [1, 3, 5, 7]);

For bulk predicate-based filtering, Vec::retain stays cleaner (and is also O(n)). Reach for swap_remove when you have a specific index you want gone in O(1).

With structs

swap_remove returns the removed value, so you can hand it off to another collection on the way out:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#[derive(PartialEq, Debug)]
struct Job { id: u32 }

let mut queue = vec![
    Job { id: 1 },
    Job { id: 2 },
    Job { id: 3 },
    Job { id: 4 },
];

let pulled = queue.swap_remove(0);

assert_eq!(pulled, Job { id: 1 });
assert_eq!(queue.len(), 3);

When to reach for it

Use swap_remove whenever you’d write remove(i) and the surrounding code doesn’t depend on element order. Order-preserving removal still needs remove, but most “remove one item from this Vec” code is order-agnostic — and swap_remove turns an O(n) pothole into a one-line O(1) win. Stable since Rust 1.0, one of those quietly-essential APIs that’s easy to forget exists.