如何编写可变迭代器？

Question

如何编写可变迭代器？

7

编辑说明：此代码示例来自Rust 1.0之前的版本，不是符合语法的Rust 1.0代码。更新后的代码版本会产生不同的错误，但答案仍包含有价值的信息。

我想创建一个生成质数流的迭代器。我的一般思路是将一个迭代器与连续的过滤器包装起来，例如，您可以从以下内容开始：

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不允许我这样做？

- dkhenry

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vladimir Matveev · Accepted Answer

这里有一个可运行的版本：

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来表示不存在。 Option::take用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