可變的迭代器VEC <Vec<(K, V)>>

Question

我試圖創建類型的矢量的可變迭代器：Vec<Vec<(K, V)>>

迭代器代碼：

pub struct IterMut<'a, K: 'a, V: 'a> { 
    iter: &'a mut Vec<Vec<(K, V)>>, 
    ix: usize, 
    inner_ix: usize, 
} 

impl<'a, K, V> Iterator for IterMut<'a, K, V> { 
    type Item = (&'a K, &'a mut V); 

    #[inline] 
    fn next(&mut self) -> Option<(&'a K, &'a mut V)> { 

     while self.iter.len() < self.ix { 
      while self.iter[self.ix].len() < self.inner_ix { 
       self.inner_ix += 1; 
       let (ref k, ref mut v) = self.iter[self.ix][self.inner_ix]; 
       return Some((&k, &mut v)); 
      } 

      self.ix += 1; 
     } 

     return None; 
    } 
} 

我得到的錯誤是：

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements 
    --> src/main.rs:16:42 
    | 
16 |     let (ref k, ref mut v) = self.iter[self.ix][self.inner_ix]; 
    |           ^^^^^^^^^^^^^^^^^^ 
    | 
help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<(&'a K, &'a mut V)> 
    --> src/main.rs:11:5 
    | 
11 |  fn next(&mut self) -> Option<(&'a K, &'a mut V)> { 
    | ^

顯然我有一生的問題，但我不知道如何告訴編譯器，這應該工作。

這是你應該如何實現可變迭代器還是有更好的方法？

Answer 1

在調試神祕的錯誤消息時，我發現儘可能多地嘗試並隔離問題。

的第一步是打破錶達成其基本成分，讓我們通過分割索引步驟開始：

fn next(&mut self) -> Option<(&'a K, &'a mut V)> { 

    while self.iter.len() < self.ix { 
     while self.iter[self.ix].len() < self.inner_ix { 
      self.inner_ix += 1; 
      let outer: &'a mut Vec<_> = self.iter; 
      let inner: &'a mut Vec<_> = &mut outer[self.ix]; 
      let (ref k, ref mut v) = inner[self.inner_ix]; 
      return Some((&k, &mut v)); 
     } 

     self.ix += 1; 
    } 

    return None; 
} 

的Index性狀假設其輸出的壽命被鏈接到它的接收器的，所以爲了獲得一個'a的生命週期，我們需要接收器具有一個&'a的生命週期，並且它向上傳播，導致上面的代碼。

但是，這裏有一個問題：let outer: &'a mut Vec<_> = self.iter;不會編譯，因爲可變引用不是Copy。

那麼，如何從一個可變引用獲得可變引用（由於IndexMut獲得可變引用，這必須是可能的）？

一個使用重新借用：let outer: &'a mut Vec<_> = &mut *self.iter;。

而且，哦：

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements 
    --> <anon>:16:45 
    | 
16 |     let outer: &'a mut Vec<_> = &mut *self.iter; 
    |            ^^^^^^^^^^^^^^^ 
    | 

的reborrowed參考無效'a，它是有效的只爲self（尚未命名）的壽命！

爲什麼生鏽？爲什麼？

因爲否則將是不安全的。

&mut T保證不會被混淆，但你的方法可能會造成混淆引用（如果你忘了推進指數）：

#[inline] 
fn next(&mut self) -> Option<(&'a K, &'a mut V)> { 
    let (ref k, ref mut v) = self.iter[self.ix][self.inner_ix]; 
    return Some((&k, &mut v)); 
} 

而且，即使你不這樣做，還有的不能保證你不沒有一個允許「退後」的方法。

TL; DR：您即將踏上地雷，你向堆棧溢出轉向替代;）

---

好的，但你如何實現迭代器！。

那麼，當然使用迭代器。正如Shepmaster（簡要地）回答的那樣，在FlatMap的幌子下，標準庫中有相同的內容。訣竅是將現有的迭代器用於細節的細節！

喜歡的東西：

use std::slice::IterMut; 

pub struct MyIterMut<'a, K: 'a, V: 'a> { 
    outer: IterMut<'a, Vec<(K, V)>>, 
    inner: IterMut<'a, (K, V)>, 
} 

然後你從inner，只要它提供的物品消耗，空當你從outer填充它。

impl<'a, K, V> MyIterMut<'a, K, V> { 
    fn new(v: &'a mut Vec<Vec<(K, V)>>) -> MyIterMut<'a, K, V> { 
     let mut outer = v.iter_mut(); 
     let inner = outer.next() 
         .map(|v| v.iter_mut()) 
         .unwrap_or_else(|| (&mut []).iter_mut()); 
     MyIterMut { outer: outer, inner: inner } 
    } 
} 

impl<'a, K, V> Iterator for MyIterMut<'a, K, V> { 
    type Item = (&'a K, &'a mut V); 

    #[inline] 
    fn next(&mut self) -> Option<(&'a K, &'a mut V)> { 
     loop { 
      match self.inner.next() { 
       Some(r) => return Some((&r.0, &mut r.1)), 
       None =>(), 
      } 

      match self.outer.next() { 
       Some(v) => self.inner = v.iter_mut(), 
       None => return None, 
      } 
     } 
    } 
} 

簡單的測試案例：

fn main() { 
    let mut v = vec![ 
     vec![(1, "1"), (2, "2")], 
     vec![], 
     vec![(3, "3")] 
    ]; 
    let iter = MyIterMut::new(&mut v); 
    let c: Vec<_> = iter.collect(); 
    println!("{:?}", c); 
} 

打印：

[(1, "1"), (2, "2"), (3, "3")] 

不如預期，所以它不是完全打破，但我希望我沒有要依靠對&[]是'static的竅門（即std::slice::IterMut實施Default）。

Answer 2

你提供任何理由，你重新實現標準Iterator::flat_map，所以我只是用那些和另一map去除可變性不需要：

fn main() { 
    let mut a: Vec<Vec<(u8, u8)>> = Default::default(); 
    let c = a.iter_mut() 
     .flat_map(|x| x.iter_mut()) 
     .map(|&mut (ref a, ref mut b)| (a, b)) 
     .count(); 
    println!("{}", c); 
} 

一旦你的，你可以只需return the iterator in one of the many ways。

#[derive(Debug, Default)] 
struct Thing<K, V>(Vec<Vec<(K, V)>>); 

impl<K, V> Thing<K, V> { 
    fn iter_mut<'a>(&'a mut self) -> Box<Iterator<Item = (&'a K, &'a mut V)> + 'a> { 
     Box::new(self.0 
      .iter_mut() 
      .flat_map(|x| x.iter_mut()) 
      .map(|&mut (ref a, ref mut b)| (a, b))) 
    } 
} 

fn main() { 
    let mut a = Thing::<u8, u8>::default(); 
    let c = a.iter_mut().count(); 
    println!("{}", c); 
}