How to swap the elements of an array, slice, or Vec?

Question

I want to swap elements of slice data using library function, but it doesn't work because of multiple borrowing:

use std::mem;

fn example() {
    let mut data = [1, 2, 3];
    let i = 0;
    let j = 1;
    
    mem::swap(&mut data[i], &mut data[j]);
}

error[E0499]: cannot borrow `data[_]` as mutable more than once at a time
 --> src/lib.rs:8:29
  |
8 |     mem::swap(&mut data[i], &mut data[j]);
  |     --------- ------------  ^^^^^^^^^^^^ second mutable borrow occurs here
  |     |         |
  |     |         first mutable borrow occurs here
  |     first borrow later used by call
  |

It could be done manually, but I don't think using this code every time is great:

let temp = data[i];
data[i] = data[j];
data[j] = temp;

Is there any other solution to swap elements in slices?

Paralysis

"It could be done manually, as usual" ... on Copy types - otherwise it will result in a "cannot move out of indexed content". – Immersionism

Answer 1

There's a swap method on slices: data.swap(i, j).

The original code doesn't work because the language requires that &muts do not alias, that is, if a piece of data is accessible via an &mut, then there must be no other way to use that data. In general, for successive indexes data[i], data[j], the compiler cannot guarantee that i and j are different. If they are the same then the indexing is referring to the same memory and so &mut data[i] and &mut data[j] would be two pointers to the same data: illegal!

.swap uses a bit of unsafe code internally, being sure to handle the i == j case correctly, avoiding aliasing &mut pointers. That said, it doesn't have to use unsafe, it is only to ensure this "primitive" operation has high-performance (and I could definitely imagine future language/library improvements that reduce the need for unsafe here by making the require invariants easier to express), e.g. the following is a safe implementation:

use std::cmp::Ordering;
use std::mem;

fn swap<T>(x: &mut [T], i: usize, j: usize) {
    let (lo, hi) = match i.cmp(&j) {
        // no swapping necessary
        Ordering::Equal => return,

        // get the smallest and largest of the two indices
        Ordering::Less => (i, j),
        Ordering::Greater => (j, i),
    };

    let (init, tail) = x.split_at_mut(hi);
    mem::swap(&mut init[lo], &mut tail[0]);
}

The key here is split_at_mut which separates the slice into two disjoint halves (this is done using unsafe internally, but Rust's standard library is built on unsafe: the language provides "primitive" features and the libraries build the rest on top of them).

Chumley

There is no magic inside - just unsafe block - what a pitty!) – Paralysis

There is, in ptr mod: github.com/rust-lang/rust/blob/master/src/libcore/ptr.rs#L164 – Erstwhile

@FominArseniy, it can be implemented with some "magic" to avoid unsafe (I've edited my answer to include an example implementation). – Chumley

It can also be implemented with using temp variable either, I don't see why there is need in such complex implementation. Problem with double borrowing arises from function call syntax swap(mut & x, mut & y), when x, y point to the same data slice. If function syntax is swap(& mut[], i, j), there is no problem to swap inside of it using temp variable. – Paralysis

@swizard, this is really dramatical implementation of swap, but it's pointer version. – Paralysis

@FominArseniy, it only works with a temp variable if the type is Copy. If the contained types moves (e.g. data: &mut [String]), it is not possible to use the code you give in your question, while the careful one I give does work. – Chumley

I think the index &mut tail[hi] is wrong, shouldn't it be &mut tail[0] ? – Highness

@FominArseniy, yes, it is pointer version which is the slice proc implemented via: github.com/rust-lang/rust/blob/master/src/libcore/slice.rs#L352 – Erstwhile

Answer 2

It is possible to use tuple destructing to swap two or more elements in an array.

// Initial data
let mut data = [1, 2, 3, 4, 5, 6];

// Swap three elements around
(data[1], data[3], data[5]) = (data[3], data[5], data[1]);

// End result
assert_eq!(data, [1, 4, 3, 6, 5, 2]);

Noto

This only works if the elements are Copy, and should be less performant than swap(). – Holter