虎牙音镇楼。

本文为笔者阅读Programming Rust第二版迭代器一章后的学习笔记以及一些个人私货。在此感谢作者和中文版译者。

背景

迭代器是现代编程语言中已经形成完整体系的一种设计模式。程序员可以使用迭代器，以相同的方式遍历各类集合，不需要了解集合的内部结构。

当然，老资料中的迭代器模式看上去平平无奇——似乎并没有什么值得令人称道的地方，C++集合的iterator就是这样，这种迭代器还是偏向底层，因此好处还不是非常明显。我们这里谈的迭代器是后期发展出的更为高级的设计理念，一个完整的迭代器库分为三部分：创建迭代器、应用各种迭代器适配器、最后消耗迭代器得到返回值。迭代器API往往是以流式调用的方式实现的，能够极大的提升代码的可读性，实着优雅。标准库实现了这种新式迭代器的语言有很多，比如Java8的Stream API（顺带一提笔者做过这个库的学习笔记，链接附上 https://lvren1485.github.io/post/d60efe45.html ），我们今天的主角Rust的std::iter，还有刚刚说的C++，在c++20痛改前非，加入了std::ranges和std::views库，也类似地实现了迭代器库。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main {
    public static void main(String[] args) {
        // 有运行时开销！
        List<Book> bookList = authors.stream()
                .distinct()
                .filter(author -> author.getAge() < 18)
                .flatMap(author -> author.getBooks().stream())
                .distinct()
                .filter(book -> book.getScore() > 70)
                .collect(Collectors.toList());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    // 依托
    auto view = numbers 
              | std::views::take(5)
              | std::views::filter([](int n) { return n % 2 == 0; })
              | std::views::transform([](int n) { return n * n; });
              | std::views::reverse;
    
    for (int n : view) {
        std::cout << n << " ";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
fn main() {
    let v = vec![1, 1, 4, 5, 1, 4];
    let result = v.iter()
            .take(5)
            .filter(|&n| n % 2 == 0)
            .map(|n| n * n);
            .collect();
    
    println!("{:?}", result);
}

但是，Java的Stream会创建很多的中间对象，存在大量的运行时开销，效率堪忧；C++的这一套东西，由于lambda的语法噪声实在太多以及臭名昭著的std::地狱，就算改成了流式调用，也并没有增加很多可读性，远远看上去还是一大坨。相比之下，Rust的迭代器库是用泛型实现的，可以做到零成本抽象，编译器能够拿到足够的信息直接内联代码，生成的二进制机器码和手写的循环一样高效，但可读性又远远优于循环，实在是美哉美哉。Rust又赢了，50 wins in 50 days.

Rust迭代器的基础

详细介绍Rust的迭代器库之前，先来明确几个概念。

对于实现了std::iter::Iterator trait 的类型，我们称之为迭代器，其next()方法会返回下一个迭代的值的Option，直到返回None，代表到达了序列的终点；

对于实现了std::iter::IntoIterator trait的类型，我们称之为可迭代对象，其into_iter()会消耗自身的所有权，并返回一个迭代自身的迭代器。

所有的迭代器都是可迭代对象。在标准库提供的实现中，它们的into_iter()方法直接返回自身。

下面就按刚才说的三个部分依次介绍Rust的迭代器库。

创建迭代器

iter && iter_mut

很多类型都提供了iter()和iter_mut()方法，分别返回item的共享引用和可变引用。与into_iter()不同，他们不会传递原集合的所有权，因此原集合之后还可继续使用。

但是请注意，这两个方法完全是自己选择实现的，没有任何Trait要求必须实现这两个方法。也就是说，在泛型函数里不能使用这两个方法。

提供多个IntoIterator实现

很多集合会提供多个IntoIterator的实现，分别是为共享引用（&T），可变引用（&mut T），移动（T）提供的实现。

这里对应上一节，T的iter()等价于&T的into_iter()，T的iter_mut()等价于&mut T的into_iter()。

为什么要提供两种等价的写法？for循环（for x in express）是语法糖，实际会调用IntoIterator::into_iter(express)，所以多个IntoIterator的实现是必要的。但是不写for循环时，xxx.iter()显然比(&xxx).into_iter()更加清晰。

from_fn && successors

from_fn使用一个返回Option<T>的闭包来创建迭代器。

successors可产生每个item依赖上一个item的关系的序列的迭代器。

drain

对于可以用范围索引的类型，drain方法获取一个要移除的元素的范围，可以只移除这个范围的元素，而不消耗整个序列。

其他

很多集合还提供了其他自定义的方法来创建迭代器。笔者建议用什么库再去翻文档，直接背下来也不明智，实在不想翻就请教D指导，好用爱用。

不过这里再提一下std::iter提供的三种迭代器：

empty() : 立即返回None。

once(114514) : 产生一次给定值然后结束。

repeat("Genshin") : 无限产生给定值。（和适配器的cycle()做一下区分，这个只能重复一个值）

迭代器适配器

Iterator trait提供了一系列适配器方法，我们简称适配器。他们消耗一个迭代器，返回一个新的迭代器。

map

对每一个item应用一个闭包产生新item。

filter

通过一个闭包决定保留哪些item，丢弃哪些item。

filter_map

类似filter和map的结合，但是闭包返回值类型为Option<B>，为None就丢弃，为Some(b)时，b就是适配器产生的下一个item。

flat_map

可以看做filter_map的扩展，filter_map产生0或1个值，flat_map可以产生0到多个值。其参数的闭包返回值类型为一个可迭代对象。

flatten

对item类型是可迭代对象的迭代器使用，把所有迭代器的元素全部连接起来，放在同一个迭代器中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// flat_map和flatten示例
// str::to_uppercase实现简化版
fn to_uppercase(&self) -> String {
    self.chars()
    	.map(char::to_uppercase) // 返回可能产生一个或多个字符的迭代器
    	.flatten()
    	.collect()
}
// 等价于
fn to_uppercase(&self) -> String {
    self.chars()
    	.flat_map(char::to_uppercase)
    	.collect()
}

顺带一提为啥这里char::to_uppercase返回的是迭代器。我们Rust是国际化的，不要局限于English。某些字符的大写形式可能对应多个字符，例如德语的ß大写是"SS"。Rust面向国际，提供Unicode兼容性，Rust又赢了

take && take_while

take可以迭代一定次数后停止迭代。参数就是迭代次数。

take_while传入一个闭包作为谓词（predicate），有一个item使predicate返回false时停止迭代。

skip && skip_while

和上面正好相反。

skip跳过起始的n个元素后再开始迭代。

skip_while直到一个item使predicate返回false时开始迭代。注意使其返回false的那个item也会被迭代。

peekable

可以提前看下一个产生的item，而不将其消耗。可以使用std::iter::Iterator的peekable()方法把迭代器转换为一个Peekable迭代器，其有一个额外的peek()方法返回Option<&Item>，如果原迭代器已经迭代完就是None，否则就是Some(r)，r是下一个item的共享引用。

例如字符流解析数字的时候会有用，看到下一个非数字字符才知道数字在哪里结束。也不是非用不可，但是这样写会比较优雅，可读性更好。

fuse

Iterator::next()返回None后，trait没有指定如果后续再调用next()的行为。（大多数都是再次返回None，但不能保证所有都如此）

fuse适配器接受任何迭代器，并产生一个第一个返回None之后一直返回None的迭代器。

rev && DoubleEndedIterator

对于实现了std::iter::DoubleEndedIterator trait的迭代器，可以使用next()和next_back()在迭代范围两端产生item。

如果迭代器是双端的，可以使用rev适配器将其反转，返回的迭代器也是双端迭代器。

inspect

经常用来调试。对每一个item的共享引用应用一个闭包。因此闭包无法影响到item，但可以做一些打印、断言之类的操作。

chain

把一个迭代器附加到另一个之后，可以把任何产生相同类型item的迭代器连接起来。

如果两个底层迭代器都是可逆的，那么产生的迭代器也是可逆的。

1
2
let v: Vec<i32> = (1..4).chain(vec![20, 30, 40]).rev().collect();
assert_eq!(v, [40, 30, 20, 3, 2, 1]);

enumerate

和Python类似，把一个索引附加到序列中。

例如原值是A, B, C, 返回的迭代器产生的值就是(0, A), (1, B), (2, C)。

zip

把两个迭代器组合成单个迭代器，一次返回一对item。若两个底层迭代器中有一个结束，zip迭代器也会随之结束。

1
2
let v: Vec<_> = (0..).zip("ABC".chars()).collect();
assert_eq!(v, vec![(0, 'A'), (1, 'B'), (2, 'C')]);

可以把zip看做enumerate的泛化版。

zip的两个迭代器的item不需要相同。

by_ref

by_ref借用迭代器的可变引用，可以对这个引用应用适配器。借用结束后，可以重新访问原迭代器，原迭代器未计算的元素仍保留。

cloned && copied

cloned适配器获取一个产生引用的迭代器，返回产生这些引用克隆出的值的迭代器。

类似iter.map(|item| item.clone())。

copied适配器类似，但是被引用的类型必须实现Copy。

类似iter.map(|item| *item)。

cycle

cycle适配器返回一个无限重复底层迭代器产生的序列的迭代器。（还记得么？和std::iter::repeat()对比记忆。）

底层迭代器必须实现Clone，这样cycle才能保存它的初始状态。

消耗迭代器

count

返回迭代器成功迭代的item的数量。

sum

计算迭代器的item的和。

product

计算迭代器的item的积。

可以通过实现std::iter::Sum和std::iter::Product来拓展sum和product支持其他类型，否则item只能是整数或浮点数。

max && min

返回迭代器产生的item的最大值/最小值。item的类型必须实现std::cmp::Ord。Rust的浮点数类型只实现了std::cmp::PartialOrd，因此浮点数序列最值无法这样计算。

max_by && min_by

通过用户提供的比较函数比较各item的大小，返回最大值/最小值。

其比较函数参数需要是引用。

max_by_key && min_by_key

通过用户提供的函数返回的值比较各item的大小，返回最大值/最小值。

比较item序列

迭代器提供了eq和ne方法进行相等性比较，lt，le，gt，ge方法用于顺序性比较，每次从两个迭代器各取一个item进行比较，直到可以比较出结果。

any && all

any对迭代器产生的每一个item都应用一个闭包，当任意item使闭包返回true时返回true。

all对迭代器产生的每一个item都应用一个闭包，当所有item都使闭包返回true时返回true。

也是惰性求值，一旦可以得出结果，则不会继续消耗剩余的item。

position && rposition

position返回第一个使闭包返回true的item的索引的Option。如果没有item使得其返回true，将会返回None，否则返回Some(index)。

rposition与其相同，区别在于是从最后一个元素往前搜索。

rposition要求迭代器实现DoubleEndedIterator和ExactSizeIterator。

fold && rfold

fold可以指定某种方式，累计所有item进行计算。

1
2
3
4
5
let a = [5, 6, 7, 8, 9, 10];
assert_eq!(a.iter().fold(0, |n, _| n + 1), 6);                  // count
assert_eq!(a.iter().fold(0, |n, i| n + i), 45);                 // sum
assert_eq!(a.iter().fold(1, |n, i| n * i), 151200);             // product
assert_eq!(a.iter().fold(i32::min_value(), std::cmp::max), 10); // max

rfold与fold相同，其需要双端迭代器，从最后往前处理Item。

try_fold && try_rfold

和上面基本相同。区别在于它的迭代过程可以提前退出，不需要消耗所有item。传递的闭包返回一个Result或Option，出问题就立刻返回，否则继续处理。

nth && nth_back

nth跳过接下来n个item，返回下一个item，若已经为空则返回None。nth_back从尾部往前移动，依旧需要双端迭代器。

nth(0)等价于next()，nth_back(0)等价于next_back()。

last

返回迭代器产生的最后一个item，如果已经为空则返回None。

不管迭代器是否可逆，都会消耗掉所有item。

find && rfind && find_map

find返回第一个使给定闭包返回true的item，无item满足条件就返回None。

rfind类似，从最后往前寻找。双端迭代器。

如果需要自己产生一个特定类型的值而不是bool，可以使用find_map，返回第一个是Some的Option。

collect && FromIterator

当一些集合类型知道如何从迭代器构建自身时，会实现std::iter::FromIterator<A> trait，其类型关联函数from_iter()从一个产生A类型值的迭代器构建一个自身类型的集合。collect()本质上是它的便捷用法，只要迭代器产生合适的item类型，就可以构建相应的集合。

extend

如果一个类型实现了std::iter::Extend trait，它的extend方法可以把一个可迭代对象的item添加到集合中。

所有标准集合都实现了Extend。

partition

partition将一个迭代器的item分成两个集合，使用一个闭包来决定每个item属于哪个集合。返回true的放入第一个集合，返回false的放入第二个集合。

partition也可以创建任意类型的集合，但两个集合的类型必须相同。

不像有的语言的partition操作把一个迭代器分成两个迭代器，Rust由于其迭代器惰性求值的特性，不缓存未分类的item，要分类就必须将其实际求出，因此无论如何都会创建某种类型的集合，所以Rust的partition签名才如此设计。

for_each && try_for_each

for_each方法对每一个item应用一个闭包。

如果闭包需要容错或提前退出，可以使用try_for_each。