如何迭代一次矢量，並在此過程中插入/刪除/修改多個元素？

Question

我想迭代一個數組/矢量一次，並在路上修改多個元素，因爲這是最優化的解決方案。我不想一次又一次地掃描它，只是因爲魯斯對借款感到不滿。

我在一個已排序的向量中存儲了一個表示爲[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. 迭代器做在一個四處借款

有borrow splitting提供

的工作，但我不知道怎樣才能在這裏使用它。

Answer 1

一般來說，你不能不能，因爲這是正是一類錯誤，防鏽防止。檢查我已經用唯一變量代替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)，然後在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 suggests，改變算法採取間隔的切片並返回一個新Vec。如果你這樣做了很多，你可以在兩個預先分配的Vec之間來回翻轉，但是在那一點上，可能比矢量有更好的數據結構;也許是一個interval tree。