Rust 自定义迭代器

在迭代器一页，你用的都是标准库提供的迭代器：vec.iter()、.map()、.filter()、.sum()。其实你也可以写自己的迭代器。倒计时器、斐波那契数列、报告的每一页、自定义文件格式的每一行……任何能一次交出一个值的东西，都可以做成迭代器。

好消息是：你只需要写一个方法，也就是 next。之后 Rust 会免费送你所有的适配器：map、filter、take、sum、zip，还有几十个别的方法。可以把它想象成一台取号机：你只负责做“打印下一张号码”的那部分，排队、显示屏、“请某号到窗口”的提示牌，全都自动就能用。

第一个迭代器：倒计时

要让一个类型成为迭代器，就为它实现 Iterator trait。它需要两样东西：

• type Item：迭代器交出的值是什么类型（关联类型的更多内容见高级 trait）。
• fn next(&mut self) -> Option<Self::Item>：有下一个值时返回 Some(value)，没有了就返回 None。

struct Countdown {
    current: u32,
}

impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None // 结束了
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}

fn main() {
    let mut countdown = Countdown::new(3);

    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());
    println!("{:?}", countdown.next());

    for n in Countdown::new(3) {
        println!("{}...", n);
    }
    println!("发射！");
}

输出：

Some(3)
Some(2)
Some(1)
None
None
3...
2...
1...
发射！

▶ 动手试一试

有几点值得注意：

• next 接收 &mut self，因为它会改变迭代器。结构体记着自己走到了哪里（current），每次调用都会往前走一步。所以 countdown 必须用 let mut 声明。
• 返回 None 的意思是“我结束了”。for 循环会一遍又一遍地调用 next，遇到第一个 None 就停下。
• 我们的倒计时结束后会一直返回 None。这样做很友好，但 trait 并没有强制要求：有些迭代器可能会重新开始。如果你需要这个保证，可以对任何迭代器调用 .fuse()。

永不结束的迭代器：斐波那契数列

迭代器不一定要结束。斐波那契数列（0, 1, 1, 2, 3, 5, 8, …）会一直延续下去：每个数都是前两个数之和。迭代器只需要记住最后两个数：

struct Fibonacci {
    current: u64,
    next: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { current: 0, next: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<u64> {
        let value = self.current;
        // checked_add 在溢出时返回 None，`?` 会把这个 None 传出去，
        // 所以数字太大时迭代器会结束，而不是崩溃。
        let new_next = self.current.checked_add(self.next)?;
        self.current = self.next;
        self.next = new_next;
        Some(value)
    }
}

fn main() {
    let first_ten: Vec<u64> = Fibonacci::new().take(10).collect();
    println!("{:?}", first_ten);
}

输出：

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

▶ 动手试一试

关键在于 .take(10)。没有它，collect() 就会试图收集整个数列。遇到永不结束的迭代器，一定要用 take、take_while 或 find 之类的方法给它设个限。

所有适配器，免费奉送

最精彩的部分来了。Iterator trait 大约有 75 个方法，除了 next 之外，其他方法都有基于 next 的默认实现。所以只要你写好了 next，你的类型就能用上所有这些方法：

struct Countdown {
    current: u32,
}

impl Countdown {
    fn new(from: u32) -> Self {
        Countdown { current: from }
    }
}

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.current == 0 {
            None
        } else {
            let value = self.current;
            self.current -= 1;
            Some(value)
        }
    }
}

fn main() {
    let total: u32 = Countdown::new(5).sum();
    println!("总和：{}", total);

    let evens: Vec<u32> = Countdown::new(10).filter(|n| n % 2 == 0).collect();
    println!("偶数：{:?}", evens);

    let labels: Vec<String> = Countdown::new(3).map(|n| format!("T-{}", n)).collect();
    println!("标签：{:?}", labels);

    let multiple = Countdown::new(100).find(|n| n % 7 == 0);
    println!("找到的第一个 7 的倍数：{:?}", multiple);

    let pairs: Vec<(u32, char)> = Countdown::new(3).zip(['a', 'b', 'c']).collect();
    println!("zip 的结果：{:?}", pairs);
}

