15. Iterators — 迭代器

迭代器是 Rust 中最核心的抽象之一——它统一了对序列数据的处理方式。Rust 的迭代器设计追求三个目标：懒惰求值（按需计算）、零成本抽象（编译后与手写循环一样快）和组合能力（通过适配器链表达复杂的数据转换逻辑）。本章从 Iterator trait 出发，系统覆盖迭代器的创建、转换、消费和自定义实现。

Iterator Trait

Iterator trait 的定义出奇地简洁：

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    // 还有 70+ 个默认方法
}

核心就是 next 方法——每次调用返回序列中的下一个元素，序列结束时返回 None。标准库为它提供了 70 多个默认方法，涵盖了过滤、映射、累积等常见操作。

for 循环的本质是对 IntoIterator 的语法糖：

// 你写的代码
for element in &collection {
    println!("{element}");
}

// 编译器展开为
let mut iterator = (&collection).into_iter();
while let Some(element) = iterator.next() {
    println!("{element}");
}

关键术语：

• 迭代器（Iterator）：任何实现了 Iterator 的类型
• 可迭代对象（Iterable）：任何实现了 IntoIterator 的类型
• Item：迭代器产生的值的类型
• 消费者（Consumer）：消费迭代器产生的值并产出最终结果的代码

IntoIterator Trait

IntoIterator 将类型转换为迭代器：

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

对于大多数集合，有三种 IntoIterator 实现——分别对应三种引用方式：

let v = vec![1, 2, 3, 4, 5];

// 共享引用遍历——产生 &i32
for item in &v {
    println!("{item}");
}

// 可变引用遍历——产生 &mut i32
for item in &mut v {
    *item += 10;
}

// 所有权遍历——产生 i32（消耗集合）
for item in v {
    println!("{item}");
}
// v 不再可用

并非所有集合都提供三种实现。HashSet、BTreeSet 和 BinaryHeap 不提供 &mut 版本的 IntoIterator——因为修改元素可能破坏集合的不变性约束（如哈希一致性、堆序）。

iter 和 iter_mut

大多数集合也暴露显式的 .iter() 和 .iter_mut() 方法：

let v = vec![1, 2, 3];

// v.iter() 返回 Iterator<Item = &i32>
// v.iter_mut() 返回 Iterator<Item = &mut i32>
// v.into_iter() 返回 Iterator<Item = i32>

let sum: i32 = v.iter().sum();
assert_eq!(sum, 6);

注意：&str 没有 .iter() 方法——用 .chars()（Unicode 字符迭代器）或 .bytes()（字节迭代器）代替。

创建迭代器

范围（Range）

// 标准范围
for i in 1..5 {       // 1, 2, 3, 4——不包括结尾
    println!("{i}");
}

for i in 1..=5 {      // 1, 2, 3, 4, 5——包括结尾
    println!("{i}");
}

for i in (1..).take(5) {  // 无界范围 + take
    println!("{i}");
}

from_fn 和 successors

std::iter::from_fn 接受一个返回 Option<T> 的闭包，每次调用产生一个新值：

use std::iter::from_fn;

// 生成 1000 个随机数
let lengths: Vec<f64> = from_fn(|| {
    Some((rand::random::<f64>() - rand::random::<f64>()).abs())
})
.take(1000)
.collect();

// 带状态的生成器——斐波那契数列
let mut state = (0u64, 1u64);
let fib: Vec<u64> = from_fn(|| {
    let (a, b) = state;
    state = (b, a + b);
    Some(a)
})
.take(10)
.collect();

assert_eq!(fib, vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]);

std::iter::successors 从前一个值推导下一个值：

use std::iter::successors;

// 幂序列：1, 2, 4, 8, 16, ...
let powers: Vec<u64> = successors(Some(1u64), |&n| Some(n * 2))
    .take(6)
    .collect();
assert_eq!(powers, vec![1, 2, 4, 8, 16, 32]);

drain

drain 允许在借用集合的同时移出元素，并从集合中删除它们：

let mut outer = "Earth".to_string();

// 取出索引 1..4 的字符
let inner: String = outer.drain(1..4).collect();

assert_eq!(outer, "Eh");     // 剩下的部分
assert_eq!(inner, "art");    // 取出的部分

当 drain 迭代器被丢弃时，所有剩余元素也从原集合中移除。

迭代器来源总览

来源类型	示例
范围	1..10, 1..=10, (1u64..)
Option<T>	opt.iter()
Result<T, E>	res.iter()
切片方法	.windows(n), .chunks(n), .split(pred)
字符串方法	.chars(), .bytes(), .split_whitespace(), .lines()
Map 方法	.keys(), .values(), .values_mut()
Set 方法	.union(), .intersection(), .difference()
I/O	BufRead::lines(), Read::bytes(), fs::read_dir()
网络	TcpListener::incoming()
通道	mpsc::Receiver::iter()
工厂函数	iter::empty(), iter::once(x), iter::repeat(x)

