What is the best way to mutate a collection whilst iterating over it with nested loops?

Hi all,

I recently wrote the following function to sort a collection of numbers.
I found that I couldn't use .iter() to iterate through the list whilst mutating it.

Is there a better way to deal with iterating over mutable Vecs in your view? Any thoughts or advice on how a Rustacean would typically handle these scenarios would be deeply appreciated.

I'll leave a Rust Playground link here: Rust Playground

Here's the code snippet as well if that's easier to go through, thanks!


fn main() {
    let numbers: Vec<u32> = vec![7, 2, 5, 4, 1, 6, 0, 3];
    let numbers_list: Vec<u32> = selection_sort(&numbers);

    println!("Start list: {:?}", numbers);
    println!("Sorted list: {:?}", numbers_list);
}

fn selection_sort(numbers: &Vec<u32>) -> Vec<u32> {
    // Clones the list so that the original one is not modified.
    let mut numbers_list = numbers.clone();

    for index in 0..numbers_list.len() {
        let number: u32 = numbers_list[index];
        let mut lowest: u32 = number;
        let mut swap_position: usize = index;

        for position in 0..numbers_list.len() {
            let comparable: u32 = numbers_list[position];

            if position <= index {
                continue;
            }

            if lowest > comparable {
                lowest = comparable;
                swap_position = position;
            }
        }

        numbers_list.swap(index, swap_position);
    }

    return numbers_list;
}

#[cfg(test)]
mod tests {
    use crate::selection_sort;

    #[test]
    fn selection_sort_orders_handles_empty_vec() {
        let original: Vec<u32> = vec![];
        let result = vec![];

        let sorted = selection_sort(&original);
        assert_eq!(sorted, result);
    }

    #[test]
    fn selection_sort_orders_handles_single_number() {
        let original = vec![7];
        let result = vec![7];

        let sorted = selection_sort(&original);
        assert_eq!(sorted, result);
    }

    #[test]
    fn selection_sort_orders_handles_two_numbers() {
        let original = vec![7, 2];
        let result = vec![2, 7];

        let sorted = selection_sort(&original);
        assert_eq!(sorted, result);
    }

    #[test]
    fn selection_sort_orders_numbers() {
        let original = vec![7, 2, 5, 4, 1, 6, 0, 3];
        let result = vec![0, 1, 2, 3, 4, 5, 6, 7];

        let sorted = selection_sort(&original);
        assert_eq!(sorted, result);
    }