输出：

总和：15
偶数：[10, 8, 6, 4, 2]
标签：["T-3", "T-2", "T-1"]
找到的第一个 7 的倍数：Some(98)
zip 的结果：[(3, 'a'), (2, 'b'), (1, 'c')]

▶ 动手试一试

这个例子很好地说明了 Rust 的 trait 为什么这么好用：投入一个小小的方法，换回一整箱工具。

迭代器是惰性的

像 map 和 take 这样的适配器自己什么都不做，它们只是搭好一份“计划”。只有当某个东西消费（consume）这个迭代器时，比如 for 循环、collect、sum 等，工作才会真正开始。我们用一个每次调用 next 都会打印的迭代器来验证一下：

struct Noisy {
    n: u32,
}

impl Iterator for Noisy {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        self.n += 1;
        println!("  调用了 next()，交出 {}", self.n);
        Some(self.n)
    }
}

fn main() {
    println!("正在搭建调用链……");
    let chain = Noisy { n: 0 }.map(|x| x * 10).take(3);
    println!("到现在还什么都没运行。开始消费：");

    for value in chain {
        println!("拿到 {}", value);
    }
    println!("完成");
}

输出：

正在搭建调用链……
到现在还什么都没运行。开始消费：
  调用了 next()，交出 1
拿到 10
  调用了 next()，交出 2
拿到 20
  调用了 next()，交出 3
拿到 30
完成

▶ 动手试一试

这里有两点收获。第一，搭建调用链时什么都没打印，next() 一次都没被调用。第二，值是一个一个流过去的：一次 next、一次 map、一次“拿到”，然后才轮到下一个值。中间并没有藏着什么列表。还有，Noisy 永远不会结束，程序却正常结束了：拿到三个元素之后，take(3) 就不再继续要了。

让你的集合能用在 for 循环里

到目前为止，我们的结构体本身就是迭代器。但更常见的情况是，你有一个集合（一个装着很多元素的结构体），希望别人能像遍历 Vec 那样遍历它。这时你要实现的是 IntoIterator。for 循环在背后用的就是这个 trait：for x in thing 实际上调用的是 thing.into_iter()。

集合通常提供三种遍历方式，在你自己的类型上看一遍会更清楚：

你写的代码	背后的方法	每个元素是	循环之后的集合
for s in &playlist	playlist.iter()	&String（只读）	仍然可用
for s in &mut playlist	playlist.iter_mut()	&mut String（可修改）	仍然可用
for s in playlist	playlist.into_iter()	String（拥有所有权）	被移动，没了

下面这个 Playlist（播放列表）三种方式都支持。我们的结构体把歌曲存放在一个 Vec 里，所以可以直接交出 Vec 自己的迭代器，不用另写新的。歌名保留英文，因为程序要用 s.len() 比较长度，还要转换成大写：

struct Playlist {
    songs: Vec<String>,
}

impl Playlist {
    fn iter(&self) -> std::slice::Iter<'_, String> {
        self.songs.iter()
    }

    fn iter_mut(&mut self) -> std::slice::IterMut<'_, String> {
        self.songs.iter_mut()
    }
}

// 让 `for song in &playlist` 能用
impl<'a> IntoIterator for &'a Playlist {
    type Item = &'a String;
    type IntoIter = std::slice::Iter<'a, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

// 让 `for song in &mut playlist` 能用
impl<'a> IntoIterator for &'a mut Playlist {
    type Item = &'a mut String;
    type IntoIter = std::slice::IterMut<'a, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

// 让 `for song in playlist` 能用（会把播放列表用掉）
impl IntoIterator for Playlist {
    type Item = String;
    type IntoIter = std::vec::IntoIter<String>;

