如何在迭代向量时一次性插入/删除/修改多个元素？

Question

如何在迭代向量时一次性插入/删除/修改多个元素？

3

我希望能够一次迭代数组/向量并在此过程中修改多个元素，因为这是最优解。我不想一遍又一遍地扫描它，只是因为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;
    }
}

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

使用迭代器一次性完成
绕开这些借用规则限制

这里提供了borrow splitting，但我不知道如何在这里应用它。

- NeatNerd

3

将vec进行原地修改是否是明确的目标？相比尝试更改原始的vec，通过创建一个新的Vec并向其中添加元素实现会更加容易。 - loganfsmyth

@loganfsmyth可能是一个小向量、小数据结构的选择。 - NeatNerd

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shepmaster · Accepted Answer

通常情况下，这是一类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之间来回切换写入，但此时可能有比向量更好的数据结构，比如区间树。