当某些值被忽略时,如何避免在我的迭代器实现中进行不必要的昂贵操作?

How can I avoid unnecessary expensive operations in my iterator implementation when some values are ignored?

我有一个 Iterator 实现,如下所示:

struct MyType {
    // stuff
}

struct Snapshot {
    // stuff
}

impl MyType {
    pub fn iter(&mut self) -> MyIterator {
        MyIterator {
            foo: self
        }
    }
}

struct MyIterator<'a> {
    foo: &'a mut MyType
}

impl<'a> Iterator for MyIterator<'a> {
    type Item = Snapshot;

    fn next(&mut self) -> Option<Self::Item> {
        if self.cheap_condition() {
           self.cheap_mutation();  // Inexpensive
           let s: Snapshot = self.snapshot();  // Expensive copying
           Some(s)
        } else {
           None
        }
    }
}

如果我想使用生成的每个 Snapshot 实例,这很好用,但是如果我想使用 Iterator::step_byIterator::last 之类的东西,我不关心中间 Snapshots,生成那些未使用的值所产生的成本是一个巨大的性能损失。

可以 覆盖 Iterator 的每一个方法,这样昂贵的操作只在必要时发生,但我觉得必须有一个更简单和更惯用的方法这样做的方法,或者如果 Iterator::next 没有被再次调用,则延迟生成与 Item 的中间类型的迭代对应的 Snapshot 的方法。

我不想 return 引用 MyType,因为我希望我 生成的 Snapshot 具有独立的生命周期,例如,使 Iterator::collect() 的结果比 MyType.

的实例更长寿

您不必重写每个 Iterator 方法。唯一相关的是 nthlastcountstep_byskip。所有其他方法都需要以某种方式检查 Self::Item,因此您无法避免为它们生成 Snapshot。幸运的是 step_byskip 在内部使用 nth,所以这实际上只剩下我们必须覆盖的 nthcountlast

use core::marker::PhantomData;

struct Snapshot;

struct MyType<'a> {
    item: PhantomData<&'a ()>,
}

impl<'a> MyType<'a> {
    fn cheap_condition(&self) -> bool {
        todo!()
    }
    fn cheap_mutation(&mut self) {
        todo!()
    }
    fn snapshot(&self) -> Snapshot {
        Snapshot
    }
}

impl<'a> Iterator for MyType<'a> {
    type Item = Snapshot;

    fn next(&mut self) -> Option<Self::Item> {
        if self.cheap_condition() {
            self.cheap_mutation(); // Inexpensive
            Some(self.snapshot()) // Expensive
        } else {
            None
        }
    }

    // also covers skip & step_by methods
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        for _ in 0..n {
            if self.cheap_condition() {
                self.cheap_mutation();
            } else {
                return None;
            }
        }
        self.next()
    }

    fn count(mut self) -> usize
    where
        Self: Sized,
    {
        let mut count: usize = 0;
        while self.cheap_condition() {
            self.cheap_mutation();
            count += 1;
        }
        count
    }

    fn last(mut self) -> Option<Self::Item>
    where
        Self: Sized,
    {
        while self.cheap_condition() {
            self.cheap_mutation();
            if !self.cheap_condition() {
                return Some(self.snapshot());
            }
        }
        None
    }
}

playground

如果你想通过检查谓词 MyType<'a> 而不是 Snapshot 来使其他 Iterator 方法像 filter 惰性,你必须定义你自己的 Iterator-like 特性,因为所有其他方法仅适用于 Self::Item.