如何在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 给我以下编译器错误（通过游乐场链接查看完整信息）：

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

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

- Chris Pearce

Answer 1

这段代码无法正常工作的原因是当前借用检查器的限制。这与NLL case #3非常相似，其中编译器在整个match语句中过度借用，而借用仅在其中一个分支中使用。使用实验性的“Polonius”借用检查器（可通过夜间编译器和-Z polonius标志获得），您的代码将被接受为原样。

在稳定的编译器中工作时，重新设计数据结构可能是一个好主意，就像Sébastien Renauld's answer所建议的那样。但如果您需要使其与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 的结果不是一个引用，所以在 if let 期间，对 vec 的借用并未被保留。

以下问题类似，它们通过从循环中提前返回来找到了相同的限制：

• 即使启用 NLL，循环中的双重可变借用错误仍会发生
• 当返回包含引用的 Result 时，出现“变量存活时间不足”的错误，但实际上它的存活时间足够长

- trent

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问题中看到的那样，它并不在不久的将来实现。

- Sébastien Renauld

---

@ChrisPearce HashSet 内部包含一个 HashMap，因此 get_or_insert() 操作的是键来检索，而不是整个集合。这是关键区别，也是我的（可行的）代码片段所说明的 - 由于生命周期的工作方式，你被迫将步骤分为两个部分，无论是在不同的结构体中还是像我一样，在不同的路径中。首先，你进行编辑，然后再返回。 - Sébastien Renauld

我刚刚查看了HashMap，我有一个疑虑，即使用get_or_insert将无法返回可变引用，因为您不允许以使哈希无效的方式修改HashMap中的条目。这是否只留下了使用Vec将插入与返回分开的选项？ - Chris Pearce

@ChrisPearce，此时我真的需要问一下你想要做什么。你有一个拥有T的对象，你将其用作默认值；整个过程听起来你实际上应该将其拆分成两个部分。我将重写答案中的片段以考虑可变性要求（所有更改都是引用），并提供更好、更具惯用性的方法。 - Sébastien Renauld

没关系，没有更习惯用的方法；在每种情况下，您都将拆分插入和检索。这是最好的选择，而不需要完善您的要求（并选择更好的存储方式）。然而，我仍然对您的用例感到困惑；毕竟，每次使用该方法时，您都会默认实例化一个对象。这肯定完全违背了您尝试做的事情的目的。 - Sébastien Renauld

这很公平，我认为在我简化代码以适合公开提问的尝试中，很多上下文都丢失了。如果您添加一些关于为什么一步操作不起作用以及带有分离的示例代码的内容，我将接受您的答案。感谢您的帮助。 - Chris Pearce