Getting first member of a BTreeSet

Question

In Rust, I have a BTreeSet that I'm using to keep my values in order. I have a loop that should retrieve and remove the first (lowest) member of the set. I'm using a cloned iterator to retrieve the first member. Here's the code:

use std::collections::BTreeSet;

fn main() {
    let mut start_nodes = BTreeSet::new();

    // add items to the set

    while !start_nodes.is_empty() {
        let mut start_iter = start_nodes.iter();
        let mut start_iter_cloned = start_iter.cloned();
        let n = start_iter_cloned.next().unwrap();

        start_nodes.remove(&n);

    }
}

This, however, gives me the following compile error:

error[E0502]: cannot borrow `start_nodes` as mutable because it is also borrowed as immutable
  --> prog.rs:60:6
   |
56 |        let mut start_iter = start_nodes.iter();
   |                             ----------- immutable borrow occurs here
...
60 |        start_nodes.remove(&n);
   |        ^^^^^^^^^^^ mutable borrow occurs here
...
77 |     }
   |     - immutable borrow ends here

Why is start_nodes.iter() considered an immutable borrow? What approach should I take instead to get the first member?

I'm using version 1.14.0 (not by choice).

Your example [seems to work](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2eb06ccb56f4e95d3b0014fbfc011da4) with Rust 2018 (which uses NLL). — Lukas Kalbertodt, Feb 03 '19 at 20:28
@LukasKalbertodt thanks, you're right. Unfortunately using the latest compiler isn't a solution for me as this is for a uni assessment and the marking environment uses Rust 1.14.0. However, I should be able to make it work with the knowledge that I'm not trying to do something stupid. — Karl, Feb 03 '19 at 20:43
@Karl Unrelated, but out of interest: what university? Always interested in seeing where Rust is taught. — Lukas Kalbertodt, Feb 03 '19 at 20:45
@LukasKalbertodt University of Kent. It might disappoint you, though, that this is just one module that looks at various languages, so the Rust coverage is pretty superficial. — Karl, Feb 03 '19 at 20:52
@Stargateur apologies, edited. Didn't realise that the compiler wasn't the latest version when I posted. — Karl, Feb 03 '19 at 20:55
https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=8aa4213db032f44d7175c367f06b14c6, if you can't use NLL you need to scope lexical your borrow. See, https://stackoverflow.com/a/50253558/7076153, all links have different context where this problem occur. — Stargateur, Feb 03 '19 at 21:05
@Stargateur thanks, introducing a new scope worked, posted an answer below. — Karl, Feb 03 '19 at 21:19

Sven Marnach · Accepted Answer · 2019-02-03T21:48:34.543

Why is start_nodes.iter() considered an immutable borrow?

Whenever you ask a question like this one, you need to look at the prototype of the function, in this case the prototype of BTreeSet::iter():

fn iter(&self) -> Iter<T>

If we look up the Iter type that is returned, we find that it's defined as

pub struct Iter<'a, T> where T: 'a { /* fields omitted */ }

The lifetime 'a is not explicitly mentioned in the definition of iter(); however, the lifetime elision rules make the function definition equivalent to

fn iter<'a>(&'a self) -> Iter<'a, T>

From this expanded version, you can see that the return value has a lifetime that is bound to the lifetime of the reference to self that you pass in, which is just another way of stating that the function call creates a shared borrow that lives as long as the return value. If you store the return value in a variable, the borrow lives at least as long as the variable.

What approach should I take instead to get the first member?

As noted in the comments, your code works on recent versions of Rust due to non-lexical lifetimes – the compiler figures out by itself that start_iter and start_iter_cloned don't need to live longer than the call to next(). In older versions of Rust, you can artificially limit the lifetime by introducing a new scope:

while !start_nodes.is_empty() {
    let n = {
        let mut start_iter = start_nodes.iter();
        let mut start_iter_cloned = start_iter.cloned();
        start_iter_cloned.next().unwrap()
    };
    start_nodes.remove(&n);
}

However, note that this code is needlessly long-winded. The new iterator you create and its cloning version only live inside the new scope, and they aren't really used for any other purpose, so you could just as well write

while !start_nodes.is_empty() {
    let n = start_nodes.iter().next().unwrap().clone();
    start_nodes.remove(&n);
}

which does exactly the same, and avoids the issues with long-living borrows by avoiding to store the intermediate values in variables, to ensure their lifetime ends immediately after the expression.

Finally, while you don't give full details of your use case, I strongly suspect that you would be better off with a BinaryHeap instead of a BTreeSet:

use std::collections::BinaryHeap;

fn main() {
    let mut start_nodes = BinaryHeap::new();
    start_nodes.push(42);
    while let Some(n) = start_nodes.pop() {
        // Do something with `n`
    }
}

This code is shorter, simpler, completely sidesteps the issue with the borrow checker, and will also be more efficient.

score 0 · Answer 2 · answered Feb 03 '19 at 21:19

Not sure this is the best approach, but I fixed it by introducing a new scope to ensure that the immutable borrow ends before the mutable borrow occurs:

use std::collections::BTreeSet;

fn main() {
    let mut start_nodes = BTreeSet::new();

    // add items to the set

    while !start_nodes.is_empty() {
        let mut n = 0;

        {
            let mut start_iter = start_nodes.iter();
            let mut start_iter_cloned = start_iter.cloned();

            let x = &mut n;
            *x = start_iter_cloned.next().unwrap();
        }

        start_nodes.remove(&n);    
    } 
}

Getting first member of a BTreeSet

2 Answers2

Linked

Related