    fn into_iter(self) -> Self::IntoIter {
        self.songs.into_iter()
    }
}

fn main() {
    let mut playlist = Playlist {
        songs: vec![String::from("intro"), String::from("main theme"), String::from("outro")],
    };

    for song in &playlist {
        println!("读取：{}", song);
    }

    for song in &mut playlist {
        *song = song.to_uppercase();
    }

    println!("最长的歌名：{:?}", playlist.iter().max_by_key(|s| s.len()));

    for song in playlist {
        println!("取走：{}", song);
    }
    // 上一个循环已经移动了 `playlist`，所以这里不能再用它。
}

输出：

读取：intro
读取：main theme
读取：outro
最长的歌名：Some("MAIN THEME")
取走：INTRO
取走：MAIN THEME
取走：OUTRO

▶ 动手试一试

代码行数不少，但每个 impl 的形状都一样：说明 Item 是什么，说明你返回哪种迭代器类型（IntoIter），然后把它返回。'a 是生命周期，它的意思是“借出来的元素和借出来的播放列表活得一样久”。几乎任何包装了 Vec 的集合，都可以照搬这个模式。

倒着走，以及知道长度

还有两个 trait 值得了解。你不会经常用到它们，但 .rev() 和 .len() 这样的适配器要靠它们：

• DoubleEndedIterator 增加了 next_back，从末尾取元素。有了它就能用 .rev()。
• ExactSizeIterator 承诺迭代器确切地知道还剩多少个元素。有了它就能用 .len()。同时你还要在 Iterator 里给出准确的 size_hint。

// 依次交出 low, low+1, ..., high-1（和区间 low..high 一样）
struct Between {
    low: u32,
    high: u32,
}

impl Iterator for Between {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        let value = self.low;
        self.low += 1;
        Some(value)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let left = self.high.saturating_sub(self.low) as usize;
        (left, Some(left))
    }
}

impl DoubleEndedIterator for Between {
    fn next_back(&mut self) -> Option<u32> {
        if self.low >= self.high {
            return None;
        }
        self.high -= 1;
        Some(self.high)
    }
}

impl ExactSizeIterator for Between {}

fn main() {
    let backwards: Vec<u32> = Between { low: 1, high: 6 }.rev().collect();
    println!("{:?}", backwards);

    let mut both_ends = Between { low: 1, high: 6 };
    println!("前端 {:?}，后端 {:?}", both_ends.next(), both_ends.next_back());
    println!("还剩 {} 个", both_ends.len());
}

输出：

[5, 4, 3, 2, 1]
前端 Some(1)，后端 Some(5)
还剩 3 个

▶ 动手试一试

两端相向而行，相遇时迭代器就结束了。impl ExactSizeIterator for Between {} 是空的：len() 用的是你已经写好的 size_hint。

捷径：from_fn 和 successors

对于需要反复使用的迭代器，写一个结构体加一个 impl 是很好的做法。如果只是临时用一下，标准库的 std::iter 里有两个帮手：

• iter::from_fn(closure)：每次需要值时调用你的闭包。闭包返回 Some(value) 或 None，和 next 一样。
• iter::successors(first, closure)：从第一个值开始，闭包根据前一个值算出下一个值。返回 None 就结束。

use std::iter;

fn main() {
    // from_fn：闭包自己保存状态（count）
    let mut count = 3;
    let countdown: Vec<u32> = iter::from_fn(|| {
        if count == 0 {
            None
        } else {
            count -= 1;
            Some(count + 1)
        }
    })
    .collect();
    println!("{:?}", countdown);

    // successors：每个值都由前一个值算出来
    let powers: Vec<u32> = iter::successors(Some(1u32), |&n| n.checked_mul(10)).collect();
    println!("{:?}", powers);

    // 一行写出斐波那契数列：把最后两个数作为一对传下去
    let fib: Vec<u64> = iter::successors(Some((0u64, 1u64)), |&(a, b)| Some((b, a + b)))
        .map(|(a, _)| a)
        .take(10)
        .collect();
    println!("{:?}", fib);
}

输出：

[3, 2, 1]
[1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

▶ 动手试一试

powers 会自己停下来：下一个 10 的幂是 10,000,000,000，u32 装不下，所以 checked_mul 返回 None，迭代器就结束了。一条好用的经验：在单个函数内部用这些捷径；如果别的代码也需要创建这个迭代器，或者它的状态很多，就写一个有名字的结构体。

常见误区

自己调用 next 时忘了加 mut。next 会改变迭代器，所以变量必须是可变的：

let countdown = Countdown { current: 3 };
println!("{:?}", countdown.next());

error[E0596]: cannot borrow `countdown` as mutable, as it is not declared as mutable
  --> src/main.rs:20:22
   |
20 |     println!("{:?}", countdown.next());
   |                      ^^^^^^^^^ cannot borrow as mutable
   |
help: consider changing this to be mutable
   |
19 |     let mut countdown = Countdown { current: 3 };
   |         +++

加上 mut 就好了。（for 循环不需要它：循环会接管迭代器，帮你处理好这件事。）

忘了写 type Item。trait 需要知道你交出的是什么：

error[E0046]: not all trait items implemented, missing: `Item`
 --> src/main.rs:5:1
  |
5 | impl Iterator for Countdown {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing `Item` in implementation
  |
  = help: implement the missing item: `type Item = /* Type */;`

在 impl 里面加上 type Item = u32;（或者你的迭代器交出的其他类型）。

对永不结束的迭代器调用 collect。Fibonacci::new().collect::<Vec<_>>()（不加 take）能顺利编译，但它永远不会以有用的方式结束：它会一直运行到数字溢出为止；如果你的 next 从不返回 None，就会永远运行下去。编译器发现不了这种问题。只要迭代器可能永不结束，消费它之前一定要加上 take、take_while 或 find。

总结

• 用 type Item 和 fn next(&mut self) -> Option<Self::Item> 实现 Iterator，结束时返回 None。
• 有了 next，你就免费得到了 map、filter、take、sum、zip 等几十个方法。
• 迭代器是惰性的：在 for 循环、collect、sum 等消费它之前，什么都不会发生，而且元素是一个一个流过去的。
• 为 &MyType、&mut MyType 和 MyType 实现 IntoIterator，就能支持借用、可变借用和消费三种 for 循环。
• DoubleEndedIterator 让你能用 .rev()；ExactSizeIterator 让你能用 .len()。
• 临时用一下的迭代器，可以用 std::iter::from_fn 或 std::iter::successors。

小测验

小测验

1. 当迭代器没有更多元素时，next 应该返回什么？

0 一个空的 Vec None 应该 panic

2. 只实现了 next 之后，能在你的迭代器上调用 .map() 和 .sum() 吗？

能，它们是基于 next 的默认方法 不能，必须逐个实现 只有同时实现了 IntoIterator 才能

3. 在惰性求值的例子里，next() 第一次被调用是在什么时候？

写下 .map() 的时候 写下 .take(3) 的时候 for 循环开始消费调用链的时候

4. 哪个 impl 让 for song in &playlist 能用？

impl Iterator for Playlist impl<'a> IntoIterator for &'a Playlist impl IntoIterator for Playlist impl DoubleEndedIterator for Playlist

5. 要让 .rev() 能用在你的迭代器上，需要实现哪个 trait？

ExactSizeIterator Clone IntoIterator DoubleEndedIterator

得分: 0 / 5

延伸阅读

• 使用迭代器处理元素序列 — Rust 程序设计语言：Iterator 和 next 是怎样工作的，以及迭代器为什么是惰性的。
• std::iter 模块（英文）：官方的迭代器指南，其中有专门讲实现自己的迭代器和 IntoIterator 的部分。
• Iterator trait — 标准库文档（英文）：写好 next 之后免费得到的所有适配器。
• 迭代器 — 通过例子学 Rust：一个简短的斐波那契迭代器示例，可以运行，也可以动手修改。
• std::iter::successors（英文）：从一个起始值和一条“下一个”规则构建迭代器的文档。