Skip to content

Latest commit

 

History

History
1493 lines (1073 loc) · 66.4 KB

ch15-迭代器.md

File metadata and controls

1493 lines (1073 loc) · 66.4 KB

迭代器(Iterators)

这是漫长一天的结束. --Phil

原文

It was the end of a very long day. --Phil

迭代器(iterator) 是一个生成一系列值的值,通常用于循环操作.Rust的标准库提供遍历向量,字符串,哈希表和其他集合的迭代器,还提供从输入流生成文本行的迭代器,到达网络服务器的连接的迭代器,通过通信通道从其他线程接收的值的迭代器,等等.当然,你可以为自己的目的实现迭代器.Rust的for循环提供了使用迭代器的自然的语法,但迭代器本身也提供了一组丰富的用于映射(mapping),过滤(filtering),连接(joining),收集(collecting)等的方法集.

Rust的迭代器具有灵活性,表现力和高效性.考虑以下函数,它返回前n个正整数的总和(通常称为 第n个三角数(nth triangle number) ):

fn triangle(n: i32) -> i32 {
    let mut sum = 0;
    for i in 1..n+1 {
        sum += i;
    }
    sum
}

表达式1..n+1是Range<i32>值.Range<i32>是一个迭代器,它生成从其起始值(包括)到其结束值(不包括)的整数,因此你可以将它用作for循环的操作数,以将值从1加到n.

但是迭代器也有一个fold方法,你可以在等效定义中使用它:

fn triangle(n: i32) -> i32 {
    (1..n+1).fold(0, |sum, item| sum + item)
}

从0开始作为运行总和,fold获取1..n+1产生的每个值并应用闭包|sum, item| sum + item去运行总和和值.闭包的返回值被视为新的运行总和.它返回的最后一个值是fold本身返回的值--在这种情况下,是整个序列的总和.如果你习惯于for和while循环,这可能看起来很奇怪,但是一旦你习惯了它,fold是一个清晰易懂的替代方案.

这是函数式编程语言的标准功能,它非常注重表现力.但Rust的迭代器经过精心设计,以确保编译器能够将它们转换为出色的机器码.在之前显示的第二个定义的发布版本中,Rust知道fold的定义,并将其内联为triangle.接下来,闭包|sum, item| sum + item被内联到那里.最后,Rust检查组合代码并认识到有一种更简单的方法可以计算数字从1到n的总和:总和总是等于n * (n+1) / 2.Rust将整个triangle体,循环,闭包以及所有内容转换为单个乘法指令和一些其他位运算.

这个例子恰好涉及简单的算术,但迭代器在更重要的使用时也表现良好.它们是Rust提供灵活的抽象的另一个例子,在典型使用中几乎不会产生任何开销.

本章的其余部分分为五个部分:

  • 首先我们将解释Iterator和IntoIteratortraits,它们是Rust迭代器的基础.

  • 然后我们将介绍典型迭代器管道的三个阶段:从某种值源创建迭代器;通过选择或处理值来调整一种迭代器到另一种迭代器;然后消费迭代器产生的值.

  • 最后,我们将展示如何为你自己的类型实现迭代器.

有很多方法,所以一旦你有了大概的想法就可以浏览一个部分.但迭代器在惯用Rust中很常见,熟悉它们附带的工具对掌握语言至关重要.

Iterator和IntoIterator Traits(Iterator and IntoIterator Traits)

迭代器是实现std::iter::Iteratortrait的任何值:

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

Item是迭代器生成的值的类型.next方法要么返回Some(v),其中v是迭代器的下一个值,要么返回None以指示序列的结束.这里我们省略了Iterator的许多默认方法;在本章的其余部分我们将单独介绍它们.

如果有一种自然的迭代某种类型的方式,它可以实现std::iter::IntoIterator,其into_iter方法接受一个值并在其上返回一个迭代器:

trait IntoIterator where Self::IntoIter::Item == Self::Item {
    type Item;
    type IntoIter: Iterator;
    fn into_iter(self) -> Self::IntoIter;
}

IntoIter是迭代器值本身的类型,Item是它生成的值的类型.我们将实现IntoIterator的任何类型称为 可迭代的(iterable) ,因为如果你问的话,你可以迭代它.

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,则循环结束.

虽然for循环总是在其操作数上调用into_iter,但你也可以直接将迭代器传递给for循环;例如,当你在Range上循环时会发生这种情况.所有迭代器都自动实现IntoIterator,使用一个简单地返回迭代器的into_iter方法.

如果在返回None之后再次调用迭代器的next方法,则Iteratortrait不会指定它应该做什么.大多数迭代器只会再次返回None,但不是全部.(如果这样会导致问题,请参阅第338页的"保险(fuse)"中的fuse适配器.)

这是迭代器的一些术语:

  • 正如我们所说, 迭代器(iterator) 是实现Iterator的任何类型.

  • 可迭代的(iterable) 是实现IntoIterator的任何类型:你可以通过调用其into_iter方法获取迭代器.在这种情况下,向量引用&v是可迭代的.

  • 迭代器 生成(produces) 值.

  • 迭代器生成的值是 项(items) .这里的项是"antimony","arsenic"等.

  • 接收迭代器生成的项的代码是 消费者(consumer) .在此示例中,for循环消费迭代器的项.

创建迭代器(Creating Iterators)

Rust标准库文档详细解释了每种类型提供的迭代器类型,但该库遵循一些通用约定来帮助你获得定向并找到所需内容.

iter和iter_mut方法(iter and iter_mut Methods)

大多数集合类型提供iter和iter_mut方法,这些方法返回类型上的自然迭代器,从而生成每个项的共享或可变引用.像&[T]和&str这样的切片也有iter和iter_mut方法.如果你不打算让for循环为你处理它的话,这些方法是获取迭代器的最常用方法:

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,它是操作系统调用接受的类型字符串的切片的借用.

IntoIterator实现(IntoIterator Implementations)

当一个类型实现了IntoIterator时,你可以自己调用它的into_iter方法,就像for循环一样:

// You should usually use HashSet, but its iteration order is
// nondeterministic, so BTreeSet works better in examples.
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实现,用于共享引用,可变引用和移动:

  • 给定对集合的 共享引用(shared reference) ,into_iter返回一个迭代器,该迭代器生成对其项的共享引用.例如,在前面的代码中,(&favorites).into_iter()将返回一个其Item类型为&String的迭代器.

  • 给定对集合的 可变引用(mutable reference) ,into_iter返回一个迭代器,该迭代器生成对项的可变引用.例如,如果vector是某个Vec<String>,则调用(&mut vector).into_iter()将返回一个其Item类型为&mut String的迭代器.

  • 当 通过值(by value) 传递集合时,into_iter返回一个迭代器,该迭代器获取集合的所有权并通过值返回项;项的所有权从集合移动到消费者,并且在此过程中消耗原始集合.例如,前面代码中的调用favorites.into_iter()返回一个迭代器,它通过值生成每个字符串;消费者接收每个字符串的所有权.当删除迭代器时,BTreeSet中剩余的任何元素也会被删除,并且该集的现在为空的外壳被丢弃.

由于for循环将IntoIterator::into_iter应用于其操作数,因此这三个实现创建了以下习惯用于迭代对集合的共享引用或可变引用,或者使用集合并获取其元素的所有权:

for element in &collection { ... }
for element in &mut collection { ... }
for element in collection { ... }

这些中的每一个都只会调用此处列出的其中一个IntoIterator实现.

并非每种类型都提供所有三种实现.例如,HashSet,BTreeSet和BinaryHeap没有在可变引用上实现IntoIterator,因为修改它们的元素可能会违反类型的不变性:修改后的值可能具有不同的哈希值,或者对其相邻值进行不同的排序,因此修改它会使其位置不正确.其他类型确实支持突变,但只部分地支持.例如,HashMap和BTreeMap产生对其条目的值可变引用,但对它们的键仅共享引用,原因与之前给出的类似.

