如何在Rust中实现多值迭代器模式？

Question

我有一个迭代器类型的对象，它可以在每次调用时返回零个、一个或多个项。我想实现一个标准的Iter接口，即next返回Option<Self::Item>，这样它就可以被逐个消费了。

在Clojure中，我可能会用mapcat (“映射和连接”)来做这件事。

我目前的解决方案(感谢@Ryan)使用了flat_map，但仍然需要大量的分配：

// Desired input:
// A stateful object that implements an iterator which returns a number of results each time.
// The real code is a bit more complicated, this is the minimal example.
struct MyThing {
    counter: i32,
}

impl Iterator for MyThing {
    type Item = Vec<String>;

    fn next(&mut self) -> Option<Vec<String>> {
        self.counter += 1;
        if self.counter == 4 {
            self.counter = 1;
        }

        match self.counter {
            1 => Some(vec!["One".to_string()]),
            2 => Some(vec!["One".to_string(), "Two".to_string()]),
            3 => Some(vec![
                "One".to_string(),
                "Two".to_string(),
                "Three".to_string(),
            ]),
            _ => Some(vec![]),
        }
    }
}

fn main() {
    let things = MyThing { counter: 0 };

    // Missing piece, though the following line does the job:
    let flattened = things.flat_map(|x| x);

    // However this requires a heap allocation at each loop.

    // Desired output: I can iterate, item by item.
    for item in flattened {
        println!("{:?}", item);
    }
}

考虑到我看到的这些创新的东西，我想知道是否有一种更惯用、更便宜的方式来实现这种模式。

Answer 1

如果您知道如何以编程方式生成“内部”值，请将Vec<String>替换为您定义的实现Iterator<Item = String>的结构。(从技术上讲，只有IntoIterator是必需的，但Iterator就足够了。)

struct Inner {
    index: usize,
    stop: usize,
}

impl Inner {
    fn new(n: usize) -> Self {
        Inner { index: 0, stop: n }
    }
}

impl Iterator for Inner {
    type Item = String;

    fn next(&mut self) -> Option<String> {
        static WORDS: [&str; 3] = ["One", "Two", "Three"];
        let result = if self.index < self.stop {
            WORDS.get(self.index).map(|r| r.to_string())
        } else {
            None
        };
        self.index += 1;
        result
    }
}

因为Inner实现了Iterator<Item = String>，所以可以像Vec<String>一样遍历它。但是Inner不必预先分配Vec并一个接一个地使用项目；它可以按需懒惰地创建每个String。

“外部”迭代器只是一个实现Iterator<Item = Inner>的结构，同样懒惰地构造每个Inner：

struct Outer {
    counter: i32,
}

impl Iterator for Outer {
    type Item = Inner;

    fn next(&mut self) -> Option<Inner> {
        self.counter = 1 + self.counter % 3;

        Some(Inner::new(self.counter as usize))
    }
}

正如您所知道的，Iterator::flat_map展平了嵌套结构，因此类似于下面的works

let things = Outer { counter: 0 };

for item in things.flat_map(|x| x).take(100) {
    println!("{:?}", item);
}

在实际的代码中，Inner和Outer在大多数情况下可能与这个示例有很大的不同。例如，在不执行与分配Vec相同的操作的情况下编写Inner不一定是可能的。因此，这些迭代器的精确形状和语义取决于有关用例的具体信息。

以上假设Inner在某种程度上是有用的，或者更容易独立实现。您可以很容易地编写一个结构来迭代序列，而不需要进行扁平化，但是您还必须将内部迭代器状态( index字段)放入Outer中

struct Outer {
    index: usize,
    counter: i32,
}

impl Iterator for Outer {
    type Item = String;

    fn next(&mut self) -> Option<String> {
        static WORDS: [&str; 3] = ["One", "Two", "Three"];
        let result = WORDS.get(self.index).map(|r| r.to_string());
        self.index += 1;
        if self.index >= self.counter as usize {
            self.counter = 1 + self.counter % 3;
            self.index = 0;
        };
        result
    }
}

fn main() {
    let things = Outer { counter: 1, index: 0 };

    for item in things.take(100) {
        println!("{:?}", item);
    }
}