Swap_remove in Rust

Introduction

The other day, looking at the std::Vec documentation in Rust, I found this interesting function called swap_remove.

First, we have to talk about the obvious difference between the standard remove, that everybody has used before, and this swap_remove that is a more tricky implementation for some use cases:

Remove

Remove, as defined in its documentation, follows the next function signature: pub fn remove(&mut self, index: usize) -> T. It recieves the mutable vector itself, and the desired index of the element to be removed, and return it.

What it is important to mention is how Rust (and almost every other language) handle vectors. Vectors in computer science are defined as a collection of elements followed in memory, that means, the distance between two elements of a vector is the size of the element.

Once we delete an element that is in the middle of the structure (if you want to delete the first or last element Rust recommends to use VecDeque instead), Rust has to shift the elements to avoid empty spots in the collection. This work has a O(n) complexity in the worst case. Wich means that if we have one million elements and we want to remove the second one, the vector will have to shift 999.998 elements!!!

Swap_remove

The function swap_remove is useful to handle this problem. This operation will swap the last element with the one to be erased, and finally perform a back pop to remove it. E.g: If we remove the value 2, the vector will look like the following:

When to use it or not

With the last explanation seems like we have to use always swap_remove instead of remove right? Thats wrong!!!

Vectors are a powerful structure when we have the values sorted. This invalidates the whole point of using swap_remove, since we will have to sort the values again.

let mut v: Vec<i32> = vec![1, 2, 3, 4];
assert!(v.is_sorted());
v.swap_remove(1); // v = [1, 4, 3]
assert!(!v.is_sorted());

We have to be careful with working with raw pointers in Rust since they are unsafe, but I will explain some errors that we can find.

let mut v: Vec<i32> = vec![1 ,2, 3, 4];
let points_to_four = &v[3] as *const i32;
let points_to_two = &v[1] as *const i32;
assert_eq!(unsafe{*points_to_four}, 4);
assert_eq!(unsafe{*points_to_two}, 2);
v.swap_remove(1);
assert_eq!(unsafe{*points_to_four}, 4); // Could be false at some point that we can not control
assert_ne!(unsafe{*points_to_two}, 2); // Now points to the value 4 at v[1]

This test was very interesting. It seems like Rust clones the elements to swap instead of moving it, this is understandable since an i32 implements the Copy and Clone traits.

Those are unsafe operations but we have to be very careful of what are we doing because if our Vec<T> where T !Copy, the assert could be or not true. By the way, even if now it is true because the value is copied, this could change in the future once the OS claim this free memory address. This happens aswell with vec::remove.

let mut v: Vec<i32> = vec![1, 2, 3, 4];
let last_ptr = &v[3] as *const i32;
assert_eq!(unsafe{last_ptr.read()}, 4);
v.swap_remove(1);
assert_eq!(unsafe{last_ptr.read()}, 4); // Still true
v.insert(1, 10);
assert_eq!(unsafe{last_ptr.read()}, 4); // FAIL: Left: 3, Right: 4. The vector has growth, shifting the value 3 to the right.

Conclusion

We should use vec::remove when we care about the order and vec::swap_remove otherwise. Working with raw pointers and remove elements of a vector is highly unsafe, but at worst… We have the same as C++ right?