如何查找或插入 Vec [重复]

Question

我正在尝试编写一个函数，它发现返回对 Vec 中现有元素的可变引用，或者如果它不存在则插入它并返回对新元素的可变引用。

我试过几次，但借阅检查员不相信。我已将我尝试编写的代码简化为下面的示例，它给出了相同的错误。

fn mut_find_or_insert<T: PartialEq>(vec: &mut Vec<T>, val: T) -> &mut T {
    if let Some(u) = vec.iter_mut().find(|u| **u == val) {
        u
    } else {
        vec.push(val);
        vec.last_mut().unwrap()
    }
}

游乐场链接：https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=cb12c38bcf3682b15a247d14aab48b6b

Rust 给我以下编译器错误（通过 playground 链接的完整消息）：

error[E0499]: cannot borrow `*vec` as mutable more than once at a time

这似乎应该可以在 Rust 中实现，但是我不清楚如何重新实现它以避免借用检查器错误。

Answer 1

这不像写的那样工作的原因是因为当前借用检查器的限制。这与 NLL 案例 #3 非常相似，其中编译器对整个

match

语句过度借用，而借用仅用于其中一个分支。使用实验性的“Polonius”借用检查器（在带有

-Z polonius

标志的夜间编译器上可用），您的代码将按原样接受。

在稳定的编译器中工作，按照 Sébastien Renauld 的回答 也建议的那样重新设计数据结构可能是个好主意，但是如果您需要使用

Vec

来完成这项工作，您可以通过简单地使用索引来解决它结束借用：

fn mut_find_or_insert<T: PartialEq>(vec: &mut Vec<T>, val: T) -> &mut T {
    if let Some(i) = vec.iter().position(|each| *each == val) {
        &mut vec[i]
    } else {
        vec.push(val);
        vec.last_mut().unwrap()
    }
}

这是有效的，因为调用

position

的结果不是引用，所以在

vec

期间不保留

if let

的借用。

这类似于以下问题，它们使用循环的早期返回设法找到相同的限制：

• 循环中的双重可变借用错误即使在 NLL 开启的情况下也会发生
• 返回包含引用的结果时“变量寿命不够长”，但它确实寿命足够长

Answer 2

Vec

是无序的，不是非常结构化的类型。它无法查找项目在其中的确切位置；默认函数最接近的是

contains()

，它只会告诉您是否包含该项目。

此外，由于一个

Vec

不是一个

Set

，“查找项或追加并返回”的行为是未定义的——“查找项”，如果有重复，需要定义进一步。

解决这个问题而不改变到正确的类型（

HashSet

是你真正想要的类型。注意

get_or_insert()

的存在，这就是你所追求的。使用正确的方法是值得的工作的结构，而不是试图让一切都适合

Vec

），我们将不得不自己构建它。保持你的签名，它看起来像这样（Playground）：

trait VecSeekOrAppend<T:PartialEq>:Sized {
    fn get_or_insert(&mut self, item: T) -> &mut T;
}

impl<T> VecSeekOrAppend<T> for Vec<T> 
    where T: PartialEq + Clone {

    fn get_or_insert(&mut self, item: T) -> &mut T {
        if !self.contains(&item) {
            self.push(item.clone());
        }
        for i in self.iter_mut() {
            if i == &mut item {
                return i;
            }
        }
        unreachable!();
    }
}

您的初始版本不起作用的原因是由于返回的生命周期要求；所有从

Vec

返回引用的方法都需要在使用期间有效。通过返回这样一个

&mut

引用，如果您尝试一次完成它，那么

Vec<_>

的突变将在已经有一个可变借用的情况下发生。

将循环一分为二，并执行插入（不保留引用）然后找到引用，可以让我们回避这个问题。执行此操作的另一种方法是通过可序列化或可散列的标识符存储项目（

HashMap

和

HashSet

工作的确切方式），以便天生提供这一层间接。

作品中有一个 rust 特性可以减轻一些这种痛苦（非词法生命周期），但是，正如你从 github issue 中看到的那样，它不会在不久的将来出现。