Rust 的迭代器 I

什么是迭代器？它是函数式编程语言所具备的一种特性。当你有一个集合（我们通常意义上所说的能装多个性质相似的元素的容器），并且想要对其中的元素进行某些操作时，那你最佳的选择恐怕就是迭代器。这里的操作并不仅限于“遍历”和“访问”，迭代器所能施展的空间远不止于此。

Rust 为迭代器定义了几个核心特征以及一系列的方法，它们共同提升了我们对迭代器的实际使用体验。

迭代器的核心特征

core::iter 中的特征定义了存在哪些类型的迭代器以及你可以对它们执行哪些操作。

Iterator 特征

按照文档的说法，Iterator 是整个 core::iter 模块的核心与灵魂（the heart and soul）。它是这样的：

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

Iterator 有一个方法 next，表示获取要迭代的下一个 Item 类型的元素。实际工作时，迭代器类型会不断调用这个方法：只要还有元素，调用 next 就会返回 Some(Item)；当所有元素都被耗尽后，它将返回 None 以表示迭代结束。个别迭代器可能会选择恢复迭代，因此再次调用 next 可能会也可能不会在某个时刻重新开始返回 Some(Item)。

实现 Iterator

创建自定义类型的迭代器涉及两个步骤：

1. 创建一个用于保存迭代器状态的结构体，然后
2. 为该结构体实现 Iterator。

这就是 core::iter 模块中有这么多结构体的原因：每个迭代器和迭代器适配器都有对应的结构体。

让我们创建一个名为 Counter 的迭代器，它从 1 计数到 5：

// 首先定义结构体

/// 一个从一计数到五的迭代器
struct Counter {
    count: usize,
}

// 我们希望计数从 1 开始，所以添加一个 new() 方法来辅助（并不是严格必需的）
// 注意我们将 `count` 从零开始，
// 原因将在下面的 `next()` 实现中说明
impl Counter {
    fn new() -> Counter {
        Counter { count: 0 }
    }
}

// 然后，为我们的 `Counter` 实现 `Iterator`

impl Iterator for Counter {
    // 我们将使用 usize 进行计数
    type Item = usize;

    // next() 是唯一必需的方法
    fn next(&mut self) -> Option<Self::Item> {
        // 增加计数
        // 这就是我们从零开始的原因
        self.count += 1;

        // 检查是否已经完成计数
        if self.count < 6 {
            Some(self.count)
        } else {
            None
        }
    }
}

// 现在我们可以使用它了

let mut counter = Counter::new();

assert_eq!(counter.next(), Some(1));
assert_eq!(counter.next(), Some(2));
assert_eq!(counter.next(), Some(3));
assert_eq!(counter.next(), Some(4));
assert_eq!(counter.next(), Some(5));
assert_eq!(counter.next(), None);

像这样反复调用 next 会很繁琐。Rust 有一种结构可以调用迭代器上的 next，直到它返回 None。我们接下来会介绍它。

实际上，完整的 Iterator 定义中还包含许多其他方法（nth 和 fold 等），但它们都提供了默认实现，并且都构建在 next 之上，因此你完全可以不手动实现它们。如果迭代器可以在不调用 next 的情况下更高效地计算出结果，也可以为 nth 和 fold 等方法编写自定义实现。

IntoIterator 与 for 循环

core::iter 中还有一个用于将某物转换为迭代器的特征：IntoIterator。该特征有一个方法 into_iter，它将实现了 IntoIterator 的实例转换为迭代器。

或者说，IntoIterator 的职责就是“变成迭代器”。

pub trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;

    // Required method
    fn into_iter(self) -> Self::IntoIter;
}

让我们从一个基本的 for 循环示例开始：

let values = vec![1, 2, 3, 4, 5];

for x in values {
    print!("{x}"); // 12345
}

注意到：我们从未在 values 上调用任何东西来生成迭代器。那这个 for 循环是如何迭代元素的？答案就藏在背后的 IntoIterator 里。

换言之，这个 for 循环是 Rust 提供的语法糖。在编译器中，上面的代码会被转换为：