迭代器适配器（Lazy）

迭代器适配器不消费迭代器——它们返回包装了原始迭代器的新迭代器，在 next() 被调用时才执行转换。这种懒惰求值是 Rust 迭代器的核心设计原则。

map 和 filter

let text = "  hello\n  world  \n  iguanas  ";

let v: Vec<&str> = text
    .lines()                        // 按行分割
    .map(str::trim)                 // 去除空白
    .filter(|s| *s != "iguanas")   // 过滤掉 iguanas
    .collect();

assert_eq!(v, vec!["hello", "world"]);

map 的签名：

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

filter 的签名（注意 predicate 接受 &Self::Item 而非 Self::Item——这避免了所有权转移）：

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

关键警告：忘记消费迭代器是最常见的错误之一：

// 错误：什么都没发生！map 和 filter 是懒惰的
(1..=10).map(|n| println!("{n}"));

// 编译器警告：iterators are lazy and do nothing unless consumed

filter_map 和 flat_map

filter_map 结合了映射和过滤——闭包返回 Option，None 被丢弃：

let inputs = vec!["42", "hello", "7", "", "99"];

let numbers: Vec<i32> = inputs
    .iter()
    .filter_map(|s| s.parse::<i32>().ok())
    .collect();

assert_eq!(numbers, vec![42, 7, 99]);

flat_map 将每个元素映射为一个迭代器，然后将所有迭代器串联：

use std::collections::HashMap;

let mut cities = HashMap::new();
cities.insert("中国", vec!["北京", "上海", "广州"]);
cities.insert("日本", vec!["东京", "大阪", "京都"]);

let all_cities: Vec<&&str> = cities
    .values()
    .flat_map(|city_list| city_list.iter())
    .collect();

println!("{:?}", all_cities);
// ["北京", "上海", "广州", "东京", "大阪", "京都"]

flat_map 的等价手写循环要复杂得多——这正是迭代器“组合能力”的价值。

flatten

flatten 是 flat_map 的特化（恒等函数作为映射）：

let nested: Vec<Vec<i32>> = vec![
    vec![1, 2],
    vec![3, 4, 5],
    vec![6],
];

let flat: Vec<i32> = nested.into_iter().flatten().collect();
assert_eq!(flat, vec![1, 2, 3, 4, 5, 6]);

flatten 的巧妙用途——过滤 Option：

let options = vec![Some(1), None, Some(3), None, Some(5)];

// flatten 丢弃 None，展开 Some
let values: Vec<i32> = options.into_iter().flatten().collect();
assert_eq!(values, vec![1, 3, 5]);

take 和 skip

let v: Vec<i32> = (1..=10).take(5).collect();    // [1, 2, 3, 4, 5]
let v: Vec<i32> = (1..=10).skip(3).collect();    // [4, 5, 6, 7, 8, 9, 10]

take_while 和 skip_while 基于条件控制：

// 提取邮件头（直到空行为止的行）
let message = "From: alice\nTo: bob\n\nHello!\n";

let headers: Vec<&str> = message
    .lines()
    .take_while(|line| !line.is_empty())
    .collect();

assert_eq!(headers, vec!["From: alice", "To: bob"]);

peekable

允许在不消费的情况下偷看下一个元素：

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_ascii_digit() => {
                n = n * 10 + r.to_digit(10).unwrap();
            }
            _ => return n,
        }
        tokens.next();
    }
}

let chars = "123abc".chars();
let mut peekable = chars.peekable();
assert_eq!(parse_number(&mut peekable), 123);

// 剩余字符还在
let rest: String = peekable.collect();
assert_eq!(rest, "abc");

chain 和 enumerate

chain 连接两个迭代器：

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

enumerate 给每个元素附加索引：

let words = vec!["a", "b", "c"];
for (index, word) in words.iter().enumerate() {
    println!("第 {index} 个词：{word}");
}

// 等价于
for (index, word) in (0..).zip(words.iter()) {
    println!("第 {index} 个词：{word}");
}

zip

将两个迭代器配对，在任一迭代器结束时停止：

let endings = vec!["going", "gone"];
let lyrics: Vec<String> = std::iter::repeat("going")
    .zip(endings)
    .map(|(a, b)| format!("{} {}", a, b))
    .collect();

assert_eq!(lyrics, vec!["going going", "going gone"]);

by_ref

by_ref 允许在适配器之间共享同一个迭代器，而不会消耗它：

