第六章集合与迭代器 (Collections and Iterators)

一、导读

1.1 本章学习目标

掌握 Rust 三大标准集合类型 Vec<T>、HashMap<K, V> 和 String 的完整 API 和使用模式

理解 Vec<T> 的内存布局、容量（capacity）与长度（length）的区别以及自动扩容机制

掌握 HashMap 的常用操作：插入、查询、更新、遍历，以及哈希冲突的处理策略

深入理解 Iterator trait 的设计哲学，掌握 next 方法与 Item 关联类型

熟练使用迭代器适配器（adaptor）：map、filter、fold、enumerate、zip 等

理解迭代器的惰性求值（lazy evaluation）特性及其性能优势

掌握 IntoIterator trait 与 for 循环的底层关系

能够在实际场景中合理选择集合类型并设计高效的迭代器链

1.2 为什么本章如此重要

集合和迭代器是日常 Rust 编程中使用频率最高的抽象。几乎所有涉及数据处理、转换和聚合的操作都离不开它们。Rust 标准库提供的集合类型虽然在数量上不如 C++ STL 或 Java Collections Framework 丰富，但每一个都经过精心设计，在安全性和性能之间取得了优秀的平衡。

迭代器是 Rust 函数式编程风格的核心载体。与命令式的 for 循环不同，迭代器链将数据转换表达为一系列声明式的操作组合。这种风格不仅代码更简洁，更重要的是——由于迭代器的惰性求值和编译期单态化，迭代器链在编译后通常会被优化为与手写循环相同的机器码，甚至更优。这就是 Rust "零成本抽象"理念的经典体现。

理解集合的内存模型对于编写高效的 Rust 程序至关重要。Vec<T> 的扩容策略、HashMap 的哈希算法选择、String 的 UTF-8 编码处理——这些底层细节直接影响程序的性能表现。同时，集合操作与所有权系统的交互也是本章的重点：当你从集合中取出元素时，是移动还是复制？当你遍历集合时，是借用还是获取所有权？这些选择决定了代码的正确性和效率。

1.3 核心问题引导

Vec<T> 在容量不足时如何扩容？扩容的时间复杂度是多少？为什么是均摊 O(1)？

HashMap 使用什么哈希算法？为什么 Rust 默认选择 SipHash 而非更快的算法？

迭代器的 map 和 for 循环在编译后生成的机器码有什么区别？

什么是"惰性求值"？为什么迭代器适配器不会立即执行？

iter()、iter_mut() 和 into_iter() 三种迭代方式有什么区别？

如何自定义一个迭代器？需要实现哪些 trait？

二、核心概念详解

6.1 Vec<T>：动态数组

Vec<T> 是 Rust 中最常用的集合类型，它在堆上分配连续内存，支持动态增长。

rust

let mut v: Vec<i32> = Vec::new();
v.push(1);
v.push(2);
v.push(3);

// 宏语法
let v = vec![1, 2, 3, 4, 5];

// 访问元素
let first = &v[0];          // 索引访问（越界会 panic）
let third = v.get(2);       // Option<&T>（安全访问）

// 遍历
for item in &v {
    println!("{}", item);
}

// 容量管理
let mut v = Vec::with_capacity(100); // 预分配容量
println!("len: {}, cap: {}", v.len(), v.capacity());

内存布局：Vec<T> 在栈上存储三个值——指向堆数据的指针、长度（len）和容量（capacity）。当 len == capacity 时，再次 push 会触发扩容：分配一块新的、更大的内存（通常是原来的 2 倍），将旧数据复制过去，然后释放旧内存。这个过程的均摊时间复杂度是 O(1)。

常用操作：pop（移除末尾）、insert（指定位置插入，O(n)）、remove（指定位置移除，O(n)）、retain（保留满足条件的元素）、sort（排序）、dedup（去重）。

6.2 HashMap<K, V>

HashMap<K, V> 存储键值对，通过哈希函数实现 O(1) 的平均查找时间。

rust

use std::collections::HashMap;

let mut scores = HashMap::new();
scores.insert("Alice", 95);
scores.insert("Bob", 87);

// 查询
if let Some(score) = scores.get("Alice") {
    println!("Alice 的分数: {}", score);
}

// 遍历
for (key, value) in &scores {
    println!("{}: {}", key, value);
}

// 更新
scores.entry("Charlie").or_insert(0);  // 不存在则插入
*scores.entry("Alice").or_insert(0) += 5; // 存在则更新

// 从 Vec 构建
let keys = vec!["a", "b", "c"];
let values = vec![1, 2, 3];
let map: HashMap<_, _> = keys.into_iter().zip(values.into_iter()).collect();

哈希算法：Rust 默认使用 SipHash，它不是最快的哈希算法，但能防止 HashDoS 攻击。对于不需要防攻击的场景（如内部数据结构），可以使用 FxHashMap（来自 rustc-hash crate）获得更好的性能。

要求：键类型必须实现 Eq 和 Hash trait。标准库中的基本类型、String、&str 等都默认实现了这两个 trait。

