Container fails borrow checker because the reference to its elements

use std::collections::HashSet;
use std::iter::FromIterator;

fn main() {
    let numbers = [1i32, 2i32, 3i32];
    let mut set: HashSet<i32> = HashSet::from_iter(numbers.iter().map(|v| *v));

    let mut to_remove = Vec::new();
    let set_iter = set.iter();
    for (i, w) in set_iter.enumerate() {
        if i % 2 == 0 {
            // Changing it to `*w` compiles.
            to_remove.push(w);
        }
    }

    for w in to_remove {
        set.remove(&w);
    }

    println!("set_ref: {:?}", set);
}

The above code fails to compile with the error:

error[E0502]: cannot borrow `set` as mutable because it is also borrowed as immutable
  --> src/main.rs:18:9
   |
9  |     let set_iter = set.iter();
   |                    --- immutable borrow occurs here
...
17 |     for w in to_remove {
   |              --------- immutable borrow later used here
18 |         set.remove(&w);
   |         ^^^^^^^^^^^^^^ mutable borrow occurs here

Is this because w is a reference (&i32) to elements in set and its lifetime depends on the reference to set stored in set_iter, which in turn makes set_iter not go out of scope after the first for loop? It's a little confusing for me to see where the immutable borrow is used.

Yes.

No, set_iter does go... well... it doesn’t really go “out of scope” (in my intuition of the term “scope”), but it isn’t used anymore aftere the first for-loop, so it isn’t directly part of the problem the borrow-checker is indicating here.

set_iter yields elements that are references into set, so after you used it, your to_remove set does contain references into set, but the iterator set_iter itself is out of the equation. The problem is that to_remove now is, to the borrow checker, something like a reference to set. (In reality it is a collection of such references.) So in order to execute the second loop, you’re keeping to_remove alive (since you’re iterating over it) but you are also mutating set at the same time, hence the error message.

Another way to look at it is that due to Rust’s borrowing rules, you can never call HashMap::remove with a reference that’s pointing into the same map. Instead it expects a reference to an external copy of the element you’re removing.

// exclusive/mutable borrow `&mut self` cannot “overlap” with
// the immutable/shared borrow `&Q`
pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
where
    T: Borrow<Q>,
    Q: Hash + Eq, 

Finally, just intuitively speaking, code like yours is problematic since it is (or at least might be) possible that by removing an element from a HashSet other elements are moved around in memory. Thus once you removed the first element, the other references pointing into the—now modified—map might be pointing to invalid objects/memory now. Especially if we were to consider a HashMap::insert operation, then the map might have resized and every previous reference into the map is pointing into deallocated memory (of the old, too small allocation of the map).


Also note that code that removes some elements from a collection while iterating over all of them can often be expressed quite efficiently using the retain operation, e.g. HashMap::retain. I’m not giving a code example here since your code is “nonsensical” in the sense that the iteration order of a HashMap is not specified, so removing “every second element” of a HashMap is a bad idea, but for a Vec, one could do something like:

use std::iter::FromIterator;

fn main() {
    let numbers = [1,2,3,5,7];
    let mut set: Vec<i32> = Vec::from_iter(numbers.iter().map(|v| *v));

    let mut i = 0;
    set.retain(|w| {
        let w_is_retained = i % 2 != 0;
        if !w_is_retained {
            println!("removing {}", w);
        }
        i += 1;
        w_is_retained
    });

    println!("set: {:?}", set);
}
removing 1
removing 3
removing 7
set: [2, 5]

By the way, as noted in it’s documentation, you’d commonly not call FromIterator::from_iter directly, but use Iterator::collect instead, e.g.

let mut set: HashSet<i32> = numbers.iter().map(|v| *v).collect();

or

let mut set: Vec<i32> = numbers.iter().map(|v| *v).collect();

and the map of a dereference can be archieved using the copied() method:

let mut set: HashSet<i32> = numbers.iter().copied().collect();
let mut set: Vec<i32> = numbers.iter().copied().collect();

and for even/odd comparison the index is not really needed, so one could do something like

fn main() {
    let numbers = [1,2,3,5,7];
    let mut set: Vec<i32> = numbers.iter().copied().collect();

    let mut even = false; // index -1 is not even
    set.retain(|w| {
        even = !even; // going from -1 to 0 in the first iteration
        // ^^^^^ alternative using xor: even ^= true;
        
        if even {
            println!("removing {}", w);
        }
        // retain if:
        !even
    });

    println!("set: {:?}", set);
}
4 Likes

Thank you for the detailed answer! Yeah, I was aware of many other points you mentioned. Just wanted to show a quick example to make sure I didn't miss other borrow checker rules.

I didn't know copied(). Thanks.