掘金后端 ( ) • 2024-04-30 10:10

教程环境

系统：MacOS

Rust 版本：1.77.2

Rust 迭代器.png 迭代器是一个值，它可以生成一系列的值，通常用来执行循环操作。

Iterator 特型与 IntoIterator 特型

迭代器实现了 std::iter::Iterator 特型。

pub trait Iterator {
    type Item;

    // Required method
    fn next(&mut self) -> Option<Self::Item>;
    // other 75 methods
}

Item 是迭代器生成值的类型。next 方法返回迭代器的下一个值，或 None。

只要能用某种方式来迭代某种类型，该类型就可以实现 std::iter::IntoIterator，其 into_iter 方法会接受一个值并返回一个迭代器。

pub trait IntoIterator where Self::IntoIter: Iterator<Item=Self::Item> {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;

    // Required method
    fn into_iter(self) -> Self::IntoIter;
}

IntoIter是迭代器本身的类型，而 Item 是它生成的值的类型。任何实现了 IntoIterator 的类型都成为称为**可迭代者，**因为可以随意的迭代它。调用 into_iter 会返回一个迭代器。 Rust 的 for 循环会将这些部分很好的结合在一起。要遍历向量的元素，可以这样写：

fn main() {
    println!("Hello, world!");

    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);
}

迭代器相关的术语：

迭代器是实现了 Iterator 的任意类型。
可迭代者是任何实现了 IntoIterator 的类型：可以通过调用 into_iter 方法获得一个迭代器。
迭代器能生成值。
迭代器生成的值是条目。
接收迭代器所生成条目的代码是消费者。在这里，for 循环就是消费者。

创建迭代器

iter 方法与 iter_mut 方法

大多数集合类型都提供了 **iter**（迭代器）和**iter_mut**（可变迭代器）方法，它们会返回该类型的自然迭代器，为每个条目生成共享引用或可变引用。

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);

IntoIterator 的实现

一个类型实现了IntoIterator这个类型就是可迭代者，可以自行调用它的 into_iter 返回一个迭代器。大多数集合都提供了 IntoIterator 的几种实现，用于共享引用（&T）、可变引用（&mut T）和移动（T）的迭代器。

给定一个集合的共享引用，into_iter 会返回一个迭代器，该迭代器会生成对其条目的共享引用。
给定对集合的可变引用，into_iter 会返回一个迭代器，该迭代器会生成对其条目的可变引用。
当按值传递集合时，into_iter 会返回一个迭代器，该迭代器会获取集合的所有权并按值返回这些条目。这些条目的所有权会从集合转移给消费者，原始集合在此过程中已经被消耗掉了。

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

HashSet、BTreeSet和BinaryHeap没有在可变引用上实现 IntoIterator。 HashMap、BTreeMap会生成对其条目的可变引用，但只能提供对其键的共享引用。切片自己不拥有值，因此不存在按值传递的情况。

对于共享引用和可变引用，前两个 IntoIterator 变体等效于在引用目标上调用 iter或iter_mut。为什么 Rust 要提供 into_iter 和 iter 两种方式？

IntoIterator 是 for 循环工作的关键。for 循环会将 IntoIterator::into_iter 作为它的操作对象。
如果不用 for 循环时，favorites.iter() 比 (&favorites).into_iter() 更清晰。
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);
    }
}

from_fn 与 successors

给定返回 Option<T> 的函数， std::iter::from_fn会返回一个迭代器，该迭代器会调用回调来生成条目。

use std::iter::from_fn;
use rand::random;

fn main() {
    let lengths: Vec<f64> = from_fn(|| Some((random::<f64>() - random::<f64>()).abs()))
        .take(1000)
        .collect();
    println!("{:?}", lengths);
}

如果每一个条目都依赖前一个条目，使用 std::iter::successors 函数很实用。

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)
}

drain 方法

