如何迭代一次向量并在此过程中插入/删除/修改多个元素?

Question

我想迭代一次数组/向量并在此过程中修改多个元素，因为这是最理想的解决方案。我不想仅仅因为 Rust 对借款不满意而一遍又一遍地扫描它。

我在排序向量中存储表示为[start;stop]的区间列表，我想添加一个新区间。它可能重叠，所以我想删除所有不再需要的元素。我想一口气完成所有工作。算法可以看起来像这样(我剪掉了一些部分(：

use std::cmp::{min, max};
#[derive(Debug, PartialEq, Clone, Copy)]
struct Interval {
start: usize,
stop: usize,
}
impl Interval {
fn new(start: usize, stop: usize) -> Interval {
Interval {
start: start,
stop: stop,
}
}
pub fn starts_before_disjoint(&self, other: &Interval) -> bool {
self.start < other.start && self.stop < other.start
}
pub fn starts_before_non_disjoint(&self, other: &Interval) -> bool {
self.start <= other.start && self.stop >= other.start
}
pub fn starts_after(&self, other: &Interval) -> bool {
self.start > other.start
}
pub fn starts_after_disjoint(&self, other: &Interval) -> bool {
self.start > other.stop
}
pub fn starts_after_nondisjoint(&self, other: &Interval) -> bool {
self.start > other.start && self.start <= other.stop
}
pub fn disjoint(&self, other: &Interval) -> bool {
self.starts_before_disjoint(other)
}
pub fn adjacent(&self, other: &Interval) -> bool {
self.start == other.stop + 1 || self.stop == other.start - 1
}
pub fn union(&self, other: &Interval) -> Interval {
Interval::new(min(self.start, other.start), max(self.stop, other.stop))
}
pub fn intersection(&self, other: &Interval) -> Interval {
Interval::new(max(self.start, other.start), min(self.stop, other.stop))
}
}
fn main() {
//making vectors
let mut vec = vec![
Interval::new(1, 1),
Interval::new(2, 3),
Interval::new(6, 7),
];
let addition = Interval::new(2, 5); // <- this will take over interval @ 2 and will be adjacent to 3, so we have to merge
let (mut i, len) = (0, vec.len());
while i < len {
let r = &mut vec[i];
if *r == addition {
return; //nothing to do, just a duplicate
}
if addition.adjacent(r) || !addition.disjoint(r) {
//if they are next to each other or overlapping
//lets merge
let mut bigger = addition.union(r);
*r = bigger;
//now lets check what else we can merge
while i < len - 1 {
i += 1;
let next = &vec[i + 1];
if !bigger.adjacent(next) && bigger.disjoint(next) {
//nothing to merge
break;
}
vec.remove(i); //<- FAIL another mutable borrow
i -= 1; //lets go back
vec[i] = bigger.union(next); //<- FAIL and yet another borrow
}
return;
}
if addition.starts_before_disjoint(r) {
vec.insert(i - 1, addition); // <- FAIL since another refence already borrowed @ let r = &mut vec[i]
}
i += 1;
}
}

由于借用规则，它在几个地方失败了。有没有办法

1. 一次性使用迭代器完成
2. 解决借款问题

有可用的借用拆分，但我看不出如何在这里应用它。

Answer 1

一般来说，你不能，因为这正是Rust 防止的一类错误。检查我用唯一变量替换i的事件序列，因为编译器无论如何都不知道将使用哪些值。

let r = &mut vec[i1];
let next = &vec[i2];
vec.remove(i3);
vec[i4] = bigger.union(next);         
vec.insert(i5, addition);

• 如果在调用vec.remove(i3)时删除i1或i2之前的任何值，则next和r中的引用将失效，因为所有值都将移动。
• 如果i5在i1或i2之前，那么同样的事情也会发生，只是在另一个方向。
• 如果i4等于i2，则next的不可变值将被改变。
• 如果i4等于i1，则对r的修改将通过另一条路径发生，而不是可变引用的单一所有者。

请注意其中每个如何与编译器告诉您的点相对应。

如果编译器变得足够聪明，可以理解您不再需要引用，则其中一些情况可能会通过非词法生存期进行修复。对于通过数组索引更改向量的情况，它无济于事;编译器不够聪明，无法跟踪您的数学并证明您从未接触过"错误"索引，也不够聪明，无法意识到如果索引是，则对数组的两个引用是不相交的。

---

在这种特定情况下，由于您的类型实现了Copy，因此可以利用它来获取值。在需要时直接写回向量。如果您从不借款，则不会有借款错误。

fn main() {
let mut vec = vec![
Interval::new(1, 1),
Interval::new(2, 3),
Interval::new(6, 7),
];
let addition = Interval::new(2, 5);
let (mut i, len) = (0, vec.len());
while i < len {
let r = vec[i];
if r == addition {
return;
}
if addition.adjacent(&r) || !addition.disjoint(&r) {
let mut bigger = addition.union(&r);
vec[i] = bigger;
while i < len - 1 {
i += 1;
let next = vec[i + 1];
if !bigger.adjacent(&next) && bigger.disjoint(&next) {
break;
}
vec.remove(i); 
i -= 1;
vec[i] = bigger.union(&next);
}
return;
}
if addition.starts_before_disjoint(&r) {
vec.insert(i - 1, addition);
}
i += 1;
}
}

实际上，我会按照 loganfsmyth 的建议去做，并更改算法以获取一部分间隔并返回新Vec。如果你经常这样做，你可以在两个预先分配的Vec之间来回切换写入，但在这一点上，可能有一个比向量更好的数据结构;也许是一个间隔树。