第 15 章 迭代器(1)
第 15 章 迭代器
漫长的一天结束了。
——Phil
迭代器 是一个值，它可以生成一系列值，通常用来执行循环操作。Rust 的标准库不仅提供了用于遍历向量、字符串、哈希表和其他集合的迭代器，还提供了“从输入流中产生文本行”“从网络服务器中产生新的入站连接”“从通信通道中其他线程接收的值”等迭代器。当然，你也可以出于自己的目的实现迭代器。Rust 的 for 循环为使用迭代器提供了一种自然的语法，但迭代器本身也提供了一组丰富的方法，比如映射（ map）、过滤（ filter）、连接（ join）、收集（ collect）等。
Rust 的各种迭代器灵活、富有表现力而且高效。考虑以下函数，它会返回前 n 个正整数之和（通常称为 第 n 个三角形数）：
fn triangle(n: i32) -> i32 {
let mut sum = 0;
for i in 1..=n {
sum += i;
}
sum
}
表达式 1..=n 是一个 RangeInclusive<i32> 型的值。而 RangeInclusive<i32> 是一个迭代器，可以生成其起始值到结束值（包括两者）之间的整数，因此你可以将它用作 for 循环的操作数来对从 1 到 n 的值求和。
但是迭代器还有一个 fold 方法，可以实现完全一样的效果：
fn triangle(n: i32) -> i32 {
(1..=n).fold(0, |sum, item| sum + item)
}
开始运行时以 0 作为总和， fold 会获取 1..=n 生成的每个值，并以总和（ sum）跟当前值（ item）为参数调用闭包 |sum, item| sum + item。闭包的返回值会作为新的总和。它返回的最后一个值就是 fold 自身要返回的值——在这个例子中，也就是整个序列的总和。如果你用惯了 for 循环和 while 循环，这种写法可能看起来很奇怪，但一旦习惯了 fold，你就会发现 fold 的表达方式更加清晰和简洁。
这就是函数式编程语言的标准风格，非常注重表达能力。Rust 的迭代器都经过了精心设计，以确保编译器可以把它们翻译成优秀的机器码。例如前面展示的第二个定义，在发行版中，Rust 会理解 fold 的定义并将其内联到 triangle 中。接下来是将闭包 |sum, item| sum + item 内联到 triangle 中。最后，Rust 会检查合并后的代码并意识到有一种更简单的方法可以对从 1 到 n 的数值求和：其总和总会等于 n * (n+1) / 2。于是 Rust 将 triangle 的整个函数体，包括循环、闭包和所有内容，翻译成了单个乘法指令和几个算术运算。
虽然这个例子只涉及简单的算术运算，但迭代器在重度使用时也同样表现出色。它们是 Rust 提供的另一种灵活抽象，在典型应用中几乎不会产生额外开销。
在本章中，我们将解释以下核心知识点。
Iterator特型和IntoIterator特型，两者是 Rust 迭代器的基础。- 一个典型的迭代器流水线通常有 3 个阶段：从某种“值源”创建迭代器，通过选择或处理从中流过的值来将一种迭代器适配成另一种迭代器，然后消耗此迭代器生成的值。
- 如何为自己的类型实现迭代器。
迭代器的方法非常多，不过只要你掌握了其基本思想，就可以粗略浏览相应的部分。但迭代器在 Rust 惯用法中非常常见，熟悉它们附带的工具对于掌握这门语言至关重要。
15.1 Iterator 特型与 IntoIterator 特型
迭代器是实现了 std::iter::Iterator 特型的任意值：
trait Iterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
…… // 很多默认方法
}
Item 是迭代器所生成的值的类型。 next 方法要么返回 Some(v)（其中 v 是迭代器的下一个值），要么返回 None（作为序列结束的标志）。这里我们省略了 Iterator 的许多默认方法，本章的其余小节会分别介绍它们。
只要可以用某种自然的方式来迭代某种类型，该类型就可以实现 std::iter::IntoIterator，其 into_iter 方法会接受一个值并返回一个迭代器：
trait IntoIterator where Self::IntoIter: Iterator<Item=Self::Item> {
type Item;
type IntoIter: Iterator;
fn into_iter(self) -> Self::IntoIter;
}
IntoIter 是迭代器本身的类型，而 Item 是它生成的值的类型。任何实现了 IntoIterator 的类型都称为 可迭代者，因为你可以随意迭代它。
Rust 的 for 循环会将所有这些部分很好地结合在一起。要遍历向量的元素，你可以这样写：
println!("There's:");
let v = vec!["antimony", "arsenic", "aluminum", "selenium"];
for element in &v {
println!("{}", element);
}
在幕后，每个 for 循环都只是调用 IntoIterator 和 Iterator 中某些方法的简写形式：
let mut iterator = (&v).into_iter();
while let Some(element) = iterator.next() {
println!("{}", element);
}
for 循环会使用 IntoIterator::into_iter 将其操作数 &v 转换为迭代器，然后重复调用 Iterator::next。每次返回 Some(element) 时， for 循环都会执行其循环体，如果返回 None，则循环结束。
先记住这个例子，下面介绍迭代器的一些术语。
- 正如我们所说， 迭代器 是实现了
Iterator的任意类型。 - 可迭代者 是任何实现了
IntoIterator的类型：你可以通过调用它的into_iter方法来获得一个迭代器。在这里，向量引用&v就是可迭代者。 - 迭代器能 生成 值。
- 迭代器生成的值是 条目。在这里，条目是
"antimony"、"arsenic"等。 - 接收迭代器所生成条目的代码是 消费者。在这里，
for循环体就是消费者。
虽然 for 循环总会在其操作数上调用 into_iter，但你也可以直接把迭代器传给 for 循环，比如，在遍历 Range 时就是这样的。所有迭代器都自动实现了 IntoIterator，并带有一个直接返回迭代器的 into_iter 方法。
如果在返回 None 后再次调用迭代器的 next 方法，则 Iterator 特型没有规定它应该做什么。大多数迭代器只会再次返回 None，但也有例外。（如果这个过程中出了问题，可以参考一下 15.3.7 节中介绍的 fuse 适配器。）
15.2 创建迭代器
虽然 Rust 标准库文档对每个种类的迭代器类型都进行了详细解释，但标准库还是遵循了一些通用的约定，来帮助你定位并找到想要的东西。
15.2.1 iter 方法与 iter_mut 方法
大多数集合类型提供了 iter（迭代器）方法和 iter_mut（可变迭代器）方法，它们会返回该类型的自然迭代器，为每个条目生成共享引用或可变引用。像 &[T] 和 &mut [T] 这样的数组切片也有 iter 方法和 iter_mut 方法。如果你不打算让 for 循环替你跟迭代器打交道， iter 方法和 iter_mut 方法就是获取迭代器最常用的方法：
let v = vec![4, 20, 12, 8, 6];
let mut iterator = v.iter();
assert_eq!(iterator.next(), Some(&4));
assert_eq!(iterator.next(), Some(&20));
assert_eq!(iterator.next(), Some(&12));
assert_eq!(iterator.next(), Some(&8));
assert_eq!(iterator.next(), Some(&6));
assert_eq!(iterator.next(), None);
这个迭代器的条目类型是 &i32：每次调用 next 都会生成对下一个元素的引用，直到抵达向量的末尾。
每种类型都可以自由选用任何符合其设计意图的方式实现 iter 和 iter_mut。 std::path::Path 上的 iter 方法会返回一个迭代器，一次生成一个路径组件：
use std::ffi::OsStr;
use std::path::Path;
let path = Path::new("C:/Users/JimB/Downloads/Fedora.iso");
let mut iterator = path.iter();
assert_eq!(iterator.next(), Some(OsStr::new("C:")));
assert_eq!(iterator.next(), Some(OsStr::new("Users")));
assert_eq!(iterator.next(), Some(OsStr::new("JimB")));
...
这个迭代器的条目类型是 &std::ffi::OsStr，是从操作系统调用所要求的那类字符串借用的切片类型。
如果类型有不止一种常用的遍历方式，该类型通常会为每种遍历方式提供一个专门的方法，因为普通的 iter 方法会产生歧义。例如， &str 字符串切片类型就没有 iter 方法——如果 s 是 &str，则 s.bytes() 会返回一个能生成 s 中每字节的迭代器，而 s.chars() 则会将内容解释为 UTF-8 并生成每个 Unicode 字符。
15.2.2 IntoIterator 的实现
如果一个类型实现了 IntoIterator，你也可以自行调用它的 into_iter 方法，就像 for 循环一样：
// 大家通常会使用HashSet，但它的迭代顺序是不确定的，
// 因此在这个示例中用了BTreeSet，它的演示效果更好些
use std::collections::BTreeSet;
let mut favorites = BTreeSet::new();
favorites.insert("Lucy in the Sky With Diamonds".to_string());
favorites.insert("Liebesträume No. 3".to_string());
let mut it = favorites.into_iter();
assert_eq!(it.next(), Some("Liebesträume No. 3".to_string()));
assert_eq!(it.next(), Some("Lucy in the Sky With Diamonds".to_string()));
assert_eq!(it.next(), None);
大多数集合实际上提供了 IntoIterator 的几种实现，用于共享引用（ &T）、可变引用（ &mut T）和移动（ T）。
- 给定一个集合的 共享引用，
into_iter会返回一个迭代器，该迭代器会生成对其条目的共享引用。例如，在前面的代码中，(&favorites).into_iter()会返回一个Item类型为&String的迭代器。 - 给定对集合的 可变引用，
into_iter会返回一个迭代器，该迭代器会生成对其条目的可变引用。如果vector是某个Vec<String>，则调用(&mut vector).into_iter()会返回一个Item类型为&mut String的迭代器。 - 当按值传递集合时，
into_iter会返回一个迭代器，该迭代器会获取集合的所有权并按值返回这些条目，这些条目的所有权会从集合转移给消费者，原始集合在此过程中已被消耗掉了。例如，前面代码中的favorites.into_iter()调用返回了一个迭代器，该迭代器会按值生成每个字符串，消费者会获得每个字符串的所有权。当迭代器被丢弃时，BTreeSet中剩余的所有元素都将被丢弃，并且该集合的空壳也将被丢弃。
由于 for 循环会将 IntoIterator::into_iter 作为它的操作对象，因此这 3 种实现创建了以下惯用法，用于迭代对集合的共享引用或可变引用，或者消耗该集合并获取其元素的所有权：
for element in &collection { ... }
for element in &mut collection { ... }
for element in collection { ... }
其中每种用法最终都会调用此处列出的三种 IntoIterator 实现之一。
并非每种类型都提供了这 3 种实现，比如， HashSet、 BTreeSet 和 BinaryHeap 不会在可变引用上实现 IntoIterator，因为修改它们的元素可能会违反类型自身的不变性规则——修改后的值很可能有不同的哈希值，或者相对于其邻居的顺序改变了，所以修改它会让该类型处于错误状态。另一部分类型确实支持修改，但只支持修改一部分，比如， HashMap 和 BTreeMap 会生成对其条目值的可变引用，但只能提供对其键的共享引用，原因与前面给出的相似。
总体原则是，迭代应该是高效且可预测的，因此 Rust 不会提供昂贵或可能表现出意外行为的实现。（例如，对修改过的 HashSet 条目重新进行哈希，可能会导致在迭代中稍后再次遇到这些条目。）
切片实现了 3 个 IntoIterator 变体中的两个，由于切片并不拥有自己的元素，因此不存在“按值”引用的情况。 &[T] 和 &mut [T] 各自的 into_iter 会分别返回一个迭代器，该迭代器会生成对其元素的共享引用和可变引用。如果你将底层的切片类型 [T] 想象成某种集合，那它就完美地遵循了集合的总体模式。1
你可能已经注意到了，对于共享引用和可变引用，前两个 IntoIterator 变体等效于在引用目标上调用 iter 或 iter_mut。为什么 Rust 要同时提供 into_iter 和 iter 这两种方式呢？
IntoIterator 是确保 for 循环工作的关键，显而易见它是必要的。但当我们不用 for 循环时，写 favorites.iter() 会比 (&favorites).into_iter() 更清晰。我们会频繁通过共享引用进行迭代，因此 iter 和 iter_mut 仍然具有很高的工效学价值。
IntoIterator 在泛型代码中也很有用：你可以使用像 T: IntoIterator 这样的限界来将类型变量 T 限制为可以迭代的类型，还可以编写 T: IntoIterator<Item=U> 来进一步要求迭代时生成具有特定类型 U 的条目。例如， dump 函数可以转储任何其条目可用 "{:?}" 格式打印的可迭代者的值：
use std::fmt::Debug;
fn dump<T, U>(t: T)
where T: IntoIterator<Item=U>,
U: Debug
{
for u in t {
println!("{:?}", u);
}
}
但你不能使用 iter 和 iter_mut 来编写这个泛型函数，因为它们不是任何特型的方法：只是大多数可迭代类型恰好具有叫这两个名字的方法而已。
15.2.3 from_fn 与 successors
要生成一系列值，有一种简单而通用的方法，那就是提供一个能返回这些值的闭包。
给定返回 Option<T> 的函数， std::iter::from_fn（来自 fn）就会返回一个迭代器，该迭代器会调用 fn 来生成条目。例如：
use rand::random; // 在Cargo.toml中添加dependencies: rand = "0.7"
use std::iter::from_fn;
// 产生1000条端点均匀分布在区间[0, 1]上的随机线段的长度（这并不是
// `rand_distr` crate中能找到的分布类型，但你可以轻易实现一个）
let lengths: Vec<f64> =
from_fn(|| Some((random::<f64>() - random::<f64>()).abs()))
.take(1000)
.collect();
它会调用 from_fn 来让迭代器产生随机数。由于迭代器总是返回 Some，因此序列永不结束，但我们调用 take(1000) 时会将其限制为前 1000 个元素。然后 collect 会从这 1000 次迭代中构建出向量。这是构造已初始化向量的有效方式，我们会在 15.4.13 节中解释原因。
如果每个条目都依赖于其前一个条目，那么 std::iter::successors 函数很实用。只需要提供一个初始条目和一个函数，且该函数能接受一个条目并返回下一个条目的 Option。如果返回 None，则迭代结束。例如，下面是编写第 2 章中的曼德博集绘图器的 escape_time 函数的另一种方式：
use num::Complex;
use std::iter::successors;
fn escape_time(c: Complex<f64>, limit: usize) -> Option<usize> {
let zero = Complex { re: 0.0, im: 0.0 };
successors(Some(zero), |&z| { Some(z * z + c) })
.take(limit)
.enumerate()
.find(|(_i, z)| z.norm_sqr() > 4.0)
.map(|(i, _z)| i)
}
从零开始， successors（后继者）调用会通过反复对最后一个点求平方再加上参数 c 来生成复平面上的一系列点。在绘制曼德博集时，我们想看看这个序列是永远在原点附近打转还是“飞向”无穷远。调用 take(limit) 确定了我们追踪序列的次数限制，然后 enumerate 对每个点进行编号，将每个点 z 变成元组 (i, z)。我们使用 find 来寻找距离原点足够远的第一个点以判断是否逃逸。 find 方法会返回一个 Option：如果这样的点存在就返回 Some((i, z))，否则返回 None。调用 Option::map 会将 Some((i, z)) 变成 Some(i)，但不会改变 None，因为这正是我们想要的返回值。
from_fn 和 successors 都接受 FnMut 闭包，因此你的闭包可以捕获和修改周边作用域中的变量。例如，下面的 fibonacci 函数就用 move 闭包来捕获一个变量并将其用作自己的运行状态：
fn fibonacci() -> impl Iterator<Item=usize> {
let mut state = (0, 1);
std::iter::from_fn(move || {
state = (state.1, state.0 + state.1);
Some(state.0)
})
}
assert_eq!(fibonacci().take(8).collect::<Vec<_>>(),
vec![1, 1, 2, 3, 5, 8, 13, 21]);
需要注意的是， from_fn 方法和 successors 方法非常灵活，你几乎可以将任何对迭代器的使用改写成对其中之一的调用，通过传递复杂的闭包来得到你想要的行为。但这样做浪费了迭代器提供的机会，即使用常见模式的标准名称来更清晰地表达计算中的数据流。在使用这两个方法之前，请确保你已经熟悉本章中的其他迭代器方法，通常其他迭代器是更好的选择。2
15.2.4 drain 方法
有许多集合类型提供了 drain（抽取）方法。 drain 会接受一个对集合的可变引用，并返回一个迭代器，该迭代器会将每个元素的所有权传给消费者。然而，与按值获取并消耗掉集合的 into_iter() 方法不同， drain 只会借入对集合的可变引用，当迭代器被丢弃时，它会从集合中移除所有剩余元素以清空集合。
对于可以按范围索引的类型（如 String、向量和 VecDeque）， drain 方法可指定要移除的元素范围，而不是“抽干”整个序列：
let mut outer = "Earth".to_string();
let inner = String::from_iter(outer.drain(1..4));
assert_eq!(outer, "Eh");
assert_eq!(inner, "art");
如果确实需要“抽干”整个序列，使用整个范围（ ..）作为参数即可。
15.2.5 其他迭代器源
前面的内容主要关注集合类型（如向量和 HashMap），但标准库中还有许多其他类型也支持迭代。表 15-1 总结了一些比较有趣的迭代器，限于篇幅，还有更多没有列出来。我们在专门讲解特定类型的章（第 16 章、第 17 章和第 18 章）中会更详细地介绍其中的一些方法。
表 15-1：标准库中的其他迭代器
类型或特型
表达式
注意事项
std::ops::Range
1..10
(1..10).step_by(2)
两个端点必须是可迭代的整数类型。范围包括起始值，不包括结束值
生成 1、3、5、7、9
std::ops::RangeFrom
1..
无界迭代。起点必须是一个整数。如果值达到了该类型的上限，可能会发生 panic 或溢出
std::ops::RangeInclusive
1..=10
和 Range 类似，但包含结束值
Option<T>
Some(10).iter()
表现得像一个长度为 0（ None）或 1（ Some(v)）的向量
Result<T, E>
Ok("blah").iter()
类似于 Option，但生成 Ok 值
Vec<T>,&[T]
v.windows(16)
v.chunks(16)
v.chunks_mut(1024)
v.split(|byte|byte & 1 != 0)
v.split_mut(...)
v.rsplit(...)
v.splitn(n, ...)
从左到右生成给定长度的所有连续切片。窗口之间会有重叠
从左到右生成给定长度的不重叠的连续切片
和 chunks 类似，但生成的切片是可变的
生成由匹配给定谓词的元素分隔的切片
同上，但生成可变切片
与 split 类似，但从右到左生成切片
与 split 类似，但最多生成 n 个切片
String,&str
s.bytes()
s.chars()
s.split_whitespace()
s.lines()
s.split('/')
s.matches(char::is_numeric)
生成一些 UTF-8 格式的字节
生成一些 UTF-8 表示的字符
按空白字符拆分字符串，并生成非空白字符的切片
生成字符串各行的切片
用给定模式拆分字符串，用匹配项之间的部分生成切片。模式可以有很多种：字符、 String 和闭包
生成与给定模式匹配的切片
std::collections::HashMap, std::collections::BTreeMap
map.keys(), map.values()
map.values_mut()
生成对该 map 的键或值的共享引用
生成对条目值的可变引用
std::collections::HashSet, std::collections::BTreeSet
set1.union(set2)
set1.intersection(set2)
生成对 set1 和 set2 并集元素的共享引用
生成对 set1 和 set2 交集元素的共享引用
std::sync::mpsc::Receiver
recv.iter()
生成从位于另一个线程的对端发送者发来的值
std::io::Read
stream.bytes()
stream.chars()
从 I/O 流中生成一些字节
将流解析为 UTF-8，并生成一些字符
std::io::BufRead
bufstream.lines()
bufstream.split(0)
将流解析为 UTF-8，并按行生成一些 String
使用给定的字节拆分流，生成该字节间的 Vec<u8> 缓冲区
std::fs::ReadDir
std::fs::read_dir(path)
生成目录条目
std::net::TcpListener
listener.incoming()
生成传入的网络连接
自由函数
std::iter::empty()
std::iter::once(5)
std::iter::repeat("#9")
立即返回 None
生成给定的值然后结束
总是生成给定的值