Compare all elements in list and get mutable references for matching pairs

Question

My goal is to compare each element in a list to every other element in the list according to some criteria. In pseudo-code, something like:

for i, x in list.enumerate():
    for y in list[i..]:
        if x.match(y):
            // Modify both x and y

I would like to get a mutable reference to both items in each matching pair. This proved to be difficult. According to this answer, the best way to get mutable references to multiple items in a list is through split_at_mut. I wrote a wrapper function for extracting two mutable references to a list:

/// Gets two mutable references to elements i and j in list
fn get_pair<'a, T>(i: usize, j: usize, list: &'a mut [T]) -> (&'a mut T, &'a mut T) {
    let (a, b) = list.split_at_mut(j);

    let first = &mut a[i];
    let second = &mut b[0];

    (first, second)
}

However, I still cannot use this function inside a nested for loop without breaking borrowing rules:

for stuff1 in list.iter() {
    // immutable borrow on list here
    for stuff2 in list[i..].iter() {
        if stuff1.compare(stuff2) {
            let (stuff1, stuff2) = get_pair(i, j, list); // mutable borrow on list
            do_something(stuff1, stuff2);
        }
    }
}

Instead I save a pair of matching indices and then in a different loop actually get the elements and do something with them.

// Find matching pairs and push their indices
let mut matches: Vec<(usize, usize)> = Vec::new();
for (i, stuff1) in list.iter().enumerate() {
    for (j, stuff2) in list[i..].iter().enumerate() {
        if stuff1.compare(stuff2) {
            matches.push((i, j));
        }
    }
}

// Get two mutable references by indices from list
for m in matches.iter() {
    let (i, j) = m;
    let (stuff1, stuff2) = get_pair(*i, *j, list);
    do_something(stuff1, stuff2);
}

This works, but seems a little overly complicated. Is there an easier or more simple way to achieve this without breaking the borrow rules?

Ideally I would like to modify matching pairs in the original loop without needing a separate loop to go over the indices.

A full example of my current code can be found on the playground.

Have you read [How can I create my own data structure with an iterator that returns mutable references?](https://stackoverflow.com/q/25730586/155423)? It explains why the iterator you want is impossible in safe Rust. — Shepmaster, Dec 12 '18 at 21:43
I understand why I cannot use mutable iterators, but am wondering how to correctly approach the above problem in Rust. The linked answer mentions [MutItems](http://huonw.github.io/strided-rs/strided/struct.MutItems.html), which looks like it may be useful. I'll have to take a look. — Increasingly Idiotic, Dec 12 '18 at 22:07
Although, I am getting the sense that a solution any better than the one I already have will likely involve unsafe code. — Increasingly Idiotic, Dec 12 '18 at 22:09
I think that's an anachronism (I should clean up that answer), but I think it's referring to what is now called [`IterMut`](https://doc.rust-lang.org/std/slice/struct.IterMut.html) — Shepmaster, Dec 12 '18 at 22:09
Any such iterator would actually *be* unsafe as it would allow you to get two mutable references to the same item. Such an iterator may not be constructed. — Shepmaster, Dec 12 '18 at 22:10
Why not iterate through the indices (`for i in 0..list.len()`), and call `get_pair()` from inside the loop? After all, you are not changing the list itself when you find a match, but only the elements. — rodrigo, Dec 12 '18 at 22:58

score 3 · Accepted Answer · edited Dec 13 '18 at 02:37

You can do it like this, and it generates pretty decent code:

let mut list = [1, 2, 3];
for i in 0..list.len() {
    let (a, b) = list.split_at_mut(i);
    let item_b = &mut b[0];
    for item_a in a {
        println!("{} {}", item_a, item_b);
    }
}

The key here is that 0..len iteration avoids locking the list to be read-only. split_at_mut proves to the borrow checker that both references can't point to the same element.

Compare all elements in list and get mutable references for matching pairs

1 Answers1