6.3 String 与字符串处理

String 是 Rust 中拥有所有权的 UTF-8 字符串。它与 &str（字符串切片）的关系类似于 Vec<T> 与 &[T]。

rust

let mut s = String::from("hello");
s.push_str(" world");
s.push('!');

// 格式化
let s = format!("{} {} {}", 1, 2, 3);

// 拼接
let s1 = String::from("hello");
let s2 = String::from("world");
let s3 = s1 + " " + &s2; // s1 被移动

// 遍历
for c in "你好世界".chars() {
    println!("{}", c);
}

for b in "hello".bytes() {
    println!("{}", b);
}

UTF-8 编码：Rust 的 String 是 UTF-8 编码的字节序列。一个 char 占用 4 字节，表示一个 Unicode 标量值。索引操作 s[i] 使用字节索引而非字符索引，因为 UTF-8 是变长编码，无法在 O(1) 时间内定位第 n 个字符。

6.4 迭代器深入

Iterator trait 只需要实现一个方法 next，其余方法都有默认实现：

rust

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

迭代器适配器（消耗迭代器，返回新迭代器）：

rust

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

let result: Vec<i32> = v.iter()
    .filter(|&&x| x % 2 == 0)   // 过滤偶数
    .map(|&x| x * x)             // 平方
    .take(3)                     // 取前3个
    .collect();                  // 收集为 Vec

println!("{:?}", result); // [4, 16, 36]

消费适配器（消耗迭代器，返回值）：

rust

let sum: i32 = (1..=100).sum();
let product: i32 = (1..=5).product();
let max = vec![3, 1, 4, 1, 5].iter().max();
let count = "hello world".chars().filter(|c| c.is_alphabetic()).count();
let found = vec![1, 2, 3].iter().any(|&x| *x == 2);
let all_positive = vec![1, 2, 3].iter().all(|&x| *x > 0);

fold：最通用的迭代器消费方法：

rust

let sum = vec![1, 2, 3, 4, 5].iter().fold(0, |acc, &x| acc + x);
let word_count = "hello world foo bar"
    .split_whitespace()
    .fold(HashMap::new(), |mut acc: HashMap<&str, i32>, word| {
        *acc.entry(word).or_insert(0) += 1;
        acc
    });

6.5 IntoIterator 与 for 循环

for 循环是 IntoIterator trait 的语法糖。for x in collection 在底层被转换为：

rust

let mut iter = IntoIterator::into_iter(collection);
loop {
    match iter.next() {
        Some(x) => { /* 循环体 */ }
        None => break,
    }
}

IntoIterator 为 &Vec<T>、&mut Vec<T> 和 Vec<T> 分别提供了实现，对应三种迭代方式：

rust

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

for x in &v { }       // 借用迭代：x 是 &i32
for x in &mut v { }   // 可变借用迭代：x 是 &mut i32
for x in v { }        // 获取所有权迭代：x 是 i32，v 被消耗

三、深入分析与讨论

3.1 迭代器的性能优势

Rust 的迭代器之所以被称为"零成本抽象"，是因为编译器能够将迭代器链优化为与手写循环相同的代码。这得益于两个关键特性：单态化和内联。

当迭代器链被编译时，编译器知道每个适配器的具体类型（因为泛型单态化），因此可以将 map、filter 等操作内联展开。最终生成的机器码通常是一个简单的循环，没有任何函数调用开销、堆分配或虚表查找。

相比之下，Java 的 Stream API 由于使用对象和虚方法，无法完全消除中间对象的创建和方法调用开销。这是 Rust 迭代器在性能上的根本优势。

3.2 集合选择策略

在实际项目中，选择合适的集合类型对性能有显著影响。Vec<T> 适合顺序访问和末尾操作；HashMap 适合键值查找；BTreeMap（有序映射）适合需要有序遍历的场景；HashSet 适合去重和成员检查。

当数据量较小（< 100 个元素）时，Vec 的线性搜索可能比 HashMap 的哈希查找更快，因为 Vec 的内存局部性更好，CPU 缓存命中率更高。在这种情况下，可以考虑使用 smallvec 或 tinyvec 等 crate。

3.3 迭代器链的设计模式

复杂的迭代器链应该拆分为有意义的步骤，而不是写成一个超长的链。使用中间变量命名每个步骤的结果，提高代码可读性。同时，注意 collect 的目标类型——Rust 的类型推断可以根据 collect 的返回类型推断整个链的类型。

四、实践案例

4.1 文本词频统计

使用集合和迭代器实现一个词频统计程序。

rust

use std::collections::HashMap;

fn word_frequency(text: &str) -> Vec<(&str, i32)> {
    let mut freq: HashMap<&str, i32> = HashMap::new();
    
    for word in text.split_whitespace() {
        let cleaned: String = word.chars()
            .filter(|c| c.is_alphanumeric())
            .collect();
        if !cleaned.is_empty() {
            *freq.entry(cleaned.to_lowercase().leak()).or_insert(0) += 1;
        }
    }
    
    let mut result: Vec<(&str, i32)> = freq.into_iter().collect();
    result.sort_by(|a, b| b.1.cmp(&a.1));
    result
}

