如何组合可变迭代器？

Question

Editor's note: This code example is from a version of Rust prior to 1.0 and is not syntactically valid Rust 1.0 code. Updated versions of this code produce different errors, but the answers still contain valuable information.

我想制作一个生成质数流的迭代器。我一般的想法是用连续的过滤器包装一个迭代器，例如你从

开始

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
        }        
    }
}

我玩过这个的变体，但我似乎无法让生命周期和类型相匹配。现在编译器告诉我

我无法变异self.base
变量 prime 的寿命不够长

这是我遇到的错误

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。这是必要的，因为您需要用消耗它的值替换它，因此内部迭代器可能会在短时间内从结构中 "absent" 。 Option 缺少 Rust 模型。 Option::take 用 None 和 returns 替换它调用的值。这在随机播放不可复制的对象时很有用。

但是请注意，此筛子实现在内存和计算上都将是低效的 - 对于每个素数，您都在创建一个额外的迭代器层，它占用堆 space。调用 next() 时堆栈的深度也随着素数的数量线性增长，所以你会在足够大的数字上得到堆栈溢出：

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

运行它：

% ./test1 

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

如何组合可变迭代器？

How to compose mutable Iterators?

iterator

rust

immutability

lifetime