如何在 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 的第二个分支中使用可变迭代器，但借用检查器抱怨我 "cannot borrow *pivots as mutable more than once at a time".

这对我来说非常有意义，因为第一个借用仍在范围内，即使它没有在 match 的情况下使用。这有点不方便：一个更聪明的检查员肯定能分辨出借用是不重叠的。我在网上看到有人建议使用 early-return 来避免这个问题，就像这样：

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

看起来最好的方法是使用索引而不是迭代器。

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) 随机访问索引的容器。

我会接受一个不同的答案，这样我就可以避免使用索引。

Answer 2

有一个合并的 RFC "non-lexical lifetimes" 解决了这个问题运行。使用 Rust 1.31 中可用的 Rust 2018 中的非词法生命周期，您的代码按原样运行：

Playground

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

如果此 不适用于您的代码，请查看

在 Rust 2018 之前，您可以通过一些额外的控制流处理来解决它。

无论更新是否发生，您都可以让匹配产生一个 bool 值，并在下方使用该值追加一个条件块。我考虑将 "update-or-append" 逻辑放入一个单独的函数（更新后使用 return ）更惯用的方法：

Playground

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

使用bool跟踪更新是否发生：

Playground

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

如何在 Vec 上更新或插入？

How to update-or-insert on a Vec?

rust

borrow-checker