内部迭代器表现得很好的例子（以及创建此存储库的原始原因）是遍历树。让我们以一个非常简单的整数树为例

struct Tree(i32, Vec<Tree>);

为了能够实现 next()，我们需要存储树中的当前位置。我们可以将此表示为索引列表，每个索引都指示对应级别的子树中的子节点。

struct TreeIter {
    tree: Tree,
    position: Vec<usize>,
}

Iterator 实现将返回当前位置的值，并前进到子树或下一个兄弟节点，然后向上移动。

// returns None if walking down the tree went out of bounds in child vector in
// some level
fn find_subtree<'a>(tree: &'a Tree, pos: &[usize]) -> Option<&'a Tree> {
    match pos {
        [] => tree,
        [idx, rest @ ..] => {
            let child = &tree.1.get(*idx)?;
            find_subtree(child, rest)
        }
    }
}

impl Iterator for TreeIter {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        loop {
            match self.position.as_slice() {
                [0, rest @ ..] => {
                    let current_tree = find_subtree(&self.tree, &self.position);
                    if let Some(tree) = current_tree {
                        let result = Some(tree.0);
                        if !tree.1.is_empty() {
                            // node has children, move position at first child
                            // of current position
                            self.position.push(0);
                        } else {
                            // node has no children, move position to next
                            // sibling
                            *self.position.last_mut().unwrap() += 1;
                        }
                        return Some(result);
                    } else {
                        // current position is out of bounds - move up by one
                        // and advance to next sibling, then loop over to try
                        // again
                        self.position.pop();
                        *self.position.last_mut().unwrap() += 1;
                    }
                }
                [1] => {
                    return None;
                }
                _ => unreachable!(),
            }
        }
    }
}

哇，这相当棘手，涉及所有这些索引操作。

让我们尝试使用 InternalIterator 做同样的事情。驱动 trait 的核心方法是 try_for_each。

use std::ops::ControlFlow;

struct TreeInternalIter {
    tree: Tree,
}

// we need a helper because we need to use `f` multiple times, but an arbitrary
// FnMut cannot be copied or reborrowed
fn iter_helper<T>(tree: Tree, f: &mut impl FnMut(i32) -> ControlFlow<T>) -> ControlFlow<T> {
    f(tree.0)?;
    for child in tree.1 {
        iter_helper(child, f)?;
    }
    ControlFlow::Continue(())
}

impl InternalIterator for TreeInternalIter {
    type Item = i32;

    fn try_for_each<T, F>(self, mut f: F) -> ControlFlow<T>
    where
        F: FnMut(i32) -> ControlFlow<T>,
    {
        iter_helper(self.tree, &mut f)
    }
}

这要简单得多，错误可能性更小，甚至不需要任何动态内存分配！多亏了 std::ops::ControlFlow 和 ? 操作符，实现起来非常容易。

它们都允许构建复杂的迭代器管道。

let tree = Tree(4, vec![
    Tree(1, vec![]),
    Tree(3, vec![
        Tree(5, vec![]),
    ]),
    Tree(2, vec![]),
]);

let iterator_result = tree
    .into_iter()
    .map(|x| x * 2)
    .filter(|&x| x > 5)
    .flat_map(|x| [x, x * 10])
    .collect::<Vec<_>>();

assert_eq!(iterator_result, vec![8, 80, 6, 60, 10, 100]);

let internal_iterator_result = tree
    .into_internal_iter()
    .map(|x| x * 2)
    .filter(|&x| x > 5)
    .flat_map(|x| [x, x * 10])
    .collect::<Vec<_>>();

assert_eq!(internal_iterator_result, vec![8, 80, 6, 60, 10, 100]);

内部迭代器不如外部迭代器表达性强——它们不能与 for 循环或需要外部迭代的某些适配器一起使用。然而，这种表达性的损失并不大，而且根据您的用例，可能是一个值得付出的小代价，以换取远更简单的迭代器实现。

限制

这个 crate 旨在提供与 std 中非常相似的简单 API，这意味着一些可以通过内部迭代提供的复杂功能在这个库中不可用。

关于缺失的 Iterator 方法

并非所有来自 std::iter::Iterator 的方法等效都实现了。其中一些是不可能的（zip 就是其中之一），而大多数其他方法尚未实现，只是因为我个人还没有需要它们。

如果您认为这个库很有价值，但缺少您需要的方法，请随时提出问题或提交拉取请求。

许可证

根据您的选择，许可如下

• Apache 许可证，版本 2.0 (LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

。

贡献

除非您明确表示，否则根据 Apache-2.0 许可证定义的，您有意提交给工作的工作的所有贡献，应按照上述方式双重许可，不附加任何其他条款或条件。