insert() and remove()

The .insert(index, element) and .remove(index) methods add or remove an element at an arbitrary index in a Vec<T> while preserving the relative order of all other elements, whereas .swap_remove(index) removes an element in $O(1)$ time when element order does not matter.

Signatures and Shifting Behavior

impl<T> Vec<T> {
    pub fn insert(&mut self, index: usize, element: T);
    pub fn remove(&mut self, index: usize) -> T;
    pub fn swap_remove(&mut self, index: usize) -> T;
}

1. v.insert(1, 99) on [10, 20, 30]:
   Shifts [20, 30] right by 1 slot (O(n - index)), writes 99 at [1]
   ──> [10, 99, 20, 30]

2. v.remove(1) on [10, 20, 30, 40]:
   Reads 20 from [1], shifts [30, 40] left by 1 slot (O(n - index))
   ──> returns 20, leaves [10, 30, 40]

3. v.swap_remove(1) on [10, 20, 30, 40]:
   Reads 20 from [1], moves last element (40) into [1] (O(1)!)
   ──> returns 20, leaves [10, 40, 30]

Comparison of Removal and Insertion Methods

fn main() {
    let mut ordered = vec!["a", "b", "c", "d"];

    // Insert "X" at index 2 (valid indices are `0..=ordered.len()`):
    ordered.insert(2, "X");
    println!("After insert(2, 'X'):  {ordered:?}");

    // Order-preserving remove at index 1 ($O(n)$ shift):
    let r1 = ordered.remove(1);
    println!("remove(1) -> '{r1}':     {ordered:?}");

    // O(1) swap_remove at index 0 (moves last element "d" into index 0):
    let r2 = ordered.swap_remove(0);
    println!("swap_remove(0) -> '{r2}': {ordered:?}");
}

After insert(2, 'X'):  ["a", "b", "X", "c", "d"]
remove(1) -> 'b':     ["a", "X", "c", "d"]
swap_remove(0) -> 'a': ["d", "X", "c"]

Maintaining a Small Sorted Vector with binary_search + insert

For small sorted sets or maps stored inside a Vec<T>, combining .binary_search(&item) with .insert(pos, item) inserts new elements at their exact sorted position:

fn insert_sorted(vec: &mut Vec<i32>, value: i32) {
    if let Err(pos) = vec.binary_search(&value) {
        vec.insert(pos, value);
    }
}

fn main() {
    let mut nums = vec![10, 30, 50];
    insert_sorted(&mut nums, 20);
    insert_sorted(&mut nums, 40);
    insert_sorted(&mut nums, 30); // Duplicate ignored

    println!("Sorted vec: {nums:?}");
}

Sorted vec: [10, 20, 30, 40, 50]