获取 BTreeSet 的第一个成员 [英] Getting first member of a BTreeSet

问题描述

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

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

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

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

我使用的是 1.14.0 版本(不是自愿的).

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

推荐答案

为什么 start_nodes.iter() 被认为是不可变的借用?

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

每当你问这样的问题时，你需要看一下函数的原型，在这种情况下是BTreeSet::iter()的原型:

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>

查找返回的Iter类型，发现定义为

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 */ }

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

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>

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

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?

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

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.

最后，虽然您没有提供用例的完整细节，但我强烈怀疑您最好使用 BinaryHeap 而不是 BTreeSet:

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.

这篇关于获取 BTreeSet 的第一个成员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！