rust - 获取 BTreeSet 的第一个成员

Question

在 Rust 中，我有一个 BTreeSet，我用它来保持我的值有序。我有一个循环，应该检索并删除集合的第一个(最低)成员。我正在使用克隆的迭代器来检索第一个成员。这是代码:

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);

    }
}

然而，这给了我以下编译错误:

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

为什么 start_nodes.iter() 被认为是不可变借用？我应该采取什么方法来获得第一个成员？

我使用的是 1.14.0 版本(不是我自己选择的)。

Answer 1

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

每当你问这样的问题时，你需要查看函数的原型(prototype)，在本例中是 BTreeSet::iter() 的原型(prototype):

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

如果我们查找返回的 Iter 类型，我们发现它被定义为

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

生命周期'a在iter()的定义中没有明确提及；但是，生命周期省略规则使函数定义等同于

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

从这个扩展版本中，您可以看到返回值的生命周期与您传入的 self 引用的生命周期绑定(bind)，这只是说明函数调用创建一个与返回值一样长的共享借用。如果将返回值存储在变量中，则借用至少与变量一样长。

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

如评论中所述，由于非词法生命周期，您的代码适用于最新版本的 Rust——编译器自行计算出 start_iter 和 start_iter_cloned 不不需要长于对 next() 的调用。在旧版本的 Rust 中，您可以通过引入新范围来人为地限制生命周期:

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);
}

但是，请注意这段代码不必要地冗长。您创建的新迭代器及其克隆版本仅存在于新范围内，它们并没有真正用于任何其他目的，因此您也可以这样写

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

它做的完全一样，并通过避免将中间值存储在变量中来避免长期借用的问题，以确保它们的生命周期在表达式后立即结束。

最后，虽然您没有提供用例的完整细节，但我强烈怀疑您使用 BinaryHeap 而不是 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`
    }
}

这段代码更短、更简单，完全回避了借用检查器的问题，而且效率也会更高。