Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 633
Arsenii Fomin Avatar asked Feb 03 '15 08:02

Arsenii Fomin


People also ask

How do you interchange an array in Java?

swap() to Swap Two Elements of an Array in Java. The swap() method of the Collections class swaps elements at the specified position in the specified list. We convert our firstArr into a list using Arrays. asList() and then pass it to the swap() method with positions 0 and 2 .


1 Answers

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).

like image 57
huon Avatar answered Oct 05 '22 06:10

huon