一般原则是迭代应该是高效且可预测的,因此不提供昂贵的或者可能表现出令人惊讶的行为的实现(例如,重新哈希已修改的HashSet条目,可能在稍后的迭代中重新访问它们),Rust完全省略它们.

切片实现三个IntoIterator变体中的两个;因为他们没有自己的元素,所以没有"通过值(by value)"的情况.相反,to_iter对于&[T]和&mut [T]返回迭代器,它产生对元素的共享引用和可变引用.如果你将底层切片类型[T]想象为某种类型的集合,则这非常适合整体模式.

你可能已经注意到前两个IntoIterator变体(对于共享引用和可变引用)等同于在引用的对象上调用iter或iter_mut.为什么Rust同时提供两种?

IntoIterator是使for循环工作的,所以这显然是必要的.但是当你没有使用for循环时,favorites.iter()比(&favorites).into_iter()更清晰.通过共享引用进行迭代是你经常需要的,因此iter和iter_mut对于其人体工程学仍然很有价值.

IntoIterator在泛型代码中也很有用:你可以使用类似T: IntoIterator的限制将类型变量T限制为可以迭代的类型.或者,你可以编写T: IntoIterator<Item=U>以进一步要求迭代生成特定类型U.例如,此函数从任何可以使用"{: ?}"格式打印其项的可迭代的中转储(dumps)值:

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来编写这个泛型函数,因为它们不是任何trait的方法:大多数可迭代类型只是碰巧都有这些名称的方法.

drain方法(drain Methods)

许多集合类型提供了一个drain方法,该方法接受对集合的可变引用,并返回将每个元素的所有权传递给消费者的迭代器.但是,与into_iter()方法不同,后者通过值获取集合并使用它,而drain只是借用一个对集合的可变引用,当迭代器被删除时,它会从集合中移除任何剩余的元素,并将其保留为空.

对于可以通过范围(range)索引的类型,如String,向量和VecDeque,drain方法需要移除一系列元素,而不是排空整个序列:

use std::iter::FromIterator;

let mut outer = "Earth".to_string();
let inner = String::from_iter(outer.drain(1..4));

assert_eq!(outer, "Eh");
assert_eq!(inner, "art");

如果确实需要排空整个序列,请使用全范围的..作为参数.

其它迭代器源(Other Iterator Sources)

前面的部分主要涉及向量和HashMap等集合类型,但标准库中还有许多其他类型支持迭代.表15-1总结了更有趣的内容,但还有更多内容.我们将在专门针对特定类型的章节中更详细地介绍其中一些方法(即第16章,第17章和第18章).

表15-1. 标准库中的其他迭代器.