let values = vec![1, 2, 3, 4, 5];
{
    let result = match values.into_iter() {
        mut iter => loop {
            let next;
            match iter.next() {
                Some(val) => next = val,
                None => break,
            };
            let x = next;
            let () = { print!("{x}"); };
        },
    };
    result
}

首先，程序对值调用 into_iter，然后对返回的迭代器 iter 反复调用 next，直到遇到 None。此时程序跳出循环，迭代结束。

实际上就多了一步：将要迭代的集合类型先用 IntoIterator 转成对应的迭代器，后面的都是不断对迭代器调用 next 的老一套东西。

标准库中还包含一个有趣的 IntoIterator 实现：

impl<I: Iterator> IntoIterator for I

由于这个实现是泛型的，所以可以说是只要实现了 Iterator，就会自动实现 IntoIterator。不难想象，我们只需要在 IntoIterator 的实现里直接返回自身就行了：

impl<I: Iterator> IntoIterator for I {
    type Item = I::Item;
    type IntoIter = I;

    fn into_iter(self) -> I {
        self 
        // into_iter 就是为了让实现它的类型转为迭代器
        // 现在 I 已经是迭代器了，直接返回自身就 OK
    }
}

同时，这意味着两件事：

1. 如果你正在编写一个迭代器，你可以直接在 for 循环中使用它。因为 Rust 将语法脱糖后，由于迭代器会自动实现 IntoIterator，因此对迭代器调用 into_iter 也是合法的。
2. 如果你正在创建一个集合，为其实现 IntoIterator 将允许你的集合在 for 循环中使用。就比如示例中的 Vec<T>，你如果查阅文档会发现它并没有实现 Iterator，而是只有 IntoIterator 的实现，并且 Vec<T> 会被转为一个藏匿更深的迭代器类型¹。对于其它常见集合（HashSet<T>、BTreeMap<K,V> 等）也是如此。

按引用迭代

由于 into_iter() 按值获取 self，因此使用 for 循环遍历集合会消耗掉该集合。但是多数情况下，你可能希望在不消耗集合的情况下对其进行迭代。

所以许多集合提供了返回引用迭代器的方法，通常分别称为 iter() 和 iter_mut()：

let mut values = vec![41];
for x in values.iter_mut() {
    *x += 1;
}
for x in values.iter() {
    assert_eq!(*x, 42);
}
assert_eq!(values.len(), 1);
// `values` 所有权没被消耗，仍归此函数所有

如果集合类型 C 提供了 iter()，它通常也会为 &C 实现 IntoIterator，其实现仅调用 iter()。

同样地，提供 iter_mut() 的集合 C 通常会借助 iter_mut() 来为 &mut C 实现 IntoIterator。这提供了一种便捷的简写形式：

let mut values = vec![41];
for x in &mut values {
    // 等同于 `values.iter_mut()`
    *x += 1;
}
for x in &values {
    // 等同于 `values.iter()`
    assert_eq!(*x, 42);
}
assert_eq!(values.len(), 1);

虽然许多集合提供 iter()，但并非所有集合都提供 iter_mut()。

例如，如果键的哈希值发生变化，修改 HashSet<T> 的键可能会使集合处于不一致状态，因此该集合只提供 iter()。

FromIterator 特征

IntoIterator 的职责是把某类型变成迭代器，那么反过来呢？答案是 FromIterator，它负责把迭代器转为某种集合类型。

pub trait FromIterator<A>: Sized {
    // Required method
    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self;
}

后面会介绍 Iterator::collect 方法，它将一个迭代器转为指定的集合类型。如果你想把一个迭代器的所有元素组成一个集合，那么应该选择 collect；但你如果想指定转换为何种类型，FromIterator 可能在易读性上更好。

// 生成一个迭代器
let five_fives = std::iter::repeat(5).take(5);

// 指明要将迭代器转换为 `Vec<_>`
let v = Vec::from_iter(five_fives);
// 等价于
let v: Vec<_> = five_fives.collect();

assert_eq!(v, vec![5, 5, 5, 5, 5]);

参考资料

• core::iter 官方文档