如何在Vec上进行更新或插入操作？

Question

我正在使用Rust编写数据结构。它包含一个键值对的Vec。在向结构中插入内容时，我需要查找匹配的键并更新键和值（实际上是一个子指针）。代码看起来像这样，其中pivots是对Vec<Pivot>的ref mut引用，而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时。是否有更常见的方法执行更新或插入操作？

- Dan Hulme

Answer 1

在 Rust 中，使用称为“非词法生命周期”的方法可以解决这个问题。通过合并的RFC （非词法生命周期） ，从长远来看可以解决这个问题。 在 Rust 2018 中使用非词法生命周期，在 Rust 1.31 中可用，您的代码将按原样工作：

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

如果这对你的代码不起作用，请查看：

• 从HashMap或Vec返回引用会导致借用超出其所在范围吗？

---

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

您可以让匹配生成一个bool值，表明是否发生了更新，然后在下面使用该值进行条件块附加。我认为将“更新或附加”逻辑放入单独的函数中（在更新后使用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, ());
}

- Stefan

---

分离函数选项已经在问题中考虑过了。也许答案可以提供第一个建议解决方案的源代码，其中match生成一个布尔值？ - user4815162342

可能是我的错误，我经常跳过问题中的长文本，并没有意识到它们已经包含了（不需要的）答案。另一方面，答案不应该在那里出现，所以在这种情况下我并不感到内疚。而且我认为一个单独的函数实际上更容易理解。 - Stefan

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）随机访问索引的容器就行不通了。

我接受一个不使用索引的不同答案。

- Dan Hulme