生鏽實現合併排序的迭代器

Question

我想實現一個迭代器，合併兩個排序的迭代器。我正在運行從結構中借用字段的問題。

如何避免此錯誤？我嘗試使用借來的引用，但似乎沒有幫助，因爲最終我需要移動a_item和b_item的值。

use std::num::Saturating; 

pub struct MergeSorted<A, T> { 
    a: T, 
    b: T, 
    a_item: Option<A>, 
    b_item: Option<A>, 
} 

impl<A: Ord, T: Iterator<A>> Iterator<A> for MergeSorted<A, T> { 
    #[inline] 
    fn next(&mut self) -> Option<A> { 

     match (self.a_item, self.b_item) { 
      (None, None) => None, 

      (None, Some(y)) => { 
       let result = self.b_item; 
       self.b_item = None; 
       return result; 
      } 

      (Some(x), None) => { 
       let result = self.a_item; 
       self.a_item = self.a.next(); 
       result 
      } 

      (Some(x), Some(y)) => { 
       if x < y { 
        let result = self.a_item; 
        self.a_item = self.a.next(); 
        result 
       } else { 
        let result = self.b_item; 
        self.b_item = self.b.next(); 
        result 
       } 
      } 
     } 
    } 

    #[inline] 
    fn size_hint(&self) -> (uint, Option<uint>) { 
     // stub 
     (10, Some(100)) 
    } 
} 

下面是具體的錯誤，這是對self.a_item和self.b_item的所有用法重複的。

error: cannot move out of dereference of `&mut`-pointer 
     match (self.a_item, self.b_item) { 
       ^~~~~~~~~~~ 

Answer 1

的第一個問題是這樣的模式：

let result = self.b_item; 
self.b_item = None; 
return result; 

第一行後，第二行self.b_item變得搬出之前，在self做一個「洞」（即使我們忘記了self是一個借來的指針，你不能移出它）。這是不允許的。爲了表達這種模式，在std::mem中有一個特殊的功能，叫做replace。

第二個主要問題是A是不是暗示可複製，所以當您嘗試匹配Option<A>類型的值，這些值都搬了出來，但是從內的&/&mut指針被禁止搬出。解決這個問題的唯一方法是匹配參考。但是你應該小心，因爲借款規則只允許你一次有單一的可變借款。因此，您必須使用模式綁定，通過匹配語句組織一種對「self.a_item」和「self.b_item」的引用的「流程」。

下面的代碼編譯。您也可以直接用mem::replace()調用替換result變量中的result變量和Some()用法，但是我認爲分隔值選擇和mem::replace()調用會使代碼更清晰。另外，我不能在最後的match手臂中使用Some(x)和Some(y)模式，因爲引用本身被移動到a_item和b_item。

use std::mem; 

pub struct MergeSorted<A, T> { 
    a: T, 
    b: T, 
    a_item: Option<A>, 
    b_item: Option<A>, 
} 

impl<A: Ord, T: Iterator<A>> Iterator<A> for MergeSorted<A, T> { 
    #[inline] 
    fn next(&mut self) -> Option<A> { 
     let result = match (&mut self.a_item, &mut self.b_item) { 
      (&None, &None) => None, 
      (&None, b_item @ &Some(_)) => Some((b_item, None)), 
      (a_item @ &Some(_), &None) => Some((a_item, self.a.next())), 
      (a_item @ &Some(_), b_item @ &Some(_)) => Some(
       if a_item.get_ref() < b_item.get_ref() { 
        (a_item, self.a.next()) 
       } else { 
        (b_item, self.b.next()) 
       } 
      ) 
     }; 

     result.and_then(|(dest, value)| mem::replace(dest, value)) 
    } 

    #[inline] 
    fn size_hint(&self) -> (uint, Option<uint>) { 
     // stub 
     (10, Some(100)) 
    } 
} 

Answer 2

該解決方案將與Rust 1.2和Rust 1.x一起使用。

我沒有保留自己的Option項目，而是選擇使用peekable迭代器適配器。這使我們能夠看到一個項目，而不會丟失它。

我還將Iterator::next方法分解爲兩部分 - 一部分決定從哪一方拉取，另一部分確實推進該迭代器。

現在還有關於如何用關聯類型定義迭代器的一般更新。

use std::iter::Peekable; 
use std::cmp::Ordering; 

struct MergeAscending<L, R> 
where 
    L: Iterator<Item = R::Item>, 
    R: Iterator, 
{ 
    left: Peekable<L>, 
    right: Peekable<R>, 
} 

impl<L, R> MergeAscending<L, R> 
where 
    L: Iterator<Item = R::Item>, 
    R: Iterator, 
{ 
    fn new(left: L, right: R) -> Self { 
     MergeAscending { 
      left: left.peekable(), 
      right: right.peekable(), 
     } 
    } 
} 

impl<L, R> Iterator for MergeAscending<L, R> 
where 
    L: Iterator<Item = R::Item>, 
    R: Iterator, 
    L::Item: Ord, 
{ 
    type Item = L::Item; 

    fn next(&mut self) -> Option<L::Item> { 
     let which = match (self.left.peek(), self.right.peek()) { 
      (Some(l), Some(r)) => Some(l.cmp(r)), 
      (Some(_), None) => Some(Ordering::Less), 
      (None, Some(_)) => Some(Ordering::Greater), 
      (None, None) => None, 
     }; 

     match which { 
      Some(Ordering::Less) => self.left.next(), 
      Some(Ordering::Equal) => self.left.next(), 
      Some(Ordering::Greater) => self.right.next(), 
      None => None, 
     } 
    } 
} 

fn main() { 
    let left = [1, 3, 5, 7, 9]; 
    let right = [3, 4, 5, 6, 7]; 

    let result: Vec<_> = MergeAscending::new(left.iter(), right.iter()).collect(); 
    println!("{:?}", result); 
}