如何編寫可變迭代器？

Question

我想做一個迭代器，生成素數的流。我一般的思維過程是如此，例如，你有

let mut n = (2..N) 

開始，然後每個素數你變異迭代器，並添加過濾器

let p1 = n.next() 
n = n.filter(|&x| x%p1 !=0) 
let p2 = n.next() 
n = n.filter(|&x| x%p2 !=0) 

我想包一個迭代器連續濾膜使用下面的代碼，但我似乎無法得到它的工作

struct Primes { 
    base: Iterator<Item = u64>, 
} 

impl<'a> Iterator for Primes<'a> { 
    type Item = u64; 

    fn next(&mut self) -> Option<u64> { 
     let p = self.base.next(); 
     match p { 
      Some(n) => { 
       let prime = n.clone(); 
       let step = self.base.filter(move |&: &x| {x%prime!=0}); 
       self.base = &step as &Iterator<Item = u64>; 
       Some(n)     
      }, 
      _ => None 
     }   
    } 
} 

我與這個變化玩弄，但我似乎無法得到壽命和類型匹配。眼下編譯器告訴我

1. 我不能突變self.base
2. 變量主要不活夠

這裏長我得到

solution.rs:16:17: 16:26 error: cannot borrow immutable borrowed content `*self.base` as mutable 
solution.rs:16   let p = self.base.next(); 
                ^~~~~~~~~ 
solution.rs:20:28: 20:37 error: cannot borrow immutable borrowed content `*self.base` as mutable 
solution.rs:20     let step = self.base.filter(move |&: &x| {x%prime!=0}); 
                   ^~~~~~~~~ 
solution.rs:21:30: 21:34 error: `step` does not live long enough 
solution.rs:21     self.base = &step as &Iterator<Item = u64>; 
                    ^~~~ 
solution.rs:15:39: 26:6 note: reference must be valid for the lifetime 'a as defined on the block at 15:38... 
solution.rs:15  fn next(&mut self) -> Option<u64> { 
solution.rs:16   let p = self.base.next(); 
solution.rs:17   match p { 
solution.rs:18    Some(n) => { 
solution.rs:19     let prime = n.clone(); 
solution.rs:20     let step = self.base.filter(move |&: &x| {x%prime!=0}); 
            ... 
solution.rs:20:71: 23:14 note: ...but borrowed value is only valid for the block suffix following statement 1 at 20:70 
solution.rs:20     let step = self.base.filter(move |&: &x| {x%prime!=0}); 
solution.rs:21     self.base = &step as &Iterator<Item = u64>; 
solution.rs:22     Some(n)     
solution.rs:23    }, 
error: aborting due to 3 previous errors 

錯誤

Rust爲什麼不讓我這樣做？

Answer 1

這裏是一個工作版本：

struct Primes<'a> { 
    base: Option<Box<Iterator<Item=u64>+'a>>, 
} 

impl<'a> Iterator for Primes<'a> { 
    type Item = u64; 

    fn next(&mut self) -> Option<u64> { 
     let p = self.base.as_mut().unwrap().next(); 
     p.map(|n| { 
      let base = self.base.take(); 
      let step = base.unwrap().filter(move |x| x % n != 0); 
      self.base = Some(Box::new(step)); 
      n     
     }) 
    } 
} 

impl<'a> Primes<'a> { 
    #[inline] 
    pub fn new<I: Iterator<Item=u64>+'a>(r: I) -> Primes<'a> { 
     Primes { 
      base: Some(Box::new(r)) 
     } 
    } 
} 

fn main() { 
    for p in Primes::new(2..).take(32) { 
     print!("{} ", p); 
    } 
    println!(""); 
} 

首先，我使用Box<Iterator>特質對象。拳擊是不可避免的，因爲內部迭代器必須存儲在next()調用之間的某個地方，而參考特性對象則無法存儲。

其次，我做了內部迭代器Option。這是必要的，因爲您需要用消耗它的值來替換它，所以內部迭代器可能在短時間內從結構中「缺席」。 Rust模特缺席Option。 take()方法Option用None替換它所調用的值，並返回所有內容。這在洗牌周圍不可複製的對象時非常有用。

但是，請注意，這個篩選實現將會是內存和計算效率低下的問題 - 對於每個主數據庫，您將創建一個額外的迭代器層，這會佔用堆空間。還呼籲next()當堆棧的深度與素數的數量呈線性增長，所以你會得到一個堆棧溢出的數量足夠多：

fn main() { 
    println!("{}", Primes::new(2..).nth(10000).unwrap()); 
} 

運行它：

% ./test1 

thread '<main>' has overflowed its stack 
zsh: illegal hardware instruction (core dumped) ./test1