Как обновить или вставить на Vec?

Question

Я пишу структуру данных в Rust. Он содержит Vec пар ключ-значение. При вставке в структуру мне нужно найти соответствующий ключ и обновить как ключ, так и значение (которое на самом деле является дочерним указателем). Код выглядит примерно так, где pivots это ref mut в Vec<Pivot> а также Pivot это просто структура с двумя полями:

match pivots.iter_mut().find(|ref p| key <= p.min_key) { // first mutable borrow
    Some(ref mut pivot) => {
        // If there is one, insert into it and update the pivot key
        pivot.min_key = key;
        pivot.child.insert(key, value) // recursive call
    },
    // o/w, insert a new leaf at the end
    None => pivots.push(Pivot /* ... */) // second mutable borrow
}

Но есть проблема. Даже если я не использую изменяемый итератор во втором ответвлении match, заемщик жалуется, что я не могу заимствовать *pivots как изменяемые более одного раза за один раз ".

Это имеет смысл для меня, потому что первый заем все еще находится в объеме, даже если он не используется в этом случае match, Это немного неудобно: умный контролер наверняка скажет, что заимствования не перекрываются. Я видел в сети кого-то, кто советовал использовать досрочное возвращение, чтобы избежать этой проблемы, например:

match pivots.iter_mut().find(|ref p| key <= p.min_key) {
    Some(ref mut pivot) => {
        pivot.min_key = key;
        pivot.child.insert(key, value);
        return
    },
    None => ()
};
pivots.push(Pivot /* ... */)

но это кажется трудным для понимания, особенно когда это означает разбиение этого кода на его собственную функцию, чтобы позволить return, Есть ли более идиоматический способ выполнить операцию обновления или вставки?

Answer 1

Существует объединенная RFC "нелексическая продолжительность жизни" ( проблема отслеживания), которая должна решить эту проблему в долгосрочной перспективе. Пока вы можете обойти это с некоторой дополнительной обработкой потока управления.

Вы могли бы сделать ваш матч bool значение, независимо от того, произошло обновление или нет, и иметь условный блок ниже, используя это значение для добавления. Я считаю целесообразным поместить логику "обновить или добавить" в отдельную функцию (используя return после обновления) более идиоматический подход:

Детская площадка

use std::collections::HashMap;

pub struct Pivot {
    pub min_key: u64,
    pub child: HashMap<u64, ()>,
}

fn update_or_append(pivots: &mut Vec<Pivot>, key: u64, value: ()) {
    if let Some(pivot) = pivots.iter_mut().find(|ref p| key <= p.min_key) {
        // If there is one, insert into it and update the pivot key
        pivot.min_key = key;
        pivot.child.insert(key, value);
        return;
    }
    // otherwise insert a new leaf at the end
    let mut m = HashMap::new();
    m.insert(key, value);
    pivots.push(Pivot {
        min_key: key,
        child: m,
    });
}

fn main() {
    let mut pivots = Vec::new();
    update_or_append(&mut pivots, 100, ());
}

Использование ночной функции nll (работа над "нелексическими временами жизни") ваш исходный код уже должен работать:

Детская площадка

#![feature(nll)]
use std::collections::HashMap;

pub struct Pivot {
    pub min_key: u64,
    pub child: HashMap<u64, ()>,
}

fn update_or_append(pivots: &mut Vec<Pivot>, key: u64, value: ()) {
    match pivots.iter_mut().find(|ref p| key <= p.min_key) {
        Some(pivot) => {
            // If there is one, insert into it and update the pivot key
            pivot.min_key = key;
            pivot.child.insert(key, value);
            return;
        }
        // o/w insert a new leaf at the end
        None => {
            let mut m = HashMap::new();
            m.insert(key, value);
            pivots.push(Pivot {
                min_key: key,
                child: m,
            });
        }
    }
}

fn main() {
    let mut pivots = Vec::new();
    update_or_append(&mut pivots, 100, ());
}

Используя bool чтобы отследить, произошло ли обновление:

Детская площадка

use std::collections::HashMap;

pub struct Pivot {
    pub min_key: u64,
    pub child: HashMap<u64, ()>,
}

fn update_or_append(pivots: &mut Vec<Pivot>, key: u64, value: ()) {
    let updated = match pivots.iter_mut().find(|ref p| key <= p.min_key) {
        Some(pivot) => {
            // If there is one, insert into it and update the pivot key
            pivot.min_key = key;
            pivot.child.insert(key, value);
            true
        }
        // o/w insert a new leaf at the end below
        None => false,
    };
    if !updated {
        let mut m = HashMap::new();
        m.insert(key, value);
        pivots.push(Pivot {
            min_key: key,
            child: m,
        });
    }
}

fn main() {
    let mut pivots = Vec::new();
    update_or_append(&mut pivots, 100, ());
}

Answer 2

Кажется, что лучший способ сделать это - использовать индекс вместо итератора.

match pivots.iter().position(|ref p| key <= p.min_key) {
    Some(i) => {
        // If there is one, insert into it and update the pivot key
        let pivot = &mut pivots[i];
        pivot.min_key = key;
        pivot.child.insert(key, value)
    },
    // o/w, insert a new leaf at the end
    None => pivots.push(Pivot /* ... */)
}

Таким образом, нет необходимости iter_mut, Я все еще не совсем доволен этой альтернативой, потому что это означает использование явного индекса вместо итератора. Это хорошо для Vec но не будет работать для контейнера со структурой, которая не имеет O(1) индексации с произвольным доступом.

Я бы принял другой ответ, который позволит мне избежать использования индекса.