如何迭代矢量一次并插入/删除/修改多个元素？

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);

• 如果在调用之前 i1或之后删除任何值,则所有值将移动i2时vec.remove(i3),引用in 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.如果你这么做很多,你可以在两个预先分配的Vecs 之间来回翻转,但在那时,可能有一个比矢量好得多的数据结构; 也许是间隔树.