    #[test]
    fn selection_sort_orders_base_ten() {
        let original = vec![70, 20, 50, 100, 40, 90, 10, 60, 30, 80];
        let result = vec![10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

        let sorted = selection_sort(&original);
        assert_eq!(sorted, result);
    }

    #[test]
    fn selection_sort_orders_base_hundred() {
        let original = vec![700, 200, 500, 1000, 400, 900, 100, 600, 300, 800];
        let result = vec![100, 200, 300, 400, 500, 600, 700, 800, 900, 1000];

        let sorted = selection_sort(&original);
        assert_eq!(sorted, result);
    }

    #[test]
    fn selection_sort_orders_base_thousand() {
        let original = vec![7000, 2000, 5000, 10000, 4000, 9000, 1000, 6000, 3000, 8000];
        let result = vec![1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10_000];

        let sorted = selection_sort(&original);
        assert_eq!(sorted, result);
    }
}

In general, using indices is the simplest approach. If you're clever, though, you can use split_first_mut to do it.

let mut vec = vec![1, 2, 3];
let mut opt = vec.split_first_mut();
while let Some((first, rest)) = opt {
    println!("{first}");
    opt = rest.split_first_mut();
}
1 Like

Using indices in cases like this is the recommended way and there's nothing wrong with it.

On a side note, your algorithm can be simplified a little, see eg https://docs.rs/rust-sort/latest/src/rust_sort/selection_sort.rs.html#19-36 and https://codereview.stackexchange.com/questions/122790/selection-sort-algorithm-in-rust

1 Like

The first thing I noticed was

-        for position in 0..numbers_list.len() {
+        for position in index+1..numbers_list.len() {
             let comparable: u32 = numbers_list[position];
-            if position <= index {
-                continue;
-            }

And this illustrates[1] that in each iteration through the outer loop, we only need to look at

  • The element at index
  • The element right of index

And these are non-overlapping regions of your Vec, so it's possible to get mutable references to them at the same time. Here's what I came up with for the inner loop operation:

fn select_least<T: Ord>(slice: &mut [T]) {
    // If there's at least two elements
    if let [first, second, rest @ ..] = slice {
        // Find the least element to the right of the first element
        let target = rest.into_iter().fold(
            second,
            |least, this| least.min(this)
        );
        // And swap it with the first, if it's less than the first
        if target < first {
            std::mem::swap(first, target);
        }
    }
}

And then your outer loop just becomes

    for index in 0..numbers.len() {
        select_least(&mut numbers_list[index..]);
    }

Incidentally, your function signature should arguably look like

fn selection_sort_inplace<T: Ord>(slice: &mut [T]) {
    for index in 0..slice.len() {
        select_least(&mut slice[index..]);
    }
}

Or perhaps

fn selection_sort_mapper<T: Ord>(mut items: Vec<T>) -> Vec<T> {
    selection_sort_inplace(&mut items);
    items
}

Taking &Vec<T> in particular isn't that useful since almost everything you can do with that type, you can do with &[T]. The latter is less indirect and more general.


Sometimes there's just no good alternative to working with indices though. However, you still may be able to use iteration and mutation in the case where your elements are Copy. Here's an article about it.



  1. as does reading the comments about the algorithm :sweat_smile: ↩︎

3 Likes

Thank you, this is really helpful!

This is what I was looking for, there's a few new aspects for me to learn from your snippets too.

Taking &Vec<T> in particular isn't that useful since almost everything you can do with that type, you can do with &[T]. The latter is less indirect and more general.

This is something I was wondering how to do as well. If I did &[T] does that mean that I can even pass characters into it? I guess to sort them I would need to add additional logic to support each type right?

Appreciate the advice and the resources. :pray:

Well, I think there are two questions here.

Why use &[_] instead of &Vec<_>?

The answers to this question are the same no matter what type is inside the Vec/slice:

  • About all you can do with &Vec<_> that you can't do with &[_] is ask for the capacity -- and since you can't extend the Vec<_> with a &Vec<_>, you will pretty much never care what the capacity is. So you don't gain anything you need by requiring &Vec<_>. All the useful shared-reference methods are on [_].

  • You go through an extra layer of indirection.

  • Callers of the function may not have a Vec<_> to share, they might only have a &[_] themselves, or an array, or some reference to a data structure that can opaquely hand out shared slices, etc. These callers would have to allocate a Vec<_> and pass in a reference to that.

  • Even if you're the only caller and you don't care about all of that, it's idiomatic to take &[_] :slightly_smiling_face:

How to sort generically on T instead of on i32 specifically?

Here's about what my first go at select_least (and the error it generated) looked like:

fn select_least(slice: &mut [i32]) { /* ... */ }
error[E0308]: mismatched types
  --> src/lib.rs:38:22
   |
38 |         select_least(&mut vec[index..]);
   |         ------------ ^^^^^^^^^^^^^^^^^ expected `&mut [i32]`, found `&mut [u32]`
   |         |
   |         arguments to this function are incorrect
   |
   = note: expected mutable reference `&mut [i32]`
              found mutable reference `&mut [u32]`

Oops. Now, I could have just corrected my type, but I figured it was a good time to try being generic anyway by using some generic T instead of u32 (or i32). I knew if I only changed it to T with no bounds, the compiler would complain, because Rust will only let you use generic parameters in ways that you have declared to be required by way of trait bounds. But I figured the errors would tell me what trait bounds I needed, so that's what I did anyway:

fn select_least<T>(slice: &mut [T]) {
error[E0599]: the method `min` exists for mutable reference `&mut T`, but its trait bounds were not satisfied
  --> src/lib.rs:49:33
   |
49 |             |least, this| least.min(this)
   |                                 ^^^ method cannot be called on `&mut T` due to unsatisfied trait bounds
   |
   = note: the following trait bounds were not satisfied:
           `T: Ord`
           which is required by `&mut T: Ord`
           `T: Iterator`
           which is required by `&mut T: Iterator`
           `&mut T: Ord`
           which is required by `&&mut T: Ord`
           `&mut T: Ord`
           which is required by `&mut &mut T: Ord`
           `&mut T: Iterator`
           which is required by `&mut &mut T: Iterator`
           `T: Ord`
           which is required by `&T: Ord`
error[E0369]: binary operation `<` cannot be applied to type `&mut T`
  --> src/lib.rs:52:19
   |
52 |         if target < first {
   |            ------ ^ ----- &mut T
   |            |
   |            &mut T
   |
help: consider restricting type parameter `T`
   |
43 | fn select_least<T: std::cmp::PartialOrd>(slice: &mut [T]) {
   |                  ++++++++++++++++++++++

It's suggesting T: Ord and T: PartialOrd ... and a bunch of other things about Iterator. I'm wasn't really sure why those other suggestions were there honestly and just ignored them since I wasn't trying to iterate the T. Now writing this up, it occurs to me that it must be because there's a min method in the Iterator trait. That's not the method I wanted, so those parts can indeed just be ignored.

Also just from experience, I also knew that Ord implies PartialOrd.

So after seeing the (expected) error, I just added one bound:

fn select_least<T: Ord>(slice: &mut [T]) {
//               ^^^^^

And that's all it took. Now that function works on slices of any type that implements Ord -- because that's the point of Rust requiring you to state the operations you need in the form of trait bounds.

So your code does not need any extra logic-per-type! You can pass in &[char] or any of those other Ord-implementing types. All the logic you need to sort is provided by the caller's implementation of Ord.[1]

That's the beauty of generics with enforced bounds.


That being said, the bounds you need for a given function aren't always this straightforward, and sometimes there's value in being concrete instead of as-generic-as-possible. It just happened to fall out naturally for me when working on your playground example.


  1. And it's the same bounds the built-in sorting methods require too. ↩︎

5 Likes