fn main() {
    let text = "hello world hello rust world hello";
    let freq = word_frequency(text);
    for (word, count) in freq {
        println!("{}: {}", word, count);
    }
}

4.2 数据处理管道

使用迭代器链实现一个数据处理管道，展示各种适配器的组合使用。

rust

struct Student {
    name: String,
    scores: Vec<f64>,
}

impl Student {
    fn average(&self) -> f64 {
        if self.scores.is_empty() {
            return 0.0;
        }
        let sum: f64 = self.scores.iter().sum();
        sum / self.scores.len() as f64
    }
}

fn main() {
    let students = vec![
        Student { name: "Alice".into(), scores: vec![90.0, 85.0, 92.0] },
        Student { name: "Bob".into(), scores: vec![78.0, 82.0, 80.0] },
        Student { name: "Charlie".into(), scores: vec![95.0, 98.0, 96.0] },
        Student { name: "Diana".into(), scores: vec![88.0, 91.0, 87.0] },
    ];

    let honor_students: Vec<(&str, f64)> = students
        .iter()
        .map(|s| (s.name.as_str(), s.average()))
        .filter(|(_, avg)| *avg >= 85.0)
        .collect();

    let class_avg: f64 = students.iter().map(|s| s.average()).sum::<f64>()
        / students.len() as f64;

    println!("班级平均分: {:.1}", class_avg);
    println!("优秀学生:");
    for (name, avg) in &honor_students {
        println!("  {} - {:.1}", name, avg);
    }
}

五、常见误区与注意事项

索引越界 panic：使用 v[i] 访问 Vec 元素时，索引越界会导致 panic。对于不确定是否存在的情况，使用 v.get(i) 返回 Option<&T>。

在遍历中修改集合：不能在遍历 Vec 的同时修改它（借用检查器会阻止）。解决方案是先收集修改信息，再在循环外统一修改。

忽略迭代器的惰性：迭代器适配器（map、filter 等）不会立即执行，必须通过 collect、for、fold 等消费方法触发。忘记消费迭代器是常见的 Bug。

String 的索引操作：String 不支持 s[i] 字节索引的语义安全使用，因为 UTF-8 是变长编码。应使用 chars() 迭代字符或 bytes() 迭代字节。

HashMap 的性能陷阱：默认的 SipHash 对于非安全敏感场景可能过慢。在性能敏感的内部数据结构中，考虑使用 FxHashMap。

六、本章小结

本章系统讲解了 Rust 的集合类型和迭代器。Vec<T> 作为动态数组提供了高效的顺序存储和末尾操作；HashMap 提供了 O(1) 的键值查找；String 处理 UTF-8 编码的文本数据。迭代器是 Rust 函数式编程的核心，通过 Iterator trait 和丰富的适配器方法，可以构建声明式的数据处理管道。由于单态化和内联优化，迭代器链在编译后与手写循环具有相同的性能。理解集合的内存模型和迭代器的工作机制，是编写高效 Rust 代码的基础。

七、思考题与练习

实现一个函数，接受 Vec<i32> 参数，返回其中所有不重复元素的 Vec<i32>。要求不使用 HashSet，仅使用 Vec 的方法。

使用迭代器链实现 FizzBuzz：对于 1 到 100 的数，3 的倍数输出 "Fizz"，5 的倍数输出 "Buzz"，同时是 3 和 5 的倍数输出 "FizzBuzz"，否则输出数字。

解释 Vec::with_capacity 和普通 Vec::new 的区别。在什么场景下使用 with_capacity 能显著提升性能？

实现一个自定义迭代器 Fibonacci，生成 Fibonacci 数列。使其可以被 for 循环和 collect 使用。

使用 HashMap 实现一个简单的电话簿程序，支持添加、删除、查询和按姓名排序输出功能。

解释为什么 String 不支持 s[0] 获取第一个字符。如何实现获取第一个字符的功能？

使用 fold 实现一个函数，将 Vec<String> 合并为一个用逗号分隔的单个字符串（不使用 join）。

比较 iter()、iter_mut() 和 into_iter() 的区别。编写代码展示三种迭代方式的不同效果。

第六章 集合与迭代器 (Collections and Iterators)

一、导读

1.1 本章学习目标

1.2 为什么本章如此重要

1.3 核心问题引导

二、核心概念详解

6.1 Vec<T>：动态数组

6.2 HashMap<K, V>

6.3 String 与字符串处理

6.4 迭代器深入

6.5 IntoIterator 与 for 循环

三、深入分析与讨论

3.1 迭代器的性能优势

3.2 集合选择策略

3.3 迭代器链的设计模式

四、实践案例

4.1 文本词频统计

4.2 数据处理管道

五、常见误区与注意事项

六、本章小结

七、思考题与练习

第六章集合与迭代器 (Collections and Iterators)