许多集合类型都提供了 drain（抽取）方法。接收一个集合的可变引用，并返回一个迭代器，该迭代器将每个元素的所有权传给消费者。与按值获取并消耗掉集合的 into_iter() 不同，drain只会借入对集合的可变引用，当迭代器被丢弃时，它会从集合中移除所有剩余元素以清空集合。对于可以按范围索引的类型（String、向量等），drain方法可指定要移除的元素范围，而不是抽干整个序列。

let mut outer = "Earth".to_string();
let inner = String::from_iter(outer.drain(1..4));
println!("outer: {outer}, inner: {inner}"); // outer: Eh, inner: art

其他迭代器源

标准库中的其他迭代器。截屏2024-04-12 13.09.19.png 截屏2024-04-12 13.10.29.png

迭代器适配器

一旦有了迭代器，它的 Iterator 特型就会提供大量的适配器方法（简称适配器）。

map 与 filter

map适配器能对迭代器的各个条目调用闭包来转换迭代器。 filter 适配器能使用闭包来帮你从迭代器中过滤某些条目。逐行遍历文本并去掉首位空格，并将 iguansa 过滤掉。

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

map会按值将每个条目传给闭包。 filter 会通过共享引用将每个条目传递给闭包。

⚠️要点：

单纯在迭代器上调用适配器不会消耗任何条目，只会返回一个新的迭代器。在适配器的适配链中，实际完成工作的唯一方法是在最终的迭代器上调用 next。
迭代器的适配器是一种零成本的抽象。由于 map、filter 和其他类似的适配器都是泛型的，因此将它们应用于迭代器就会专门针对所涉及的特定迭代器类型生成特化代码。

filter_map 与 flat_map

filter_map 和 map 类似，不同之处是 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);
}
// 1.00
// 0.25
// 289.00
// 3.14

flat_map也是类似的适配器，但是它可以一次返回任意数量的条目序列。flat_map 迭代器会生成此闭包返回的序列串联后的结果。

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

flatten - 展平

flatten会串联起迭代器的各个条目，这里假设每个条目都是可迭代的。也就是将二级结构展平为一级结构。

use std::collections::BTreeMap;

// 一个把城市映射为城市中停车场的表格：每个值都是一个向量
let mut parks = BTreeMap::new();
parks.insert("Portland",  vec!["Mt. Tabor Park", "Forest Park"]);
parks.insert("Kyoto",     vec!["Tadasu-no-Mori Forest", "Maruyama Koen"]);
parks.insert("Nashville", vec!["Percy Warner Park", "Dragon Park"]);

// 构建一个表示全部停车场的向量。`values`给出了一个能生成
// 向量的迭代器，然后`flatten`会依次生成每个向量的元素
let all_parks: Vec<_> = parks.values().flatten().cloned().collect();

assert_eq!(all_parks,
           vec!["Tadasu-no-Mori Forest", "Maruyama Koen", "Percy Warner Park",
                "Dragon Park", "Mt. Tabor Park", "Forest Park"]);”

flatten还有一个看似不寻常的用法。如果想从一个 Vec<Option<...>> 中迭代出 Some 值，可以使用 flatten。

assert_eq!(vec![None, Some("day"), None, Some("one")]
           .into_iter()
           .flatten()
           .collect::<Vec<_>>(),
           vec!["day", "one"]);

因为 Option 本身也是 IntoIterator，表示 0 个或 1 个元素组成的序列。

take 与 take_while

take和take_while的作用是当条目达到一定数量或闭包决定中止时结束迭代。 take会在最多生成 n 个条目后返回 None。 take_while迭代器会针对每个条目调用 predicate，并对 predicate 返回了 false 的首页条目以及其后的条目都返回 None。

skip 与 skip_while

skip 从迭代开始时就丢弃一定数量的值。 skip_while 则一直丢弃条目直到闭包终于找到一个可接受的条目为止，然后将剩下的条目按照原样传递。

peekable

peekable允许窥视即将生成的下一个条目，而无须实际消耗它。它有一个额外的方法 peek，该方法返回一个 Option<&Item>：如果底层迭代器消耗尽，返回值为 None；否则返回 Some(r)，r 是对下一个条目的共享引用。

