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

Question

我有一个 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_by 或 Iterator::last 之类的东西，我不关心中间 Snapshots，生成那些未使用的值所产生的成本是一个巨大的性能损失。

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

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

的实例更长寿

Answer 1

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

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.

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

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

rust

iterator

traits

lazy-evaluation

iterator-traits