理解 Rust 迭代器
原文地址¶
对集合容器的遍历是一项非常常见的操作，通常用于循环遍历的操作有 C 风格的 for 语句，比如下面代码用于遍历一个数组并输出：
这种循环遍历足够强大，也足够灵活，受到 C，C++，Java, JavaScript 等很多语言的支持。但因为它足够灵活使用起来有一些注意事项，加之 Rust 对于语言一致性的考虑所以并不支持这种 C 风格的循环。在 Rust 中遍历集合容器都是通过迭代器模式来完成的，也称为游标模式，它提供了一种方法，可以顺序访问一个集合容器中的元素，而又不需要暴露该容器的内部结构和实现细节。
迭代器分为两种，内部迭代器 和 外部迭代器；
内部迭代器就是一些实现了遍历整个容器并将给定的函数 依次 应用到容器中 每个元素 的高阶函数。这就意味者外部无法控制迭代的流程，只要调用了内部迭代器，就必须等待迭代器依次为容器中的每个元素都执行完相关的操作之后才可以停止遍历。
外部迭代器也叫主动迭代器，通常被认为是指向某种类型的指针，主要有两种操作：引用集合中的特定元素（称为元素访问）；修改自身使其指向下一个元素（称为元素遍历）。当然，还需要有方法可以创建一个迭代器并让它指向第一个元素以及还需要有某种方式来确定何时迭代器已经遍历了容器中所有元素。它的一大特点就是外部可以控制整个遍历的流程；
如下分别是 Rust 中通过内部迭代和外部迭代的方式将一串字符串改大写的操作：
内部迭代示例：
fn main() {
let str = "hello world!";
str.chars().collect::<Vec<char>>().iter().for_each(|x| {
print!("{}", x.to_uppercase());
});
}
外部迭代示例：
fn main() {
let str = "hello world!";
for char in str.chars() {
print!("{}", char.to_uppercase());
}
}
std::iter 模块¶
Rust 迭代器相关的所有 trait，struct，function 等的实现全部都位于 std::iter 模块。所以我们可以通过 std::iter 模块的组织对 Rust 迭代器的实现架构有一个大致的了解。可以看到 std::iter 模块主要有两个多级子模块 adapters 和 traits 模块，以及两个单级子模块 range 和 sources。
通过查看它们的文件可以看到，trait 模块下主要定义了迭代器相关的一些 trait，比如 Iterator，FromIterator，IntoIterator，DoubleEndedIterator 等。adapters 模块主要定义了一些 struct，并且这些 struct 无一例外的都实现了 Iterator 这个 trait，有的还实现了额外的一些 trait，比如 DoubleEndIterator 等。sources 模块里面则主要提供了一些函数，这些函数可用来直接创建对应的迭代器。
可知，Rust 迭代器主要分为三个部分：Traits，Struct，Function。
Traits 是核心部分，它主要定义了存在哪种类型的迭代器以及你可以用它们做什么。Struct 通常都是 Traits 中定义的各种方法的返回类型。通常来说，你可能更想要了解创建这些 struct 的方法，而不是这些 struct 本身。Function 就是提供了一些很有用的辅助函数用于直接创建一些基本的迭代器。
迭代器相关的 traits¶
从上面可以看到，Rust 迭代器的功能都是通过强大的 trait 系统实现的，而堪称 Rust 迭代器核心和灵魂的角色就是 Iterator trait。它的定义如下：
Iterator 里面定义了非常多实用的函数，比如 map，filter，fold 等，这些都有默认实现，并构建在next() 方法之上。我们需要关心的只有关联类型 Item，以及 next() 函数。next() 函数主要的功能就是推进迭代器往前走并返回下一个元素，若不存在下一个元素的话，则返回 None。所以 Item 也就是表示被迭代的元素类型。
Rust 的迭代器都是可组合的，一个常见的用法就是通过迭代器的链式调用来完成更复杂的功能。比如下面就是一个通过组合不同的迭代器来实现字符串中单词首字母大写例子：
fn main() {
let str = "hello world; hello rust!";
// 首先把字符串按单词拆分
let res = str.split(' ').collect::<Vec<&str>>().iter().map(|x| {
// 把单词的首字母转换乘大写
x.chars()
.enumerate()
.map(|x| if x.0 == 0 { x.1.to_ascii_uppercase() } else { x.1 } )
.collect::<String>()
})// 把转换后的单词再拼接成字符串
.fold(String::from(""), |acc, x| acc + &x + " " );
// 输出 "Hello World; Hello Rust!"
println!("{:?}", res.trim());
}
Rust 的集合容器提供了三种不同的方法来创建迭代器。
- iter()，对 &T 的迭代
- iter_mut()，对 &mut T 的迭代
- into_iter()，对 T 的迭代
前面两种是容器的普通方法，into_iter() 来自 IntoIterator trait，不过 Rust 标准库中有如下的代码：
#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator> IntoIterator for I {
type Item = I::Item;
type IntoIter = I;
fn into_iter(self) -> I {
self
}
}
可以看到 Rust 自动为所有实现了 Iterator triat 的类型实现了 IntoIterator trait。通过给一个类型实现 IntoIterator trait，你可以定义如何把这个类型转换成一个迭代器，这对于常见的描述某种集合的类型很有用。另外一个好处就是，假如你的类型实现了 IntoIterator trait，那么你的类型就可以直接使用 for 循环语法来遍历了。原因就在于 Rust 的 for 循环实际上就是迭代器的语法糖。
如上的代码，Rust 编译器在编译的时候有可能被转换成如下的代码：
fn main() {
let arr = vec![1,2,3,4,5];
// 外围的 block 充当 for 的作用域
{
match arr.into_iter() {
mut iter => {
loop {
let next;
match iter.next() {
Some(val) => next = val,
None => break,
}
println!("{}", next);
}
}
};
}
}
还有一个与 IntoIterator 相反的 FromIterator trait，他的作用和 IntoIterator 相反，它是定义了如何从迭代器转换成指定类型。它主要提供了一个 from_iter() 方法，不过这个方法通常很少直接使用，常见的方式是通过 Iterator trait 里面提供的 collect() 方法来间接调用。
/////////////////////////// rust stdlib //////////////////////////
pub trait Iterator {
.....
fn collect<B: FromIterator<Self::Item>>(self) -> B
where
Self: Sized,
{
FromIterator::from_iter(self)
}
}
/////////////////////////////////////////////////////////////////
fn main() {
let vec = vec![1,2,3,4];
let vec = vec.iter().map(|x| x * 2 ).collect::<Vec<i32>>();
println!("vec={:?}", vec);
}
如下代码就是自定义个的一个叫做 Even 的迭代器，该迭代器的功能就是遍历给定范围内的偶数。可以看到我们只需要实现了 Iterator trait 的 next() 方法之后，一个迭代器就完成了，并且也可以像内置的迭代器那样直接 for 循环进行遍历。
struct Even {
start: i32,
end: i32,
}
impl Even {
fn new(st: i32, ed: i32) -> Self {
assert_eq!(st % 2, 0);
Even {
start: st,
end: ed
}
}
}
impl Iterator for Even {
type Item=i32;
fn next(&mut self) -> Option<Self::Item> {
self.start += 2;
if self.start > 12 {
return None;
}
Some(self.start)
}
}
fn main() {
for x in Even::new(2, 12) {
println!("{}", x);
}
}
迭代器适配器¶
接受一个迭代器并返回另一个迭代器的函数就被叫做迭代器适配器。常见的迭代器适配器包括 map，filter，zip 等。
map：接受一个闭包并在每个元素中都应用给定的闭包以返回一个迭代器。注意，map 是惰性的，也就是说你必须要调用另一个消费函数（比如，collect，count等）代码才会执行。
fn main() {
let arr = [1,2,3,4,6];
// let double_arr = arr.iter().map(|x| x*x );
let double_arr = arr.iter().map(|x| x*x ).collect::<Vec<i32>>();
println!("{:?}", double_arr);
}
可以看到，map 实际上的动作就是从一个迭代器到另一个迭代器的映射，具体的映射关系就是传递进去的闭包。注意第三行并没有调用任何消费函数，map() 接受的映射关系实际上不会被执行，得到到还只是一个叫做 Map 的迭代器结构体，而不是一个 vector。
filter：创建一个新的迭代器，迭代器中的元素由传入的闭包决定是否应该过滤出来。也就是说传入的闭包一定需要返回一个 bool 类型。如果闭包返回 true，则元素被返回，若闭包返回 false，就会略过它并在下一个元素上调用闭包。
fn main() {
let arr = (0..100).into_iter().filter( |x| x % 21==0 ).collect::<Vec<i32>>();
println!("{:?}", arr);
}
可以看到 filter 实际上就是在一个迭代器上过滤出符合条件的元素到另一个迭代器中，具体过滤的条件就是传入的闭包决定的。注意它也是惰性的，也是需要执行一个消费函数后，才会执行过滤的代码。map，filter 都是两个非常常见的迭代器适配器，并且很多时候都需要两个组合使用，如下：
fn main() {
let a = ["1", "rust", "3", "cpp", "5"];
let mut arr = a.iter()
.filter(|x| x.parse::<i32>().is_ok())
.map(|x| x.parse::<i32>().ok().unwrap())
.collect::<Vec<i32>>();
println!("{:?}", arr); //输出：[1, 3, 5]
}
所以，Rust 提供了 filter_map 迭代器适配器来实现 filter 和 map 组合在一起的功能。那它是怎么做到在一个闭包里面同时实现映射和过滤两个功能的呢？答案就在于闭包的返回值，我们知道 map 的闭包返回一个泛型 T，filter 的闭包返回一个 bool 类型。而 filter_map 的闭包则返回一个 Option
fn main() {
let a = ["1", "rust", "3", "cpp", "5"];
let mut arr = a.iter()
.filter_map(|x| x.parse::<i32>().ok())
.collect::<Vec<i32>>();
println!("{:?}", arr);
}
zip：压缩两个迭代器到一个新的迭代器。迭代的元素是一个元组，元组第一个元素来自第一个迭代器，元组第二个元素来自迭代器。
如下代码就是使用 zip 迭代器按顺序打印所有的小写英文字母以及它们的索引。
fn main() {
let mut a = (0..).into_iter().zip('a'..='z');
for x in a {
println!("{:?}", x);
}
}
(0, 'a')
(1, 'b')
(2, 'c')
(3, 'd')
(4, 'e')
(5, 'f')
(6, 'g')
(7, 'h')
(8, 'i')
(9, 'j')
(10, 'k')
(11, 'l')
(12, 'm')
(13, 'n')
(14, 'o')
(15, 'p')
(16, 'q')
(17, 'r')
(18, 's')
(19, 't')
(20, 'u')
(21, 'v')
(22, 'w')
(23, 'x')
(24, 'y')
(25, 'z')
可以看到，zip 迭代器具有短路性质，也就是说迭代器较短的那个迭代器迭代完成之后整个 zip 动作也就完成了。
除此之外，Rust 还提供其他很多有用的迭代器适配器，比如 StepBy，Take，Scan 等，同时还有一些非常有用的迭代器方法，比如 fold，for_each，nth 等。了解过函数式编程的童鞋对这些应该会感到熟悉，更多详细的资料可以查看 Rust 文档。
迭代器的惰性，无限性¶
从上面例子我们也知道了 Rust 中的迭代器以及迭代器适配器都是惰性的。就是所仅仅创建一个迭代器或迭代器适配器并不会做任何实际的工作，直到你调用了 next() 函数。比如下面的代码实际什么也不会输出：
上面的代码仅仅就只是创建了一个 Map 迭代器适配器而已，并没有任何地方使用这个适配器，所以 Map 适配器传入的闭包代码就不会被执行。对于上面这种情况，一般是使用 for_each() 函数：
另外，得益于 Rust 迭代器的惰性，Rust 迭代器的范围可以是无限的，因为你创建一个无限的迭代器并没有坏的影响，因为它实际上并没有执行。真正需要执行的时候也是从一个无限的迭代器中迭代有限的次数。