How can I partition a mutably borrowed vector?


Keywords:rust 


Question: 

If I have a local, mutable vector, I can partition it as follows, copied from the documentation of partition.

let mut a = vec![1, 2, 3, 4];
let (even, odd): (Vec<i32>, Vec<i32>) = a.into_iter().partition(|&n| n % 2 == 0);

The a vector is consumed (moved) in this process. However, the same call to partition doesn't work if I have a borrowed mutable reference. If I try to use the same code in that case, I get the error:

error[E0277]: the trait bound `std::vec::Vec<i32>: std::iter::Extend<&mut i32>` is not satisfied
 --> src/main.rs:2:59
  |
2 |     let (even, odd): (Vec<i32>, Vec<i32>) = a.into_iter().partition(|n| **n % 2 == 0);
  |                                                           ^^^^^^^^^ the trait `std::iter::Extend<&mut i32>` is not implemented for `std::vec::Vec<i32>`
  |
  = help: the following implementations were found:
            <std::vec::Vec<T> as std::iter::Extend<&'a T>>
            <std::vec::Vec<T> as std::iter::Extend<T>>

Based on How to make a Rust mutable reference immutable?, I wrote the following, which compiles and puts the right values into even and odd.

fn doit(a: &mut Vec<i32>) {
    let (even, odd): (Vec<i32>, Vec<i32>) = (&*a).into_iter().partition(|&n| n % 2 == 0);
    println!("even {:?}, odd {:?}, a {:?}", even, odd, a);
}

However, this does not consume the original vector, even though I'm using into_iter(). There's something about mutability, borrowing, or iterators that I'm just not getting here.


2 Answers: 

As others have implied, you can't move the original vector since you don't own it. However you can move all the values out of the vector, leaving it empty. This can be accomplished with the drain method:

fn doit(a: &mut Vec<i32>) {
    let (even, odd): (Vec<i32>, Vec<i32>) = a.drain(..).partition(|&n| n % 2 == 0);
    println!("even {:?}, odd {:?}, a {:?}", even, odd, a);
}

playground



The reason is that the IntoIterator trait is implemented differently for &'a mut Vec<T> and &'a Vec<T> then it is for Vec<T>. The First two create an iterator by value where as the Vec<T> version creates a consuming iterator, that is, one that moves each value out of the vector (from start to end). The vector cannot be used after calling into_iter(). So you can think of the first two &'a mut Vec<T> and &'a Vec<T> as using the values inside the reference to the Vector to create an iterator. Where as the Vec<T> you can think of it removing the values out of the Vec<T> and putting them into the iterator. Shepmaster's comment of not being able to consume something that you don't own is the reason why they are implemented differently.

Also be aware that there is different ways to get an iterator. From the Rust documentation:

  • iter(), which iterates over &T.
  • iter_mut(), which iterates over &mut T.
  • into_iter(), which iterates over T.

So you could also keep the function the same without doing (&*a) by using iter() instead of into_iter().

fn doit(a: &mut Vec<i32>) {
    let (even, odd): (Vec<i32>, Vec<i32>) = a.iter().partition(|&n| n % 2 == 0);
    println!("even {:?}, odd {:?}, a {:?}", even, odd, a);
}