Borrows, moves, iter slices

My question is in the comment towards the bottom of the function. When I added the "if" at the bottom I then needed to update the way I was iterating sorted_nums by adding .iter().cloned(). I have it working, but I don't understand why I had to do this. Could someone please explain it to me? Any other criticisms (advice) are welcome. I'm a seasoned Python developer taking my first steps into Rust.

    pub fn missing_number(nums: Vec<i32>) -> i32 {
        // https://leetcode.com/problems/missing-number/
        let mut prev_num: Option<i32> = None;
        let mut sorted_nums = nums.clone();
        sorted_nums.sort();
        for num in sorted_nums.iter().cloned() {
            if prev_num.is_some() {
                let expected = prev_num.unwrap() + 1;
                if num != expected {
                    return expected;
                }
            } else if prev_num.is_none() && num != 0 {
                return 0;
            }
            prev_num = Some(num);
        }
        // After adding this "if" I had to add `.iter().cloned()`
        // to the loop and I don't really know why.
        if sorted_nums[sorted_nums.len() - 1] != sorted_nums.len() as i32 {
            return sorted_nums[sorted_nums.len() - 1] + 1;
        }
        panic!("hhhh");
    }

Without .iter().cloned() I get these errors

let mut sorted_nums = nums.clone();
// Diagnostics:
// 1. move occurs because `sorted_nums` has type `Vec<i32>`, which does not implement the `Copy` trait [E0382]
for num in sorted_nums { 
// Diagnostics:
// 1. `sorted_nums` moved due to this implicit call to `.into_iter()` [E0382]
// 2. consider iterating over a slice of the `Vec<i32>`'s content to avoid moving into the `for` loop: `&` [E0382]

Instead of doing the slice, I seemed to have done a clone?

if sorted_nums[sorted_nums.len() - 1] != sorted_nums.len() as i32 {
// Diagnostics:
// 1. borrow of moved value: `sorted_nums`
//   value borrowed here after move [E0382]

I essentially don't understand any of these errors. Help understanding would be appreciated. Thanks!

This is due to the move behavior of for statements.

Any for consumes the iterator it goes over, so iterating over sorted_nums renders it inaccessible to code after the for-loop.

In most circumstances, I would instead iterate over the array via a borrow:

for &num in &sorted_nums { 
    // iterates over a REFERENCE (non-owning) to sorted_nums
    // then copies out the number from behind the reference
}

Side note: You can save yourself a cloning operation by mutating num:

pub fn missing_number(mut nums: Vec<i32>) -> i32 {
    nums.sort();
    // ...
}
5 Likes

A for loop consumes the thing being iterated by calling IntoIterator::into_iter (note the self receiver). Without the if that follows, you don't need sorted_num to exist after the for loop. With it, you do need it to still exist, so you can't consume it.

By replacting it by .iter().cloned(), you are not consuming the Vec, but instead borrowing it and getting &i32 as an item because of iter(), and then turning that into an iterator over i32 with .cloned().


Tip one: Use .copied() instead to signal that this is a cheap operation, since i32: Copy.

Alternatively, don't use .copied() or .cloned() at all and just adjust either the body of the loop or the for _ pattern to work with &i32 (example in my last playground). In this case, for num in sorted_nums.iter() will be the same as for num in &sorted_nums as suggested above.


Tip two: the clone in let mut sorted_nums = nums.clone(); is completely unnecessary.[1] All you need to do is change the mutability of the binding:

let mut sorted_nums = nums;

And in fact even better would be to just make the binding mut to begin with:

-pub fn missing_number(nums: Vec<i32>) -> i32 {
+pub fn missing_number(mut nums: Vec<i32>) -> i32 {
+    // And use `nums` instead of `sorted_nums` throughout the body...

In case you weren't aware: While &T is a distinct and very semantically different type than &mut T, the mutability of bindings is basically just a lint. So here:

pub fn missing_number(nums: Vec<i32>) -> i32 {
    let mut sorted_nums /* : Vec<i32> */ = nums;
    // ...
}

nums and sorted_nums have the same type -- Vec<i32> -- but the nums binding is not mutable, while the sorted_nums is mutable -- so you can overwrite it or take a &mut to it.

The suggested change of making the parameter mut in the function signature:

pub fn missing_number(mut nums: Vec<i32>) -> i32 {
//                    ^^^

does not change the API of the function at all; it is notionally the same as

pub fn missing_number(nums: Vec<i32>) -> i32 {
    let mut nums = nums;

Here's a playground with some adjustments as per the comments above.


Here's another where instead of .iter().copied(), I adjust the binding in the for loop:

    for &num in &nums {

You may not yet understand why this works, in which case I recommend reading this article about patterns. Or don't worry about it for now and file this away to come back to another day.

Which of the two approaches you prefer is a matter of style.


  1. Unless maybe you have a logic error -- I didn't bother looking at leetcode ↩ī¸Ž

4 Likes

Any for consumes the iterator it goes over

Oh interesting! That translates to Python and the world I know. I am familiar with iterators being consumed.

I suppose I'm surprised because I didn't think the iterator made from a vector would have an impact on the vector.

Thanks to your response I've been able to "google" this better and am finding a bunch of content. e.x. For loops and ownership - #2 by stebalien is basically my question.

The clone() is perhaps something that isn't needed in Rust. In Python I'm careful not to mutate inputs but Rust might have that solved given ownership/moves etc. concepts I clearly am developing.

Thank you for the response, this helps a bunch!

edit: I also went on to read reference - What is the purpose of `&` before the loop variable? - Stack Overflow which was useful!

Thank you so much for this detailed response! I do understand it more now. But as you alluded to, I'm definitely going to be digesting this a bit over the next little while as it solidifies and as I start to write more Rust code. Thank you!

1 Like

I just want to add that Rust has "value semantics" instead of "reference semantics" by default, so anything you pass into a function is passed "by value", in fact by moving, and has no tie to the outside unless you tell it to. A lot like "primitive types" in many by-reference languages. Except the caller will not be left with a copy of the value either, unless the value's type implements the opt-in Copy trait (numbers, bool, etc. implement Copy, Vec<T> does not). The caller need to .clone() the vector in your case to keep (a copy of) it.

It would have been different with &mut Vec<i32>, for example, where it's possible to "steal" all the values and leave the caller with an empty vector. But you can see that it's explicitly signaled with &mut that you intend to modify the vector. So unless you see &mut T, &T, Rc<T>, Arc<T>, or something else that's meant to have shared data, you are the sole owner and holder of that instance. It's still possible to write code with unclear intentions by not documenting or clarifying internal sharing, but that's very unusual IME and no reason to be generally defensive.

3 Likes

No. You are confusing the iterator and the iterated collection being consumed.

If you iterate over a vector by reference (.iter(), for example), then the iterator itself is still consumed. (It always is, by definition of the for loop.) But this of course only borrows the vector, it doesn't consume it.

The IntoIterator impl for Vec does iterate by-value, which means that creating the iterator needs to consume the vector in the first place. This has nothing to do with the for loop consuming the iterator, though. The vector will already have been consumed by the time you get an iterator.

5 Likes

Things I've realized:

  1. .clone() is not actually needed
  2. "avoid moving into the for loop

I didn't think about about the "moving into" words here. It seems I need to think about the for loop a bit like a function and how variables can move into a function. To avoid the move (into a function) one would use & which is what iter() does. The fact that there is an implicit into_iter() with a for-loop should also not go unnoticed. Using it is not like using &.

1 Like

To be clear, that applies to your specific example. In general, it's best to move the container into a for-loop, unless you need to reuse it later. It's more efficient, leads to simpler code (no extra cloning or dereferencing of values) and prevents accidental reuse of the container.

3 Likes

Makes sense! Thanks!