use std::iter::Peekable;

fn main() {
    let mut chars = "226153980,1766319049".chars().peekable();
    println!("{}", parse_number(&mut chars)); // 226153980
    println!("{:?}", chars.next()); // Some(',')
    println!("{}", parse_number(&mut chars)); // 1766319049
    println!("{:?}", chars.next()); // None
}

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();
    }
}

fuse

fuse能接收任何适配器并生成一个确保第一次返回 None 后继续返回 None 的迭代器。

可逆迭代器与 rev

使用 rev 可反转迭代器。有的迭代器可以从序列的两端抽取条目，使用 rev 适配器可以反转此类迭代器。这样的迭代器实现 std::iter::DoubleEndedIterator 特型。

pub trait DoubleEndedIterator: Iterator {
    // Required method
    fn next_back(&mut self) -> Option<Self::Item>;

    // Provided methods
    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> { ... }
    fn nth_back(&mut self, n: usize) -> Option<Self::Item> { ... }
    fn try_rfold<B, F, R>(&mut self, init: B, f: F) -> R
       where Self: Sized,
             F: FnMut(B, Self::Item) -> R,
             R: Try<Output = B> { ... }
    fn rfold<B, F>(self, init: B, f: F) -> B
       where Self: Sized,
             F: FnMut(B, Self::Item) -> B { ... }
    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
       where Self: Sized,
             P: FnMut(&Self::Item) -> bool { ... }
}

next和next_back所做的只是从起始指针或结束指针提取一个条目。 BTreeSet和BTreeMap等有序集合的迭代器是双端的。

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");

chain

chain适配器会将一个迭代器追加到另一个迭代器后。a.chain(b)会返回一个迭代器，该迭代器从 a 中提取条目，然后从 b 中提取条目。

enumerate

enumerate会将运行索引附加到序列中。生成 (index, item) 或 (key, value)值。

zip

zip将两个迭代器组合成一个迭代器，新迭代器生成值对，每个底层迭代器各提供一个值。

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

zip 可以看作 enumerate 的泛化版本。 zip的参数本身不一样是迭代器，可以是任意可迭代者。

by_ref

前面的适配器附加到迭代器上之后，不能在取下适配器了。因为适配器会接收底层迭代器的所有权，并且没有提供归还所有权的方法。 迭代器的 **by_ref** 方法会借入迭代器的可变引用，便于将各种适配器应用于该引用。一旦消耗完适配器中的条目，就会丢弃这些适配器，借用也就结束了，之后可重新获取对原始迭代器的访问权。

let message = "To: jemb\r\n\
               From: id\r\n\
               \r\n\
               Oooooh, dounts!!\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);
}

// Headers:
// To: jemb
// From: id

// Body:
// Oooooh, dounts!!

cloned 与 copied

cloned会接受一个生成引用的迭代器，并返回一个会生成从这些引用克隆而来的值的迭代器。

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

copied设计思路一样，但是限制更严格，要求引用目标的类型必须实现了 Copy。

cycle

cycle会返回一个迭代器，会无限的重复底层迭代器生成的序列。底层迭代器必须实现 std::clone::Clone。

消耗迭代器

可以使用 for 循环，或显式调用 next。 Iterator 特型也通过了很多方法。

简单累加：count、sum、product

count从迭代器提取条目，知道迭代器返回None，并报告提取的条目数。 sum求和，计算迭代器条目之和。 product乘积，计算迭代器条目的乘集。

min 与 max

min 和 max 返回迭代器生成条目的最大值或最小值。

max_by 与 min_by

通过提供比较函数来确定最大或最小条目。

max_by_key 与 min_by_key

根据键值返回最大或最小条目。例如，要扫描城市哈希表，查找人口最多的城市或最少的城市。

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)));

对条目进行比较

迭代器的比较需要使用 eq、ne、lt、le、gt、ge 等方法。

any 与 all