let message = "From: alice\nTo: bob\n\nHello!\nBody line 1\nBody line 2";
let mut lines = message.lines();

// 先读取头部（空行之前）
println!("Headers:");
for header in lines.by_ref().take_while(|l| !l.is_empty()) {
    println!("  {header}");
}

// lines 仍然可用——继续读取正文
println!("Body:");
for body_line in lines {
    println!("  {body_line}");
}

cloned 和 copied

let strings = vec!["hello".to_string(), "world".to_string()];

// cloned: 对引用调用 clone() 产生拥有值
let clones: Vec<String> = strings.iter().cloned().collect();

// copied: 只有 Copy 类型可用，等价于 .map(|&x| x)
let nums = vec![1, 2, 3];
let copies: Vec<i32> = nums.iter().copied().collect();

rev 和 fuse

rev 需要 DoubleEndedIterator（实现了 next_back 的迭代器）：

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

fuse 保证迭代器在第一次返回 None 后永远返回 None——解决某些迭代器在 None 后行为不一致的问题。

inspect

调试利器——在不修改数据流的情况下观察每个元素：

let result: i32 = (1..=5)
    .inspect(|n| println!("处理前: {n}"))
    .map(|n| n * n)
    .inspect(|n| println!("处理后: {n}"))
    .sum();

println!("结果: {result}");
// 输出：
// 处理前: 1 -> 处理后: 1
// 处理前: 2 -> 处理后: 4
// ...
// 结果: 55

迭代器消费者（Eager）

消费者是“终端操作”——它们消费迭代器，产出最终结果。

简单累积：count, sum, product

fn triangle(n: u64) -> u64 { (1..=n).sum() }
fn factorial(n: u64) -> u64 { (1..=n).product() }

assert_eq!(triangle(100), 5050);
assert_eq!(factorial(5), 120);

min, max

返回 Option<Self::Item>，需要 Ord trait。f32/f64 只有 PartialOrd，不能直接用：

let nums = vec![7, 2, 9, 1, 5];
assert_eq!(nums.iter().min(), Some(&1));
assert_eq!(nums.iter().max(), Some(&9));

// 浮点数需要用比较器
let floats = vec![1.5f64, 3.2, 0.8, 2.9];
let min_float = floats
    .iter()
    .min_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Less));
assert_eq!(min_float, Some(&0.8));

max_by_key, min_by_key

let cities = vec![
    ("北京", 21_540_000),
    ("上海", 24_870_000),
    ("拉萨", 900_000),
];

let largest = cities.iter().max_by_key(|&(_name, pop)| pop);
let smallest = cities.iter().min_by_key(|&(_name, pop)| pop);

assert_eq!(largest, Some(&("上海", 24_870_000)));
assert_eq!(smallest, Some(&("拉萨", 900_000)));

any 和 all

短路求值（short-circuit）：

let nums = vec![1, 3, 5, 7, 8, 9];

assert!(nums.iter().any(|&n| n % 2 == 0));   // 有偶数
assert!(!nums.iter().all(|&n| n % 2 == 1));   // 不全是奇数

find, position, rfind

let nums = vec![1, 3, 5, 7, 9];

let first_even = nums.iter().find(|&&n| n % 2 == 0);
assert_eq!(first_even, None);

let pos = nums.iter().position(|&n| n > 3);
assert_eq!(pos, Some(2));  // 索引 2 的值是 5

fold 和 rfold

fold 是最通用的累积操作——许多其它消费者都可以用它实现：

// fold 实现 count
let count = (1..=10).fold(0, |acc, _| acc + 1);

// fold 实现 sum
let sum = (1..=10).fold(0, |acc, n| acc + n);

// fold 构建字符串
let words = ["hello", "world", "rust"];
let sentence = words.iter().fold(String::new(), |mut acc, w| {
    acc.push_str(w);
    acc.push(' ');
    acc
});
assert_eq!(sentence.trim(), "hello world rust");

rfold 从右端开始累积，需要 DoubleEndedIterator。

try_fold

try_fold 支持提前退出——短路返回 Result::Err 或 Option::None：

let numbers = vec!["42", "7", "invalid", "99"];

let result: Result<Vec<i32>, _> = numbers
    .iter()
    .try_fold(Vec::new(), |mut acc, s| {
        let n = s.parse::<i32>()?;  // 遇到错误立即返回
        acc.push(n);
        Ok(acc)
    });

assert!(result.is_err());

collect 和 FromIterator

collect 是将迭代器转化为集合的“瑞士军刀”：

use std::collections::{HashSet, HashMap};

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

// 同一迭代器可以收集为不同类型
let set: HashSet<i32> = (1..=5).chain(3..=7).collect();
assert_eq!(set.len(), 7);  // 去重了

