如何组成可变迭代器？ [英] How to compose mutable Iterators?
问题描述
编者注：此代码示例来自1.0之前的Rust版本，并且在语法上不是有效的Rust 1.0代码。此代码的更新版本会产生不同的错误，但答案仍包含有价值的信息。
我想创建一个生成素数流的迭代器。我的一般思维过程是用连续的过滤器包装一个迭代器，例如你从
开始 让mut n =（2 .. N）
然后对于每个素数，你改变迭代器并添加一个过滤器
让p1 = n.next（）
n = n.filter（|& x | x％ p1！= 0）
让p2 = n.next（）
n = n.filter（|& x | x％p2！= 0）
我正在尝试使用以下代码，但我似乎无法让它工作
struct Primes {
base：Iterator< Item = u64>，
}
impl<'a> ; Primes的迭代器<'a> {
type Item = u64;
fn next（& mut self） - >选项< U64> {
let p = self.base.next（）;
匹配p {
Some（n）=> {
let prime = n.clone（）;
let step = self.base.filter（move |& ;:& amp; x | {x％prime！= 0}）;
self.base =& step as& Iterator< Item = u64> ;;
一些（n）
}，
_ =>无
}
}
}
我玩过各种变化这个，但我似乎无法让生活和类型相匹配。现在编译器告诉我
- 我不能改变self.base
- 变量素数不够长
这是我得到的错误
< pre class =lang-none prettyprint-override>
solution.rs:16:17:16:26错误：无法借用不可变借用内容`* self.base`作为可变
解决方案。 rs：16让p = self.base.next（）;
^ ~~~~~~~~
solution.rs:20:28:20:37错误：无法借用不可变借用内容`* self.base`作为可变
解决方案.rs ：20 let step = self.base.filter（move |& ;:& amp; x | {x％prime！= 0}）;
^ ~~~~~~~~
solution.rs:21:30:21:34错误：`step`活不够久
solution.rs:21 self.base =& step as& Iterator< Item = u64> ;;
^ ~~~
solution.rs:15:39:26:6注意：引用必须在15:38块上定义的生命周期'a有效...
solution.rs:15 fn next（& mut self） - >选项< U64> {
solution.rs:16让p = self.base.next（）;
solution.rs:17匹配p {
solution.rs:18 Some（n）=> {
solution.rs:19 let prime = n.clone（）;
solution.rs:20 let step = self.base.filter（move |& ;:& amp; x | {x％prime！= 0}）;
...
solution.rs:20:71:23:14注意：...但借用的值仅对于在20:70
解决方案的语句1之后的块后缀有效。 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一些（n）
solution.rs:23}，
错误：由于之前的3个错误而中止
为什么Rust不允许我这样做？
这是一个工作版本：
struct Primes<'a> {
base：选项< Box< Iterator< Item = u64> +'a>>，
}
impl<'a> Primes的迭代器<'a> {
type Item = u64;
fn next（& mut self） - >选项< 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>素数及LT;一> {
＃[inline]
pub fn new< I：Iterator< Item = u64> +'a>（r：I） - >素数及LT;一> {
Primes {
base：Some（Box :: new（r）），
}
}
}
fn main（ ）{
for p in Primes :: new（2 ..）。take（32）{
print！（{}，p）;
}
println！（）;
}
我正在使用 Box< Iterator> 特质对象。拳击是不可避免的，因为内部迭代器必须存储在 next（）调用之间，并且无处可存储参考特征对象。
我使内部迭代器成为选项。这是必要的，因为您需要将其替换为消耗它的值，因此内部迭代器可能会在短时间内从结构中缺失。 Rust模型缺少选项。 Option :: take 用无替换它所调用的值，并返回那里的任何内容。这在对非可复制对象进行混洗时非常有用。
但是，请注意，此筛选实现将是内存和计算效率低下 - 对于每个素数，您都是创建一个额外的迭代器层，它占用堆空间。调用 next（）时堆栈的深度也会随着素数的增加呈线性增长，因此在足够大的数字上会出现堆栈溢出：
fn main（）{
println！（{}，Primes :: new（2 ..）。nth（10000）。解开（））;
}
运行它：
< pre class =lang-none prettyprint-override>
％。/ test1
thread'< main>'溢出其堆栈
zsh：非法硬件指令（核心倾销）./ test1
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.
I would like to make an iterator that generates a stream of prime numbers. My general thought process was to wrap an iterator with successive filters so for example you start with
let mut n = (2..N)
Then for each prime number you mutate the iterator and add on a filter
let p1 = n.next()
n = n.filter(|&x| x%p1 !=0)
let p2 = n.next()
n = n.filter(|&x| x%p2 !=0)
I am trying to use the following code, but I can not seem to get it to work
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
}
}
}
I have toyed with variations of this, but I can't seem to get lifetimes and types to match up. Right now the compiler is telling me
- I can't mutate self.base
- the variable prime doesn't live long enough
Here is the error I am getting
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
Why won't Rust let me do this?
Here is a working version:
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!("");
}
I'm using a Box<Iterator> trait object. Boxing is unavoidable because the internal iterator must be stored somewhere between next() calls, and there is nowhere you can store reference trait objects.
I made the internal iterator an Option. This is necessary because you need to replace it with a value which consumes it, so it is possible that the internal iterator may be "absent" from the structure for a short time. Rust models absence with Option. Option::take replaces the value it is called on with None and returns whatever was there. This is useful when shuffling non-copyable objects around.
Note, however, that this sieve implementation is going to be both memory and computationally inefficient - for each prime you're creating an additional layer of iterators which takes heap space. Also the depth of stack when calling next() grows linearly with the number of primes, so you will get a stack overflow on a sufficiently large number:
fn main() {
println!("{}", Primes::new(2..).nth(10000).unwrap());
}
Running it:
% ./test1
thread '<main>' has overflowed its stack
zsh: illegal hardware instruction (core dumped) ./test1
这篇关于如何组成可变迭代器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