any会将闭包应用于迭代器的每个条目。如果对任意的条目返回了 true，则返回 true。 all会将闭包应用与迭代器的每个条目。如果所有条目都返回了 true，则返回 true。 这两个方法都只会消耗确定答案所需的尽可能少的条目。

position、reposition 和 ExactSizeIterator

position 返回调用闭包第一个结果为 true 的条目的索引的 Option。如果没有任何条目返回 true，返回 None。 rposition 和 positon 类似，只是从右侧开始搜索。 rposition 要求使用可逆迭代器，以便它能从序列的右端提取条目。另外它要求这个迭代器是确切大小的。

确切大小的迭代器实现了 std::iter::ExactSizeIterator 特型。

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

len 方法返回剩余的条目数。 is_empty 方法会在迭代完成时候返回 true。

fold 与 rfold

fold（折叠）在迭代器生成的整个条目上累计某种结果。给一个初始值（累加器）和闭包，fold会以当前累加器和迭代器中的下一个条目为参数反复的调用闭包。闭包返回的值被视为新的累加器，并将其与下一个条目传给闭包。最终，返回累加器的值。如果序列为空，则 fold返回初始值。 rfold 从后往前处理。

try_fold 与 try_rfold

与 fold 基本相同，不过可以提前退出。

如果闭包返回的是 Result<T, E>，返回的是 Ok(v) 就继续累加，如果返回的是 Err(e)，就停止。最终返回的是 Result。
如果闭包返回的是 Option<T>，也是类似的。
闭包还可以返回 std::ops::ControlFlow 值。它是一个枚举，Continue(c) 和 Break(b)，分别表示使用新的累加值 c 或提前终止迭代。

nth 与 nth_back

nth接受索引参数 n，从迭代器跳过 n 个条目，返回下一个条目，如果提前结束了，返回 None。 .nth(0)等效于 .next()。

nth_back会从后往前提取。

last

last返回迭代器生成的最后一个条目，如果迭代器为空返回 None。它会从开始消耗所有的迭代器条目。如果有一个可逆的迭代器，不想消耗所有条目，可以使用 iter.next_back()。

find、rfind 和 find_map

find返回第一个满足闭包条件的条目，没有返回 None。 rfind从后往前搜索，返回最后一个满足闭包的条目。 find_map 和 find 类似，但是其闭包不会返回 bool，而是返回某个 Option。find_map 会返回第一个类型为 Some 的 Option。

构建集合：collect 与 Fromiterator

collect方法构建包含迭代条目的集合。实现了std::iter::FromIterator 特型的集合类型可从迭代器构造自身。

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

collect 就是对其的浅层包装。

Extend 特型

实现了std::iter::Extend特型，那么它的 extend 方法能将一些可迭代的条目添加到集合中。所有标准集合都实现了 Extend。String 也实现了。但具有固定长度的数组和切片没有实现。

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]);

partition

partition将迭代器条目分到两个集合中，使用闭包决定每个条目的归属。要求其结果类型实现了 std::default::Deafult。

for_each 与 try_for_each

for_each对每个条目调用闭包。 try_for_each 容错版本。

实现自己的迭代器

实现一个简单的迭代器，可以遍历范围类型。

fn main() {
    let mut  range = I32Range {
        start: 1,
        end: 3
    };
    println!("{:?}", range.next()); // Some(1)
    println!("{:?}", range.next()); // Some(2)
    println!("{:?}", range.next()); // Some(3)
    println!("{:?}", range.next()); // None

    // 标准库为每个实现了 Iterator 的类型都提供了 IntoIterator 的通用实现，所以 I32Range 可以直接使用
    for r in (I32Range{ start:0, end: 5 }) {
        println!("r: {}", r);
    }
}

struct I32Range {
    start: i32,
    end: i32
}

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

考链接：

https://kaisery.github.io/trpl-zh-cn/ch13-02-iterators.html

https://www.ituring.com.cn/book/2846

🌟 🙏🙏感谢您的阅读，如果对您有帮助，欢迎关注、点赞 🌟🌟