// 构建 HashMap
let map: HashMap<_, _> = vec![("a", 1), ("b", 2)]
    .into_iter()
    .collect();
assert_eq!(map.get("a"), Some(&1));

// 将 Result 迭代器收集为 Result<Vec>
let results = vec![Ok(1), Ok(2), Ok(3)];
let all: Result<Vec<i32>, &str> = results.into_iter().collect();
assert_eq!(all, Ok(vec![1, 2, 3]));

FromIterator trait 定义了 from_iter 方法，所有标准集合都实现了它。size_hint 提示帮助集合预分配容量：

let v: Vec<i32> = (0..1000).collect();
// collect 会调用 (0..1000).size_hint() 得到 (1000, Some(1000))
// Vec 据此预分配精确的容量

partition

按条件将元素分为两组：

let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];

let (evens, odds): (Vec<i32>, Vec<i32>) = numbers
    .into_iter()
    .partition(|n| n % 2 == 0);

assert_eq!(evens, vec![2, 4, 6, 8]);
assert_eq!(odds, vec![1, 3, 5, 7]);

for_each

对每个元素执行副作用：

(1..=5).for_each(|n| {
    println!("处理第 {n} 项");
});

for 循环 vs for_each：for 循环中可以提前 break 或 return，for_each 不行。但对于简单的元素遍历，for_each 与迭代器链更搭配。

实现自定义迭代器

简单范围迭代器

struct I32Range {
    start: i32,
    end: i32,
}

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

// 实现 Iterator 后，自动获得所有默认方法
// 同时也自动获得 IntoIterator——可以直接用于 for 循环
let range = I32Range { start: 1, end: 5 };
let squares: Vec<i32> = range.map(|n| n * n).collect();
assert_eq!(squares, vec![1, 4, 9, 16]);

二叉树的中序遍历迭代器

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

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

// 迭代器维护一个显式栈
struct TreeIter<'a, T> {
    unvisited: Vec<&'a TreeNode<T>>,
}

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

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

impl<'a, T> Iterator for TreeIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        let node = self.unvisited.pop()?;
        self.push_left_edge(&node.right);
        Some(&node.element)
    }
}

// 为二叉树的引用实现 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 {
        TreeIter::new(self)
    }
}

一旦实现了 Iterator，标准库的 70+ 个适配器和消费者全部可用了：

let tree = /* 构造二叉树 */;

// map, filter, collect 全部免费获得
let names: Vec<String> = tree
    .iter()
    .map(|node| format!("mega-{node}"))
    .filter(|name| name.len() > 5)
    .collect();

零成本抽象的原理

Rust 的迭代器被称为“零成本抽象”，因为在编译后它们与手写的 for 循环生成完全等价的机器码：

// 迭代器版本
let sum: i32 = (1..=1000).map(|n| n * n).filter(|n| n % 2 == 0).sum();

// 编译器在 release 模式下生成大致等价于
let mut sum = 0i32;
let mut n = 1i32;
while n <= 1000 {
    let squared = n * n;
    if squared % 2 == 0 {
        sum += squared;
    }
    n += 1;
}

以三角形数求和为例，编译器甚至能识别出数学恒等式：

fn triangle(n: i32) -> i32 {
    (1..=n).sum()
}
// Release 模式下编译为: n * (n + 1) / 2
// 一条乘法指令 + 几条位运算

迭代器与循环的对比

维度	迭代器	手写循环
可读性	声明式，数据流清晰	命令式，需要跟踪状态
组合能力	适配器链表达多步转换	嵌套循环 + 临时变量
性能	编译后与循环等价	—
边界检查	编译器可优化掉	有时保留检查
灵活性	受限于适配器 API	任意控制流
提前退出	需要 try_fold 等	break / return 直接

建议：能用迭代器就用迭代器。当逻辑复杂到适配器链难以表达时（多层循环、复杂条件分支），回退到循环。

小结

• Iterator trait 以 next() -> Option<Item> 为核心，标准库提供了 70+ 个默认方法。IntoIterator 将类型转换为迭代器——区分了共享引用、可变引用和所有权三种遍历模式。
• 迭代器适配器是懒惰的——map、filter、flat_map 等不立即执行，而是返回包装迭代器。只有调用消费者（collect、fold、sum 等）时，整个链路才被驱动执行。
• 零成本抽象——编译器将迭代器链完全内联展开为等价的手写循环代码，没有任何运行时开销。
• 组合能力是迭代器最大的优势——chain、zip、enumerate、flatten 等适配器可以自由组合表达复杂的数据转换流水线。
• 自定义迭代器只需实现一个 next 方法——然后标准库中所有适配器和消费者全部免费获得。