类型或trait 表达式 说明
std::ops::Range 1..10 端点必须是可迭代的整数类型.范围包括起始值,并不包括结束值.
std::ops::RangeFrom 1.. 无限次迭代.起始必须是整数.如果值达到类型的限制,可能会发生恐慌或溢出.
Option<T> Some(10).iter() 行为类似于长度为0(None)或1(Some(v))的向量.
Vec<T>,&[T] v.windows(16) 从左到右生成给定长度的每个连续切片.窗口重叠.
v.chunks(16) 从左到右生成给定长度的非重叠连续切片.
v.chunks_mut(1024) 类似chunks,但切片是可变的.
`v.split( byte
v.split_mut(...) 类似上一个,但产生可变切片.
v.rsplit(...) 类似split,但是从右到左产生切片.
v.splitn(n, ...) 类似split,但最多产生n个切片.
String,&str s.bytes() 生成UTF-8形式的字节
s.chars() 产生UTF-8表示的char.
s.split_whitespace() 按空格拆分字符串,并生成非空格字符的切片.
s.lines() 生成字符串行的切片.
s.split('/') 按给定模式拆分字符串,生成匹配之间的切片.模式可以是很多东西:字符,字符串,闭包.
s.matches(char::is_numeric) 生成与给定模式匹配的切片.
std::collections::HashMap,
std::collections::BTreeMap		 map.keys(),
map.values()		 生成对映射的键或值的共享引用.
map.values_mut() 生成对条目值的可变引用.
std::collections::HashSet,
std::collections::BTreeSet		 set1.union(set2) 生成对set1和set2的并集元素的共享引用.
set1.intersection(set2) 生成对set1和set2的交集元素的共享引用.
std::sync::mpsc::Receiver recv.iter() 生成从相应Sender的另一个线程发送的值.
std::io::Read stream.bytes() 从I/O流生成字节
stream.chars() 解析流为UTF-8并产生char
std::io::BufRead bufstream.lines() 解析流为UTF-8,生成行作为String
bufstream.split(0) 在给定字节上拆分流,产生字节间( inter-byte)Vec<u8>缓冲区.
std::fs::ReadDir std::fs::read_dir(path) 生成目录条目.
std::net::TcpListener listener.incoming() 生成传入的网络连接.
Free functions std::iter::empty() 立即返回None.
std::iter::once(5) 生成给定值,然后结束.
std::iter::repeat("#9") 永远产生给定的值

迭代器适配器(Iterator Adapters)

一旦掌握了迭代器,Iteratortrait提供了广泛的 适配器方法(adapter methods) 选择,或者只是 适配器(adapters) ,它们消费一个迭代器并构建一个具有有用行为的新迭代器.要了解适配器的工作原理,我们将展示如何使用两个最受欢迎的适配器.

map和filter(map and filter)

Iteratortrait的map适配器允许你通过对其项应用闭包来转换迭代器.filter适配器允许你从迭代器中过滤掉项,使用闭包来决定保留哪些项以及删除哪些项.

例如,假设你正在迭代文本行,并且想要省略每行的前导和尾随空格.标准库的str::trim方法从单个&str中删除前导和尾随空格,返回一个新的,修剪过的&str,它从原始中借用.你可以使用map适配器将str::trim应用于迭代器中的每一行:

let text = "  ponies  \n   giraffes\niguanas  \nsquid".to_string();
let v: Vec<&str> = text.lines()
    .map(str::trim)
    .collect();
assert_eq!(v, ["ponies", "giraffes", "iguanas", "squid"]);

text.lines()调用返回一个生成字符串行的迭代器.在该迭代器上调用map将返回第二个迭代器,该迭代器将str::trim应用于每一行,并将结果作为其项生成. 最后,collect将这些项收集到一个向量中.

当然,迭代器map返回本身就是进一步适应的候选者.如果要从结果中排除鬣蜥(iguanas),可以编写以下内容:

let text = "  ponies  \n   giraffes\niguanas  \nsquid".to_string();
let v: Vec<&str> = text.lines()
    .map(str::trim)
    .filter(|s| *s != "iguanas")
    .collect();
assert_eq!(v, ["ponies", "giraffes", "squid"]);

这里,filter返回第三个迭代器,它只生成map迭代器中的使闭包|s| *s != "iguanas"返回true的那些项.迭代器适配器链就像Unix shell中的管道:每个适配器都有一个单一的目的,当从左到右读取时,很清楚如何转换序列.

这些适配器的签名如下:

fn map<B, F>(self, f: F) -> some Iterator<Item=B>
    where Self: Sized, F: FnMut(Self::Item) -> B;

fn filter<P>(self, predicate: P) -> some Iterator<Item=Self::Item>
    where Self: Sized, P: FnMut(&Self::Item) -> bool;

我们用于返回类型的some Iterator <...>表示法是无效Rust(代码)1.真正的返回类型是不透明的struct类型,它们不提供信息;在实践中最重要的是这些方法返回具有给定Item类型的迭代器.

由于大多数适配器都是通过值接受self,因此它们要求Self是Sized(所有常见的迭代器都是).

map迭代器通过值将每个项传递给它的闭包,然后将闭包结果的所有权传递给它的消费者.filter迭代器通过共享引用将每个项传递给其闭包,在选择将项传递给其消费者时保留所有权.这就是为什么示例必须解引用s以将其与"iguanas"进行比较的原因:filter迭代器的项类型是&str,因此闭包的参数s的类型是&&str.

关于迭代器适配器,有两点需要注意.

首先,简单地在迭代器上调用适配器不会消耗任何项目;它只返回一个新的迭代器,准备根据需要通过从第一个迭代器中提取元素来生成自己的项.在适配器链中,实际完成任何工作的唯一方法是在最终迭代器上调用next.

所以在前面的例子中,方法调用text.lines()本身实际上并不解析字符串中的任何行;它只返回一个迭代器,如果请求到,它 将(would) 解析行.类似地,map和filter只返回新迭代器,如果要求到,它 将(would) 映射或过滤.在collect开始在filter迭代器上调用next之前,不会发生任何工作.

如果你使用有副作用的适配器,这一点尤为重要.例如,此代码根本不打印任何内容:

["earth", "water", "air", "fire"]
    .iter().map(|elt| println!("{}", elt));

iter调用返回一个数组的元素上的迭代器,map调用返回第二个迭代器,它将闭包应用于第一个迭代器生成的每个值.但是这里没有任何东西真正需要整个链的值,所以没有next方法会运行.事实上,Rust会警告你:

warning: unused result which must be used:
iterator adaptors are lazy and do nothing unless consumed
    |
387 | /         ["earth", "water", "air", "fire"]
388 | |             .iter().map(|elt| println!("{}", elt));
    | |___________________________________________________^
    |
= note: #[warn(unused_must_use)] on by default

错误消息中的术语"lazy(懒惰)"不是一个贬义词;它只是任何一种将计算推迟到需要其值时的机制的术语.Rust的惯例是,迭代器应该做最少的工作来满足对next的每次调用;在这个示例中,根本没有这样的调用,因此不进行任何工作.

第二个重点是迭代器适配器是零开销抽象.由于map,filter及它们的同伴是泛型的,因此将它们应用到迭代器上,可以为所涉及的特定迭代器类型提供专门的代码.这意味着Rust有足够的信息,可以将每个迭代器的next方法内联到其使用者中,然后将整个安排为一个单元转换为机器码.所以,我们之前展示的迭代器的lines/map/filter链和你手工可能编写的代码一样高效:

for line in text.lines() {
    let line = line.trim();
    if line != "iguanas" {
        v.push(line);
    }
}

本节的其余部分介绍Iteratortrait上可用的各种适配器.

filter_map和flat_map(filter_map and flat_map)

在每个传入项生成一个传出项的情况下,map适配器很好.但是,如果你想从迭代中删除某些项而不是处理它们,或者用零个或多个项替换单个项,该怎么办?filter_map和flat_map适配器为你提供了这种灵活性.

filter_map适配器类似于map,除了它允许其闭包将项转换为新项(如map那样)或从迭代中删除项.因此,它有点像filter和map的组合.其签名如下:

fn filter_map<B, F>(self, f: F) -> some Iterator<Item=B>
    where Self: Sized, F: FnMut(Self::Item) -> Option<B>;

这与map的签名相同,除了这里闭包返回Option<B>,而不是简单的B.当闭包返回None时,该项将从迭代中删除;当它返回Some(b)时,则b是filter_map迭代器产生的下一个项.

例如,假设你要扫描字符串以查找可以解析为数字的空格分隔的单词,并处理数字,删除其他单词.你可以写:

use std::str::FromStr;

let text = "1\nfrond .25  289\n3.1415 estuary\n";

for number in text.split_whitespace()
                  .filter_map(|w| f64::from_str(w).ok()) {
    println!("{:4.2}", number.sqrt());
}

这将打印以下内容:

1.00
0.50
17.00
1.77

给filter_map的闭包尝试使用f64::from_str解析每个空格分隔的切片.返回Result<f64, ParseFloatError>,其中.ok()变为Option<f64>:解析错误变为None,而成功的解析结果变为Some(v).filter_map迭代器删除所有None值,并为每个Some(v)生成值v.

但是将map和filter融合到这样的单个操作中的重点是什么,而不是直接使用这些适配器?filter_map适配器在刚刚展示的情况下显示其值,此时决定是否在迭代中包含项的最佳方法是实际尝试处理它.你可以只使用filter和map做同样的事情,但它有点笨拙:

text.split_whitespace()
    .map(|w| f64::from_str(w))
    .filter(|r| r.is_ok())
    .map(|r| r.unwrap())

你可以将flat_map适配器看作与map和filter_map相同的结构,只是现在闭包不仅可以返回一个项目(如map)或零或一个项目(如filter_map),还可以返回任意数量的项的序列.flat_map迭代器生成闭包返回的序列的连接.

flat_map的签名如下:

fn flat_map<U, F>(self, f: F) -> some Iterator<Item=U::Item>
    where F: FnMut(Self::Item) -> U, U: IntoIterator;

传递给flat_map的闭包必须返回一个可迭代的,但任何类型的可迭代的都可以.2

例如,假设我们有一个表格将国家映射到它们的主要城市.给定一个国家名单,我们如何迭代它们的主要城市?

use std::collections::HashMap;

let mut major_cities = HashMap::new();
major_cities.insert("Japan", vec!["Tokyo", "Kyoto"]);
major_cities.insert("The United States", vec!["Portland", "Nashville"]);
major_cities.insert("Brazil", vec!["São Paulo", "Brasília"]);
major_cities.insert("Kenya", vec!["Nairobi", "Mombasa"]);
major_cities.insert("The Netherlands", vec!["Amsterdam", "Utrecht"]);

let countries = ["Japan", "Brazil", "Kenya"];

for &city in countries.iter().flat_map(|country| &major_cities[country]) {
    println!("{}", city);
}

这将打印以下内容:

Tokyo
Kyoto
São Paulo
Brasília
Nairobi
Mombasa

一种看待这种情况的方法是,对于每个国家,我们检索其城市的向量,将所有向量连接在一起成为单个序列,并打印出来.

但请记住,迭代器是惰性的:它只是for循环对flat_map迭代器的next方法的调用,导致工作完成.完整的连接序列从来没有在内存中构建.相反,我们这里有一个小型状态机,它从城市迭代器中抽取,一次一项,直到它耗尽,然后才为下一个国家生成一个新的城市迭代器.效果是一个嵌套循环,但打包用作迭代器.

scan(scan)

scan适配器类似于map,只是闭包被赋予它可以参考的可变值,并且有提前终止迭代的选项.它接受一个初始状态值,然后是一个接受对状态的可变引用的闭包,以及来自底层迭代器的下一个项.闭包必须返回一个Option,scan迭代器将其作为下一个项.

例如,这是一个迭代器链,它对另一个迭代器的项进行平方,并在它们的总和超过10时终止迭代:

let iter = (0..10)
    .scan(0, |sum, item| {
        *sum += item;
        if *sum > 10 {
            None
        } else {
            Some(item * item)
        }
    });

assert_eq!(iter.collect::<Vec<i32>>(), vec![0, 1, 4, 9, 16]);

闭包的sum参数是对迭代器私有的值的可变引用,并初始化为scan的第一个参数--在本例中为0.闭包更新*sum,检查它是否已超出限制,并返回迭代器的下一个结果.

take和take_while(take and take_while)

Iteratortrait的take和take_while适配器允许你在一定数量的项之后结束迭代,或者当一个闭包决定关闭时.他们的签名如下:

fn take(self, n: usize) -> some Iterator<Item=Self::Item>
    where Self: Sized;

fn take_while<P>(self, predicate: P) -> some Iterator<Item=Self::Item>
    where Self: Sized, P: FnMut(&Self::Item) -> bool;

两者都获取迭代器的所有权并返回一个新的迭代器,该迭代器传递来自第一个的项,可能会提前结束序列.生成最多n个项,take迭代器返回None.take_while迭代器将predicate应用于每个项,并返回None代替predicate返回false的第一个项,以及每次后续调用next.

例如,给定一封电子邮件消息,其中有一个空行将标题和消息正文分开,你可以使用take_while迭代标题:

let message = "To: jimb\r\n\
               From: superego <editor@oreilly.com>\r\n\
               \r\n\
               Did you get any writing done today?\r\n\
               When will you stop wasting time plotting fractals?\r\n";
for header in message.lines().take_while(|l| !l.is_empty()) {
    println!("{}" , header);
}

回想一下第64页的"字符串字面量(String Literals)",当字符串中的一行以反斜杠结尾时,Rust不包含字符串中下一行的缩进,因此字符串中没有任何行具有任何前导空格.这意味着message的第三行是空白的.take_while适配器在看到该空行时立即终止迭代,因此此代码仅打印两行:

To: jimb
From: superego <editor@oreilly.com>

skip和skip_while(skip and skip_while)

Iteratortrait的skip和skip_while方法是take和take_while的补充:它们从迭代开始时删除一定数量的项,或者删除项直到闭包找到一个可接受的项,然后将其余项目保持不变.它们的签名如下:

fn skip(self, n: usize) -> some Iterator<Item=Self::Item>
    where Self: Sized;

fn skip_while<P>(self, predicate: P) -> some Iterator<Item=Self::Item>
    where Self: Sized, P: FnMut(&Self::Item) -> bool;

skip适配器的一个常见用途是在迭代程序的命令行参数时跳过命令名.在第2章中,我们最大的公约数计算器使用以下代码循环其命令行参数:

for arg in
 std::env::args().skip(1) {
    ...
}

std::env::args函数返回一个迭代器,它将程序的参数生成为String,第一个项是程序本身的名称.那不是我们想要在这个循环中处理的字符串.在该迭代器上调用skip(1)将返回一个新的迭代器,该迭代器在第一次调用时删除程序名,然后生成所有后续参数.

skip_while适配器使用闭包来决定从序列开头删除多少项.你可以迭代上一节中消息的正文行,如下所示:

for body in message.lines()
    .skip_while(|l| !l.is_empty())
    .skip(1) {
    println!("{}" , body);
}

这使用skip_while来跳过非空行,但是迭代器确实产生了空白行--毕竟,该行的闭包返回false.所以我们也使用skip方法来删除它,给我们一个迭代器,它的第一个项将是消息体的第一行.与上一节的message声明一起,此代码打印:

Did you get any writing done today?
When will you stop wasting time plotting fractals?

peekable(peekable)

一个可窥探(peekable)的迭代器可以让你偷看将生成的下一个项,而不会实际消耗它.你可以通过调用Iteratortrait的peekable方法将几乎所有迭代器转换为可窥探的迭代器:

fn peekable(self) -> std::iter::Peekable<Self>
    where Self: Sized;

这里,Peekable<Self>是一个实现Iterator<Item=Self::Item>的struct,Self是底层迭代器的类型.

Peekable迭代器有一个额外的方法peek,返回一个Option<&Item>:如果底层迭代器完成则返回None,否则返回Some(r)其中r是对下一个项的共享引用.(注意,如果迭代器的项类型已经是某个东西的引用,那么这最终会成为对引用的引用.)

调用peek尝试从底层迭代器中拉取下一个项,如果有,则将其缓存直到下一次调用next.Peekable上的所有其他Iterator方法都知道这个缓存:例如,可窥探迭代器iter上的iter.last()知道在耗尽底层迭代器后检查缓存.

当你在走得太远之前,无法决定从迭代器中消耗多少项时,可窥探迭代器是必不可少的.例如,如果你要解析字符流中的数字,则在看到后面的第一个非数字字符之前,你无法确定数字的结束位置:

use std::iter::Peekable;

fn parse_number<I>(tokens: &mut Peekable<I>) -> u32
    where I: Iterator<Item=char>
{
    let mut n = 0;
    loop {
        match tokens.peek() {
            Some(r) if r.is_digit(10) => {
                n = n * 10 + r.to_digit(10).unwrap()
            }
            _ => return n
        }
        tokens.next();
    }
}

let mut chars = "226153980,1766319049".chars().peekable();
assert_eq!(parse_number(&mut chars), 226153980);
// Look, `parse_number` didn't consume the comma! So we will.
assert_eq!(chars.next(), Some(','));
assert_eq!(parse_number(&mut chars), 1766319049);
assert_eq!(chars.next(), None);

parse_number函数使用peek来检查下一个字符,只有当它是一个数字时才使用它.如果它不是数字或迭代器耗尽(即,如果peek返回None),我们返回我们解析的数字并将下一个字符留在迭代器中,等待使用.

fuse(fuse)

一旦Iterator返回None,如果再次调用next方法,该trait就不会指定它行为应该怎样.大多数迭代器只返回None,但不是全部.如果你的代码依赖于该行为,你可能会感到惊讶.

fuse适配器接受任何迭代器并转为一个,一旦它第一次完成,肯定会继续返回None:

struct Flaky(bool);

impl Iterator for Flaky {
    type Item = &'static str;
    fn next(&mut self) -> Option<Self::Item> {
        if self.0 {
            self.0 = false;
            Some("totally the last item")
        } else {
            self.0 = true; // D'oh!
            None
        }
    }
}

let mut flaky = Flaky(true);
assert_eq!(flaky.next(), Some("totally the last item"));
assert_eq!(flaky.next(), None);
assert_eq!(flaky.next(), Some("totally the last item"));

let mut not_flaky = Flaky(true).fuse();
assert_eq!(not_flaky.next(), Some("totally the last item"));
assert_eq!(not_flaky.next(), None);
assert_eq!(not_flaky.next(), None);

fuse适配器可能在需要使用不确定来源的迭代器的泛型代码中最有用.而不是希望你必须处理的每个迭代器都表现良好,你可以使用fuse来确保.

可逆的迭代器和rev(Reversible Iterators and rev)

一些迭代器能够从序列的两端拉取项.你可以使用rev适配器来反转此类迭代器.例如,向量上的迭代器可以像从头开始一样容易地从向量的末尾拉取项.这样的迭代器可以实现std::iter::DoubleEndedIterator特性,它扩展了Iterator:

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

你可以把双端迭代器看成是有两个手指标记序列的当前正面和背面.从任一端拉取项将手指推向另一端;当两者相遇时,迭代完成:

use std::iter::DoubleEndedIterator;

let bee_parts = ["head", "thorax", "abdomen"];

let mut iter = bee_parts.iter();
assert_eq!(iter.next(),      Some(&"head"));
assert_eq!(iter.next_back(), Some(&"abdomen"));
assert_eq!(iter.next(),      Some(&"thorax"));

assert_eq!(iter.next_back(), None);
assert_eq!(iter.next(),      None);

切片上的迭代器结构体使得这种行为易于实现:它实际上是一对指向我们尚未生成的元素范围的开始和结束的指针;next和next_back只是从一个或另一个中拉取一个项.有序集合(如BTreeSet和BTreeMap)的迭代器也是双端的:它们的next_back方法首先拉取最大的元素或条目.通常,标准库在任何实际情况下都提供双端迭代.

但并非所有迭代器都可以这么容易地做到这一点:从其他线程到达通道的Receiver生成值的迭代器无法预测最后接收到的值可能是什么.通常,你需要检查标准库的文档,以查看哪些迭代器实现了DoubleEndedIterator,哪些没有.

如果迭代器是双端的,你可以使用rev适配器将其反转:

fn rev(self) -> some Iterator<Item=Self>
    where Self: Sized + DoubleEndedIterator;

返回的迭代器也是双端的:它的next和next_back方法只是交换:

let meals = ["breakfast", "lunch", "dinner"];

let mut iter = meals.iter().rev();
assert_eq!(iter.next(), Some(&"dinner"));
assert_eq!(iter.next(), Some(&"lunch"));
assert_eq!(iter.next(), Some(&"breakfast"));
assert_eq!(iter.next(), None);

大多数迭代器适配器,如果应用于可逆迭代器,则返回另一个可逆迭代器.例如,map和filter保留可逆性.

inspect(inspect)

inspect适配器用于调试迭代器适配器的管道,但在生产代码中使用不多.它只是将闭包应用于每个项的共享引用,然后传递该项.闭包不会影响项,但它可以执行打印或对它们进行断言等操作.

此示例显示将字符串转换为大写更改其长度的情况:

let upper_case: String = "große".chars()
    .inspect(|c| println!("before: {:?}", c))
    .flat_map(|c| c.to_uppercase())
    .inspect(|c| println!(" after:     {:?}", c))
    .collect();
assert_eq!(upper_case, "GROSSE");

小写德语字母"ß"的大写等价物是"SS",这就是char::to_uppercase返回字符迭代器,而不是单个替换字符的原因.上面的代码使用flat_map连接to_uppercase返回的所有序列为一个单个的String,打印为以下内容:

before: 'g'
 after:     'G'
before: 'r'
 after:     'R'
before: 'o'
 after:     'O'
before: 'ß'
 after:     'S'
 after:     'S'
before: 'e'
 after:     'E'

chain(chain)

chain适配器将一个迭代器附加到另一个迭代器.更准确地说,i1.chain(i2)返回一个迭代器,它从i1中拉取项直到它耗尽,然后从i2中拉取项.

chain适配器的签名如下:

fn chain<U>(self, other: U) -> some Iterator<Item=Self::Item>
    where Self: Sized, U: IntoIterator<Item=Self::Item>;

换句话说,你可以将迭代器与任何生成相同项类型的迭代链接在一起.

例如:

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

chain迭代器是可逆的.如果它的两个底层迭代器都是可逆的:

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

chain迭代器跟踪两个底层迭代器中的每一个是否返回None,并根据需要将next和next_back调用指向其中一个或另一个.

enumerate(enumerate)

Iteratortrait的enumerate适配器将一个运行索引附加到序列,使用生成项A, B, C, ...的迭代器并返回生成对(0, A), (1, B), (2, C)的迭代器.乍一看看起来微不足道,但经常出人意料地使用它.

消费者可以使用该索引将一个项与另一个项区分开来,并建立处理每个项的上下文.例如,第2章中的Mandelbrot集绘图器将图像分成8个水平条带,并将每个条带分配给不同的线程.该代码使用enumerate来告诉每个线程图像的哪个条带对应于它.

从矩形像素缓冲区开始:

let mut pixels = vec![0; columns * rows];

它使用chunks_mut将图像分割成水平带,每个线程一个:

let threads = 8;
let band_rows = rows / threads + 1;
...
let bands: Vec<&mut [u8]> = pixels.chunks_mut
(band_rows * columns).collect();

然后它遍历各个带,为每个带启动一个线程:

for (i, band) in bands.into_iter().enumerate() {
    let top = band_rows * i;
    // start a thread to render rows `top..top + band_rows`
}

每次迭代都得到一对(i, band),其中band是线程应该绘制的像素缓冲区的&mut [u8]切片,i是整个图像中该条带的索引,由enumerate适配器提供.给定绘图的边界和条带的大小,这就足够让线程确定它已被分配图像的哪个部分,从而确定要绘制到条带中的内容.

zip(zip)

zip适配器将两个迭代器组合成一个迭代器,该适配器器生成从每个迭代器中保存一个值的对,就像拉链(zipper)将其两侧连接成单个接缝一样.当两个底层迭代器中的任何一个结束时,拉链(zipped)迭代器结束.

例如,通过与另一个迭代器压缩半开范围0 ..,你可以获得与enumerate适配器相同的效果:

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

从这个意义上讲,你可以将zip视为enumerate的一般化:而enumerate将索引附加到序列,zip附加任意迭代器的项.我们之前建议,enumerate可以帮助提供处理项的上下文;zip是一种更灵活的方式来做同样的事情.

zip的参数不需要是迭代器本身;它可以是任何可迭代的:

use std::iter::repeat;

let endings = vec!["once", "twice", "chicken soup with rice"];
let rhyme: Vec<_> = repeat("going")
    .zip(endings)
    .collect();
assert_eq!(rhyme, vec![("going", "once"),
                       ("going", "twice"),
                       ("going", "chicken soup with rice")]);

by_ref(by_ref)

在本节中,我们一直在为迭代器附加适配器.一旦你这样做了,你能再次获取适配器吗?通常,不能:适配器获取底层迭代器的所有权,并且不提供任何方法来将其返还.

迭代器的by_ref方法借用了对迭代器的可变引用,以便你可以将适配器应用于引用.当你完成从这些适配器使用项时,你将删除它们,借用结束,并重新获得对原始迭代器的访问权限.

例如,在本章的前面我们展示了如何使用take_while和skip_while来处理邮件消息的标题行和正文.但是,如果你想使用相同的底层迭代器来同时处理两个呢?使用by_ref,我们可以使用take_while来处理消息头,完成后,返还底层迭代器,take_while已经完全处于正确位置以处理消息体:

let message = "To: jimb\r\n\
               From: id\r\n\
               \r\n\
               Oooooh, donuts!!\r\n";

let mut lines = message.lines();

println!("Headers:");
for header in lines.by_ref().take_while(|l| !l.is_empty()) {
    println!("{}" , header);
}

println!("\nBody:");
for body in lines {
    println!("{}" , body);
}

调用lines.by_ref()借用对迭代器的可变引用,并且take_while迭代器获取所有权的是这个引用.迭代器在第一个for循环结束时超出作用域,这意味着借用已经结束,因此可以在第二个for循环中再次使用lines.这将打印以下内容:

Headers:
To: jimb
From: id

Body:
Oooooh, donuts!!

by_ref适配器的定义很简单:它返回对迭代器的可变引用.然后,标准库包含这个奇怪的小实现:

impl<'a, I: Iterator + ?Sized> Iterator for 'a mut I {
    type Item = I::Item;
    fn next(&mut self) -> Option<I::Item> {
        (**self).next()
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        (**self).size_hint()
    }
}

换句话说,如果I是某一迭代器类型,那么&mut I也是一个迭代器,其next和size_hint方法遵从它的引用的对象.当你在对迭代器的可变引用上调用适配器时,适配器将获取 引用(reference) 的所有权,而不是迭代器本身.这只是一个借用,当适配器超出作用域时结束.

cloned(cloned)

cloned适配器接受生成引用的迭代器,并返回一个迭代器,该迭代器生成从这些引用克隆的值.当然,引用的对象的类型必须实现Clone.例如:

let a = ['1', '2', '3', '∞'];
assert_eq!(a.iter().next(),          Some(&'1'));
assert_eq!(a.iter().cloned().next(), Some('1'));

cycle(cycle)

cycle适配器返回一个迭代器,它无休止地重复由底层迭代器生成的序列.底层迭代器必须实现std::clone::Clone,这样cycle可以保存其初始状态,并在每次循环重新开始时重用它.

例如:

let dirs = ["North", "East", "South", "West"];
let mut spin = dirs.iter().cycle();
assert_eq!(spin.next(), Some(&"North"));
assert_eq!(spin.next(), Some(&"East"));
assert_eq!(spin.next(), Some(&"South"));
assert_eq!(spin.next(), Some(&"West"));
assert_eq!(spin.next(), Some(&"North"));
assert_eq!(spin.next(), Some(&"East"));

或者,对于非常无偿地使用迭代器:

use std::iter::{once, repeat};

let fizzes = repeat("").take(2).chain(once("fizz")).cycle();
let buzzes = repeat("").take(4).chain(once("buzz")).cycle();
let fizzes_buzzes = fizzes.zip(buzzes);

let fizz_buzz = (1..100).zip(fizzes_buzzes)
    .map(|tuple|
        match tuple {
            (i, ("", "")) => i.to_string(),
            (_, (fizz, buzz)) => format!("{}{}", fizz, buzz)
        });
for line in fizz_buzz {
    println!("{}", line);
}

这是一个儿童文字游戏,现在有时被用作编码员的面试问题,玩家轮流计数,用"fizz"替换任何可被3整除的数字,以及用"buzz"替换任何可被5整除的数字.被两者整除的数字变成了"fizzbuzz".

消费迭代器(Consuming Iterators)

到目前为止,我们已经介绍了创建迭代器,并适配它们为新的迭代器;在这里,我们通过展示消费它们的方法来完成这个过程.

当然,你可以用for循环消费迭代器,或者显式地调用next,但是有许多常见的任务你不应该一遍又一遍地写出来.Iteratortrait提供了广泛的方法选集来涵盖这些.

简单累加:count,sum,product(Simple Accumulation: count, sum, product)

count方法从迭代器中拉取项,直到它返回None,并告诉你它拿到多少.这是一个简短的程序,它计算其标准输入的行数:

use std::io::prelude::*;

fn main() {
    let stdin = std::io::stdin();
    println!("{}", stdin.lock().lines().count());
}

sum和product方法计算迭代器项的总和或乘积,它们必须是整数或浮点数:

fn triangle(n: u64) -> u64 {
    (1..n+1).sum()
}
assert_eq!(triangle(20), 210);

fn factorial(n: u64) -> u64 {
    (1..n+1).product()
}
assert_eq!(factorial(20), 2432902008176640000);

(你可以通过实现std::iter::Sum和std::iter::Producttraits来扩展sum和product以与其他类型一起使用,我们将在本书中对其进行描述.)

max, min(max, min)

Iterator上的min和max方法返回迭代器生成的最小项或最大项.迭代器的项类型必须实现std::cmp::Ord,以便可以将项相互比较.例如:

assert_eq!([-2, 0, 1, 0, -2, -5].iter().max(), Some(&1));
assert_eq!([-2, 0, 1, 0, -2, -5].iter().min(), Some(&-5));

这些方法返回一个Option<Self::Item>,这样如果迭代器没有产生任何项,它们就可以返回None.

正如第272页的"相等性测试(Equality Tests)"中所述,Rust的浮点类型f32和f64只实现了std::cmp::PartialOrd,而不是std::cmp::Ord,所以你不能使用min和max方法来计算一系列浮点数的最小值或最大值.这不是Rust设计的一个流行方面,而是它故意的:目前还不清楚这些函数应该如何处理IEEE NaN值.简单地忽略它们可能会掩盖代码中更严重的问题.

如果你知道如何处理NaN值,则可以使用max_by和min_by迭代器方法,这样你就可以提供自己的比较函数.

max_by, min_by(max_by, min_by)

max_by和min_by方法返回迭代器生成的最大项或最小项,由你提供的比较函数确定:

use std::cmp::{PartialOrd, Ordering};

// Compare two f64 values. Panic if given a NaN.
fn cmp(lhs: &&f64, rhs: &&f64) -> Ordering {
    lhs.partial_cmp(rhs).unwrap()
}

let numbers = [1.0, 4.0, 2.0];
assert_eq!(numbers.iter().max_by(cmp), Some(&4.0));
assert_eq!(numbers.iter().min_by(cmp), Some(&1.0));

let numbers = [1.0, 4.0, std::f64::NAN, 2.0];
assert_eq!(numbers.iter().max_by(cmp), Some(&4.0)); // panics

(cmp参数中的双引用是因为numbers.iter()产生对元素的引用,然后max_by和min_by将闭包引用传递给迭代器的项.)

max_by_key, min_by_key(max_by_key, min_by_key)

Iterator上的max_by_key和min_by_key方法允许你选择由应用于每个项目的闭包确定的最大项或最小项.闭包可以选择项的某个字段,或者对项执行计算.由于你经常对与某些最小值或最大值相关的数据感兴趣,而不仅仅是极值本身,因此这些函数通常比min和max更有用.它们的签名如下:

fn min_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item>
    where Self: Sized, F: FnMut(&Self::Item) -> B;

fn max_by_key<B: Ord, F>(self, f: F) -> Option<Self::Item>
    where Self: Sized, F: FnMut(&Self::Item) -> B;

也就是说,给定一个接受一个项并返回任何有序类型B的闭包,返回闭包返回的最大或最小的B项,如果没有生成项则返回None.

例如,如果你需要扫描城市的哈希表以查找人口最多和最小的城市,你可以写:

use std::collections::HashMap;

let mut populations = HashMap::new();
populations.insert("Portland",  583_776);
populations.insert("Fossil",        449);
populations.insert("Greenhorn",       2);
populations.insert("Boring",      7_762);
populations.insert("The Dalles", 15_340);

assert_eq!(populations.iter().max_by_key(|&(_name, pop)| pop),
           Some((&"Portland", &583_776)));
assert_eq!(populations.iter().min_by_key(|&(_name, pop)| pop),
           Some((&"Greenhorn", &2)));

闭包|&(_name, pop)| pop将应用于迭代器生成的每个项目,并返回用于比较的值--在本例中为城市的人口.返回的值是整个项,而不仅仅是闭包返回的值.(当然,如果你经常进行这样的查询,你可能希望安排一种更有效的方法来查找条目,而不是通过表格进行线性搜索.)

比较项目序列(Comparing Item Sequences)

你可以使用<和==运算符来比较字符串,向量和切片,假设可以比较各个元素.尽管迭代器不支持Rust的比较运算符,但它们确实提供了类似于eq和lt的方法来执行相同的工作,从迭代器中拉取成对项,并进行比较,直到能够做出决定为止.例如:

let packed =  "Helen of Troy";
let spaced =  "Helen   of    Troy";
let obscure = "Helen of Sandusky"; // nice person, just not famous

assert!(packed != spaced);
assert!(packed.split_whitespace().eq(spaced.split_whitespace()));

// This is true because ' ' < 'o'.
assert!(spaced < obscure);

// This is true because 'Troy' > 'Sandusky'.
assert!(spaced.split_whitespace().gt(obscure.split_whitespace()));

对split_whitespace的调用会返回在字符串的空格分隔的单词上的迭代器.在这些迭代器上使用eq和gt方法执行逐字(word-by-word)比较,而不是逐字符(character-by-character)比较.这些都是可能的,因为&str实现了PartialOrd和PartialEq.

迭代器提供用于相等性比较的eq和ne方法,以及用于有序比较的lt,le,gt和ge方法.cmp和partial_cmp方法的行为类似于Ord和PartialOrdtrait的相应方法.

any和all(any and all)

any和all方法对迭代器生成的每个项应用闭包,如果闭包对任意项或所有项返回true,则返回true:

let id = "Iterator";

assert!( id.chars().any(char::is_uppercase));
assert!(!id.chars().all(char::is_uppercase));

这些方法只消费确定答案所需的项数.例如,如果闭包已经对于给定的项返回true,则any立即返回true,而不从迭代器中再拉取任何项.

position,rposition,和ExactSizeIterator(position, rposition, and ExactSizeIterator)

position方法对迭代器中的每个项应用闭包,并返回闭包返回true的第一个项的索引.更准确地说,它返回索引的Option:如果闭包对于没有项返回true,则position返回None.一旦闭包返回true,它就会停止拉取项.例如:

let text = "Xerxes";
assert_eq!(text.chars().position(|c| c == 'e'), Some(1));
assert_eq!(text.chars().position(|c| c == 'z'), None);

除了从右边搜索之外,rposition方法是相同的.例如:

let bytes = b"Xerxes";
assert_eq!(bytes.iter().rposition(|&c| c == b'e'), Some(4));
assert_eq!(bytes.iter().rposition(|&c| c == b'X'), Some(0));

rposition方法需要一个可逆迭代器,以便它可以从序列的右端拉取项.它还需要一个精确大小的迭代器,以便它可以以与position相同的方式分配索引,从左侧的0开始.精确大小的迭代器是实现std::iter::ExactSizeIteratortrait的迭代器:

pub trait ExactSizeIterator: Iterator {
    fn len(&self) -> usize { ... }
    fn is_empty(&self) -> bool { ... }
}

len方法返回剩余的项数,如果迭代完成,则is_empty方法返回true.

当然,并非每个迭代器都提前知道它将生成多少项;在前面的例子中,&str上的chars迭代器不知道(UTF-8是一个可变宽度编码),所以你不能在字符串上使用rposition.但是,字节数组上的迭代器肯定知道数组的长度,因此它可以实现ExactSizeIterator.

fold(fold)

fold方法是一种非常通用的工具,用于在迭代器生成的整个项的序列上累加某种结果.给定一个初始值(我们称之为 累加器(accumulator) )和一个闭包,fold重复地将闭包应用于当前累加器和迭代器中的下一个项.闭包返回的值被视为新的累加器,将与下一个项一起传递给闭包.最终累加器值是fold本身返回的值.如果序列为空,则fold只返回初始累加器.

许多其他消费迭代器值的方法可以写成fold的用法:

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

// max
assert_eq!(a.iter().fold(i32::min_value(), |m, &i| std::cmp::max(m, i)),
           10);

fold方法的签名如下:

fn fold<A, F>(self, init: A, f: F) -> A
    where Self: Sized, F: FnMut(A, Self::Item) -> A;

这里,A是累加器类型.init参数是A,作为闭包的第一个参数和返回值,以及fold本身的返回值.请

注意,累加器值移入和移出闭包,因此你可以使用非Copy累加器类型的fold:

let a = ["Pack ", "my ", "box ", "with ",
         "five ", "dozen ", "liquor ", "jugs"];

let pangram = a.iter().fold(String::new(),
                            |mut s, &w| { s.push_str(w); s });
assert_eq
!(pangram, "Pack my box with five dozen liquor jugs");

nth(nth)

nth方法接受索引n,从迭代器中跳过许多项,并返回下一个项,如果序列在该点之前结束,则返回None.调用.nth(0)相当于.next().

它不像适配器那样获取迭代器的所有权,因此你可以多次调用它.

let mut squares = (0..10).map(|i| i*i);

assert_eq!(squares.nth(4), Some(16));
assert_eq!(squares.nth(0), Some(25));
assert_eq!(squares.nth(6), None);

它的签名如下所示:

fn nth(&mut self, n: usize) -> Option<Self::Item>
    where Self: Sized;

last(last)

last方法消费项,直到迭代器返回None,然后返回最后一项.如果迭代器没有生成任何项,则last返回None.其签名如下:

fn last(self) -> Option<Self::Item>;

例如:

let squares = (0..10).map(|i| i*i);
assert_eq!(squares.last(), Some(81));

这会从前面开始消费所有迭代器的项目,即使迭代器是可逆的.如果你有一个可逆迭代器并且不需要消费它的所有项,你应该只写iter.rev().next().

find(find)

find方法从迭代器中拉取项,返回给定闭包返回true的第一个项,如果序列在找到合适的项之前结束,则返回None.它的签名是:

fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
    where Self: Sized,
    P: FnMut(&Self::Item) -> bool;

例如,使用第347页的"max_by_key, min_by_key"中的城市和人口表,你可以写:

assert_eq!(populations.iter().find(|&(_name, &pop)| pop > 1_000_000),
           None);
assert_eq!(populations.iter().find(|&(_name, &pop)| pop > 500_000),
           Some((&"Portland", &583_776)));

表中没有一个城市人口超过一百万,但有一个城市有五十万人口.

构建集合:collect和FromIterator(Building Collections: collect and FromIterator)

在整本书中,我们一直在使用collect方法来构建包含迭代器项的向量.例如,在第2章中,我们调用std::env::args()来获取程序命令行参数的迭代器,然后调用迭代器的collect方法将它们收集到向量中:

let args: Vec<String> = std::env::args().collect();

但是collect并不是特定于向量的:事实上,它可以构建来自Rust的标准库的任何种类的集合,只要迭代器生成合适的项类型:

use std::collections::{HashSet, BTreeSet, LinkedList, HashMap, BTreeMap};

let args: HashSet<String> = std::env::args().collect();
let args: BTreeSet<String> = std::env::args().collect();
let args: LinkedList<String> = std::env::args().collect();

// Collecting a map requires (key, value) pairs, so for this example,
// zip the sequence of strings with a sequence of integers.
let args: HashMap<String, usize> = std::env::args().zip(0..).collect();
let args: BTreeMap<String, usize> = std::env::args().zip(0..).collect();

// and so on

当然,collect本身并不知道如何构建所有这些类型.相反,当某些集合类型(如Vec或HashMap)知道如何从迭代器构造自身时,它实现了std::iter::FromIteratortrait,对于它来说,collect只是一个方便的外表.

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

如果集合类型实现FromIterator<A>,则其静态方法from_iter从生成类型A的项的可迭代的构建该类型的值.

在最简单的情况下,此实现可以简单地构造一个空集合,然后逐个添加迭代器中的项.例如,std::collections::LinkedList的FromIterator实现以这种方式工作.

但是,某些类型可以做得更好.例如,从某些迭代器iter构造一个向量可以很简单:

let mut vec = Vec::new();
for item in iter {
    vec.push(item)
}
vec

但这并不理想:随着向量的增长,它可能需要扩展其缓冲区,需要调用堆分配器和现有元素的副本.向量确实采取算法措施来保持低开销,但如果有某种方法可以简单地分配一个正确大小的初始缓冲区,那么根本不需要调整大小.

这是Iteratortrait的size_hint方法的用武之地:

trait Iterator {
    ...
    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, None)
    }
}

此方法返回迭代器将生成的项数的下限和可选上限.默认定义返回零作为下限,并拒绝命名上限,实际上是说,"我不知道(I have no idea)",但许多迭代器可以做得比这更好.例如,Range上的迭代器确切地知道它将产生多少项,就像Vec或HashMap上的迭代器一样.这些迭代器为size_hint提供了自己的专用定义.

这些边界正是Vec的FromIterator实现需要的从一开始就正确调整新向量缓冲区大小的信息.插入仍然检查缓冲区是否足够大,因此即使提示不正确,也只会影响性能,而不是安全性.其它类型可以采取类似的步骤:例如,HashSet和HashMap也使用Iterator::size_hint为其哈希表选择合适的初始大小.

关于类型推断的一个注意事项:在本节的顶部,看到相同的调用std::env::args().collect(),根据其上下文生成四种不同的集合,这有点奇怪.collect的返回类型是其类型参数,因此前两个调用等效于以下内容:

let args = std::env::args().collect::<String>();
let args = std::env::args().collect::<HashSet<String>>();

The Extend trait(The Extend Trait)

如果一个类型实现了std::iter::Extend trait,那么它的extend方法会将一个可迭代的的项添加到集合中:

let mut v: Vec<i32> = (0..5).map(|i| 1 << i).collect();
v.extend(&[31, 57, 99, 163]);
assert_eq!(v, &[1, 2, 4, 8, 16, 31, 57, 99, 163]);

所有的标准集合都实现了Extend,所以它们都有这个方法;String也是如此.具有固定长度的数组和切片没有.

此trait的定义如下:

trait Extend<A> {
    fn extend<T>(&mut self, iter: T)
        where T: IntoIterator<Item=A>;
}

显然,这与std::iter::FromIterator非常相似:它创建了一个新集合,而Extend则扩展了现有集合.事实上,标准库中的几个FromIterator实现只是创建一个新的空集合,然后调用extend来填充它.例如, std::collections::LinkedList的Fromdterator实现以这种方式工作:

impl<T> FromIterator<T> for LinkedList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = Self::new();
        list.extend(iter);
        list
    }
}

partition(partition)

partition方法划分迭代器的项到两个集合中,使用闭包来决定每个项的所在位置:

let things = ["doorknob", "mushroom", "noodle", "giraffe", "grapefruit"];

// Amazing fact: the name of a living thing always starts with an
// odd-numbered letter.
let (living, nonliving): (Vec<&str>, _)
    = things.iter().partition(|name| name.as_bytes()[0] & 1 != 0);

assert_eq!(living,    vec!["mushroom", "giraffe", "grapefruit"]);
assert_eq!(nonliving, vec!["doorknob", "noodle"]);

像collect一样,partition可以制作你喜欢的任何类型的集合(尽管两者必须属于同一类型).和collect一样,你需要指定返回类型:前面的例子写出了living和nonliving的类型,并让类型推断为调用选择正确的类型参数.

partition的签名如下:

fn partition<B, F>(self, f: F) -> (B, B)
    where Self: Sized,
          B: Default + Extend<Self::Item>,
          F: FnMut(&Self::Item) -> bool;

而collect要求其结果类型来实现FromIterator,而partition要求std::default::Default,所有Rust集合都通过返回一个空集合来实现,和std::default::Extend.

为什么partition不将迭代器拆分为两个迭代器,而是构建两个集合?一个原因是从底层迭代器中拉取但尚未从适当的分区的迭代器中拉取的项需要在某处缓冲; 无论如何,你最终会在内部构建某种类型的集合.但更根本的原因与安全有关.将一个迭代器分区为两个迭代器需要两个分区共享相同的底层迭代器.迭代器必须是可变的才能使用;所以底层迭代器必然是共享的,可变的状态,那是Rust的安全性依赖所避免的.

实现你自己的迭代器(Implementing Your Own Iterators)

你可以为自己的类型实现IntoIterator和Iteratortrait,使本章中显示的所有适配器和消费者都可以使用,以及为使用标准迭代器接口而编写的许多其他库和crate代码.在本节中,我们将展示一个在范围(range)类型上简单的迭代器,然后是一个在二叉树类型上的更复杂的迭代器.

假设我们有以下范围(range)类型(从标准库的std::ops::Range<T>类型简化):

struct I32Range {
    start: i32,
    end: i32
}

迭代I32Range需要两个状态:当前值,以及迭代应该结束的限制.这恰好适合I32Range类型本身,使用start作为下一个值,并以end作为限制.所以你可以像这样实现Iterator:

impl Iterator for I32Range {
    type Item = i32;
    fn next(&mut self) -> Option<i32> {
        if self.start >= self.end {
            return None;
        }
        let result = Some(self.start);
        self.start += 1;
        result
    }
}

这个迭代器生成i32项,因此这是Item类型.如果迭代完成,则next返回None;否则,它会产生下一个值,并更新其状态以准备下一个调用.

当然,for循环使用IntoIterator::into_iter将其操作数转换为迭代器.但是标准库为每个实现Iterator的类型提供了一个IntIterator的全面实现,因此I32Range可以使用了:

let mut pi = 0.0;
let mut numerator = 1.0;

for k in (I32Range { start: 0, end: 14 }) {
    pi += numerator / (2*k + 1) as f64;
    numerator /= -3.0;
}
pi *= f64::sqrt(12.0);

// IEEE 754 specifies this result exactly.
assert_eq!(pi as f32, std::f32::consts::PI);

但是I32Range是一个特殊情况,因为可迭代的和迭代器是相同的类型.很多情况并非如此简单.例如,这是第10章中的二叉树类型:

enum BinaryTree<T> {
    Empty,
    NonEmpty(Box<TreeNode<T>>)
}

struct TreeNode<T> {
    element: T,
    left: BinaryTree<T>,
    right: BinaryTree<T>
}

遍历二叉树的经典方法是递归,使用函数调用堆栈来跟踪你在树中的位置以及尚未访问的节点.但是当为BinaryTree<T>实现Iterator时,每次调用next都必须产生一个值并返回.为了跟踪它尚未生成的树节点,迭代器必须维护自己的堆栈.这是BinaryTree的一种可能的迭代器类型:

use self::BinaryTree::*;

// The state of an in-order traversal of a `BinaryTree`.
structTreeIter<'a, T: 'a> {
    // A stack of references to tree nodes. Since we use `Vec`'s
    // `push` and `pop` methods, the top of the stack is the end of the
    // vector.
    //
    // The node the iterator will visit next is at the top of the stack,
    // with those ancestors still unvisited below it. If the stack is empty,
    // the iteration is over.
    unvisited: Vec<&'a TreeNode<T>>
}

事实证明，推入运行在子树的左边缘的节点是一种常见的操作,因此我们将在TreeIter上定义一个方法来执行此操作:

impl<'a, T: 'a> TreeIter<'a, T> {
    fn push_left_edge(&mut self, mut tree: &'a BinaryTree<T>) {
        while let NonEmpty(ref node) = *tree {
            self.unvisited.push(node);
            tree = &node.left;
        }
    }
}

使用这个辅助方法,我们可以给BinaryTree一个iter方法,它返回一个树上的迭代器:

impl<T> BinaryTree<T> {
    fn iter(&self) -> TreeIter<T> {
        let mut iter = TreeIter { unvisited: Vec::new() };
        iter.push_left_edge(self);
        iter
    }
}

iter方法构造一个空的TreeIter,然后调用push_left_edge来设置初始堆栈.根据unvisited堆栈的规则的要求,最左边的节点最终位于顶部.

遵循标准库的实践,然后我们可以通过调用BinaryTree::iter在树的共享引用上实现IntoIterator:

impl<'a, T: 'a> IntoIterator for &'a BinaryTree<T> {
    type Item = &'a T;
    type IntoIter = TreeIter<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

IntoIter定义将TreeIter建立为&BinaryTree的迭代器类型.

最后,在Iterator实现中,我们实际上遍历树,像BinaryTree的iter方法一样,迭代器的next方法是由栈的规则引导的:

impl<'a, T> Iterator for TreeIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        // Find the node this iteration must produce,
        // or finish the iteration.
        let node = match self.unvisited.pop() {
            None => return None,
            Some(n) => n
        };

    // The next node after this one is the leftmost child of
    // this node's right child, so push the path from here down.
    self.push_left_edge(&node.right);

    // Produce a reference to this node's value.
    Some(&node.element)
    }
}

如果堆栈为空,则迭代完成.否则,node是对现在要访问的节点的引用;此调用将返回对其element字段的引用.但首先,我们必须将迭代器的状态推进到下一个节点.如果此节点具有正确的子树,则要访问的下一个节点是子树的最左侧节点,我们可以使用push_left_edge将其及其未访问的祖先推送到堆栈.但是如果这个节点没有正确的子树,push_left_edge没有效果,这正是我们想要的:我们可以指望堆栈的新顶部是node的第一个未访问的祖先,如果有的话.

使用IntoIterator和Iterator实现,我们最终可以使用for循环通过引用迭代BinaryTree:

fn make_node<T>(left: BinaryTree<T>, element: T, right: BinaryTree<T>)
           -> BinaryTree<T>
{
    NonEmpty(Box::new(TreeNode { left, element, right }))
}

// Build a small tree.
let subtree_l = make_node(Empty, "mecha", Empty);
let subtree_rl = make_node(Empty, "droid", Empty);
let subtree_r = make_node(subtree_rl, "robot", Empty);
let tree = make_node(subtree_l, "Jaeger", subtree_r);

// Iterate over it.
let mut v = Vec::new();
for kind in &tree {
    v.push(*kind);
}
assert_eq!(v, ["mecha", "Jaeger", "droid", "robot"]);

图15-1显示了在我们遍历示例树时,unvisited堆栈的行为.在每个步骤中,要访问的下一个节点位于堆栈的顶部,所有未访问的祖先都在其下方.

图15-1.遍历二叉树.

所有常用的迭代器适配器和消费者都可以在我们的树上使用了:

assert_eq!(tree.iter()
           .map(|name| format!("mega-{}", name))
           .collect::<Vec<_>>(),
           vec!["mega-mecha", "mega-Jaeger","mega-droid", "mega-robot"]);

Footnotes

  1. Rust RFC1522将为语言添加语法,非常像我们的some Iterator表示法.在Rust 1.17中,它还没有被默认包含在语言中. ↩

  2. 实际上,由于Option是一个可迭代的,行为就像一个零个或一个项的序列, iterator.filter_map(closure)等效于iterator.flat_map(closure),假设闭包返回一个Option<T>. ↩