Получение первого члена 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

Почему start_nodes.iter() считается неизменным заимствованием?

Всякий раз, когда вы задаете вопрос, подобный этому, вам нужно посмотреть на прототип функции, в данном случае прототипиз BTreeSet::iter():

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, чтовы передаете, что является еще одним способом заявить, что вызов функции создает общий заем, который живет столько же, сколько и возвращаемое значение.Если вы сохраняете возвращаемое значение в переменной, заимствование живет, по крайней мере, столько же, сколько и переменная.

Какой подход вместо этого следует использовать, чтобы получить первый член?

Как отмечено в комментариях, ваш код работает на последних версиях 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`
    }
}

Этот код короче, проще, полностью обходит проблему с помощью средства проверки заимствований и также будетболее эффективный.

Answer 2

Не уверен, что это лучший подход, но я исправил его, введя новую область действия, чтобы гарантировать, что неизменяемый заем заканчивается до того, как произойдет изменяемый заем:

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