面试题：Rust中复杂自定义迭代器链及Iterator trait的高级应用

Question

编写一个Rust程序，定义两个自定义迭代器结构体`FilteredIterator`和`TransformedIterator`。`FilteredIterator`用于过滤掉不符合某个条件的值，`TransformedIterator`用于对值进行某种转换。然后，通过实现`Iterator` trait，将这两个迭代器链接起来，形成一个迭代器链，使其能依次对一个基础迭代器产生的值进行过滤和转换操作。同时，要考虑如何在迭代器链中高效地处理内存和性能问题，以及如何确保类型的安全性和一致性。

Answer 1

// 定义FilteredIterator结构体
struct FilteredIterator<I, P>
where
    I: Iterator,
    P: FnMut(&<I as Iterator>::Item) -> bool,
{
    iter: I,
    predicate: P,
}

// 为FilteredIterator实现Iterator trait
impl<I, P> Iterator for FilteredIterator<I, P>
where
    I: Iterator,
    P: FnMut(&<I as Iterator>::Item) -> bool,
{
    type Item = <I as Iterator>::Item;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let item = self.iter.next()?;
            if (self.predicate)(&item) {
                return Some(item);
            }
        }
    }
}

// 定义TransformedIterator结构体
struct TransformedIterator<I, F>
where
    I: Iterator,
    F: FnMut(<I as Iterator>::Item) -> <I as Iterator>::Item,
{
    iter: I,
    f: F,
}

// 为TransformedIterator实现Iterator trait
impl<I, F> Iterator for TransformedIterator<I, F>
where
    I: Iterator,
    F: FnMut(<I as Iterator>::Item) -> <I as Iterator>::Item,
{
    type Item = <I as Iterator>::Item;

    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|item| (self.f)(item))
    }
}

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    let iter = numbers.into_iter();

    let filtered_and_transformed_iter = TransformedIterator {
        iter: FilteredIterator {
            iter,
            predicate: |&x| x % 2 == 0,
        },
        f: |x| x * 2,
    };

    for result in filtered_and_transformed_iter {
        println!("{}", result);
    }
}

内存和性能优化

1. 惰性求值：FilteredIterator 和 TransformedIterator 都是惰性的，只有在调用 next 方法时才会处理下一个元素，避免了不必要的计算。
2. 链式调用：通过结构体嵌套，在迭代器链中减少了中间数据结构的创建，从而减少了内存分配和拷贝。

类型安全性和一致性

1. 泛型约束：在定义 FilteredIterator 和 TransformedIterator 时，通过泛型约束确保了传入的迭代器和闭包的类型一致性。例如，FilteredIterator 要求传入的闭包 P 能够接受 I::Item 类型的引用并返回 bool，TransformedIterator 要求传入的闭包 F 能够接受并返回 I::Item 类型的值。
2. trait 限定：通过为结构体实现 Iterator trait，明确了迭代器的行为，进一步保证了类型安全性。在实现 next 方法时，返回值类型必须与 Self::Item 一致，这由 Rust 的类型系统强制检查。