集合与容器

📚 Rust 课程系列
课程概览
基础语法（一）：变量、数据类型与字符串
切片（Slice）：序列的借用视图
基础语法（二）：运算符、表达式与控制流
函数与输入输出
所有权、借用与生命周期
结构体
枚举
模式匹配
类型系统：泛型、trait 与多态
集合与容器（本文）
错误处理与 Panic 恢复
模块、属性与宏
智能指针、迭代器与闭包
并发与异步编程
Unsafe Rust 与常用 trait 详解
工具链、Cargo 与外部 crate
最佳实践、性能与调试

集合（容器）是日常编程最常用的数据结构。本章先介绍语言内建的定长数组 [T; N] 与切片 &[T]（它们不属于集合库，却是理解一切序列容器的基础），再逐一介绍 std::collections 下的标准容器。各容器完整方法表见延伸阅读《Rust Containers》。

容器总览

类别	容器	特点
内建序列	`[T; N]`（数组）、`&[T]`（切片）	长度固定/借用视图，最基础的序列类型
序列	`Vec<T>`、`VecDeque<T>`、`LinkedList<T>`	按插入顺序存放，可按位置或顺序访问
映射	`HashMap<K,V>`、`BTreeMap<K,V>`	键值对，按键查找
集合	`HashSet<T>`、`BTreeSet<T>`	仅键，去重/成员判断
堆	`BinaryHeap<T>`	优先队列，快速取最值

Vec、HashMap、BTreeMap 覆盖了绝大多数场景；其余容器在特定需求下才登场。

创建时类型是如何确定的

容器都是泛型类型（Vec<T>、HashMap<K, V>），创建时必须同时确定容器种类和元素类型。Rust 通过以下途径确定它们，实际代码中常组合使用：

途径	写法示例	说明
类型标注	`let v: Vec<i32> = Vec::new();`	最直观
turbofish	`Vec::<i32>::new()`	标注在构造器/函数上
构造参数	`HashMap::from([("a", 1)])`	由实参推断
后续使用	先 `new()` 再 `push(1)`	编译器看整个函数体
默认回退	`vec![1, 2, 3]` → `Vec<i32>`	整数默认 `i32`，浮点默认 `f64`

// 1. 类型标注
let v: Vec<i32> = Vec::new();

// 2. turbofish：标注在构造函数上
let v = Vec::<i32>::new();

// 3. 构造参数推断
let m = HashMap::from([("a", 1)]); // HashMap<&str, i32>

// 4. 后续使用推断：编译器分析整个函数体
let mut v = Vec::new(); // 此刻 T 未知，先「挂起」
v.push(1);              // 由 push 的实参推断为 Vec<i32>

// 5. 默认回退：推断无其它约束时
let v = vec![1, 2, 3];    // Vec<i32>（整数默认 i32）
let v = vec![1.0, 2.0];   // Vec<f64>（浮点默认 f64）

几个容易踩坑的点：

元素必须同类型：vec![1, "a"] 编译报错。确需混合类型时，用枚举或 trait object（Vec<Box<dyn Trait>>）。
空容器且后续无使用——编译器永远无法确定元素类型，报 E0282: type annotations needed：

1
2
3

let v = Vec::new();       // ❌ 报错：T 无法确定
let v: Vec<i32> = Vec::new(); // ✅ 必须标注
let v: Vec<_> = vec![];   // ✅ 元素类型留待后续推断

collect() 天然歧义：迭代器可以收集成任意容器，必须给出目标类型。惯用写法是「标注容器种类，元素类型用 _ 交给推断」，turbofish 是等价写法：

1 2	`let s: HashSet<_> = [1, 2, 3].into_iter().collect(); let s = [1, 2, 3].into_iter().collect::<HashSet<_>>();`

默认值只在最后兜底：vec![1, 2, 3] 的 i32 并非创建那一刻就锁死——若后续把它当作 Vec<i64> 使用（如传给 fn f(v: Vec<i64>)），编译器会推断为 i64；只有当整个函数体都没有其它约束时，才回退到 i32/f64。

💡 提示：团队代码风格上，局部变量优先让编译器推断（后续使用/默认回退通常够用），只在空容器、collect()、歧义报错三种情况下显式标注，保持代码简洁。

数组 [T; N]：定长数组

数组是 Rust 内建的最基础序列类型：长度在编译期固定，通常分配在栈上（大数组可用 Box<[T; N]> 放到堆上）。

let a: [i32; 3] = [1, 2, 3];  // 显式标注类型与长度
let b = [1, 2, 3];            // 类型推断
let zeros = [0; 5];           // [0, 0, 0, 0, 0]

assert_eq!(a.len(), 3);
assert_eq!(a[0], 1);

长度 N 是类型的一部分：[i32; 3] 与 [i32; 4] 是不同类型，不能互相赋值。
索引越界：编译期常量下标越界直接编译报错；运行期下标越界则 panic。

⚠️ 注意：数组长度固定，不能 push/pop。需要动态增长时用 Vec——Vec 实质就是「容量可增长的堆上数组」。

切片 &[T]：借用视图

切片 &[T] 是对数组（或 Vec）一段连续元素的借用，长度在运行期确定（切片完整讨论见《切片（Slice）》）。函数参数用 &[T] 可同时接受数组和 Vec：

fn sum(xs: &[i32]) -> i32 {
  xs.iter().sum()
}

let a = [1, 2, 3];
let v = vec![1, 2, 3];
assert_eq!(sum(&a), 6);      // 数组自动转切片
assert_eq!(sum(&v), 6);      // Vec 同样适用
assert_eq!(sum(&a[1..]), 5); // 子切片

💡 提示：只读参数优先写 &[T] 而非 &Vec<T>——后者强迫调用方使用 Vec，而前者数组、Vec、切片都接受，更通用（字符串同理用 &str 而非 &String）。

数组与切片常用操作

以下方法实现于切片类型 [T]，数组和 Vec 都可直接调用：

操作	方法	备注
重叠窗口	`windows(n)`	如 `[1,2]` `[2,3]` 依次滑动
不重叠分块	`chunks(n)`	常用于并行/分批处理
排序	`sort()` / `sort_by(f)`	原地排序，需可变引用
二分查找	`binary_search(&x)`	要求已排序
切分	`split_at(i)` / `split_first()`	返回两个子切片
元素映射	`arr.map(f)`	数组专属，逐元素转换返回新数组

🔬 进阶：[T; N] 中的 N 是 const 泛型参数。自 Rust 1.51 起数组对任意 N 实现了常用 trait，因此可以写长度泛型函数 fn f<const N: usize>(a: [i32; N])，无需再为每种长度分别实现。

🔄 对比：Rust 数组 ≈ C 数组 / Go 数组，长度编译期确定、值语义。与 C 的关键区别是 Rust 数组不会「衰减」为指针——长度信息始终保留在类型里，天然杜绝了 C 中传参丢失长度的问题。

Vec<T>：动态数组

Vec<T> 是最常用的容器，在堆上存储连续的同类型元素，容量随需增长。

1 2	`let mut v = Vec::new(); v.push(1);`

创建：vec! 宏

vec! 是创建 Vec 的宏，有两种形式：

let v1 = vec![1, 2, 3];     // 枚举元素
let v2 = vec![0; 5];        // [0, 0, 0, 0, 0]
let v3: Vec<i32> = vec![];  // 空 Vec 需类型标注

// 嵌套出二维结构
let grid = vec![vec![0; 3]; 2]; // 2 行 3 列全 0

要点：

vec![elem; n] 要求 elem: Clone：elem 只求值一次，然后克隆 n 份。写 vec![String::new(); 3] 得到 3 个独立的空字符串。
vec! 只是语法糖，vec![1, 2, 3] 大致展开为「先建数组再转 Vec」，容量恰好等于长度——之后第一次 push 就会触发重分配。已知后续还要追加元素时，改用 with_capacity 或 Vec::from([..]) 再 reserve 更划算。
与数组字面量 [1, 2, 3] 的区别：vec! 在堆上分配、长度可变；数组在栈上、长度固定。需要栈上定长时用数组字面量即可，无需宏。

⚠️ 注意：初始化集合类容器没有类似的宏——HashMap/HashSet 只能用 HashMap::from([("a", 1)]) 或 insert 循环，想要 map!{} 语法需第三方 crate（如 maplit）。

容量与增长策略：Vec 内部维护「容量」（已分配槽位数）和「长度」（实际元素数）。当长度超过容量时，Vec 重新分配更大的内存（通常翻倍）并搬移旧元素。因此 push 是 O(1) 均摊成本，但偶发的重分配会带来一次 O(n) 拷贝。

💡 提示：当已知大小时使用 Vec::with_capacity(n) 预分配以避免重复分配——这是 Vec 最常见的性能优化手段。

1
2
3

let mut v = Vec::with_capacity(1000); // 一次性分配
for i in 0..1000 { v.push(i); }
v.shrink_to_fit(); // 归还多余容量

访问与删除速查：

操作	方法	复杂度	备注
索引访问	`v[i]`	O(1)	越界 panic
安全访问	`v.get(i)`	O(1)	返回 `Option<&T>`
末尾删除	`pop()`	O(1)	返回 `Option<T>`
中间删除	`remove(i)`	O(n)	后续元素前移
中间删除	`swap_remove(i)`	O(1)	与末尾交换后 pop，不保序

⚠️ 注意：swap_remove 虽然是 O(1)，但会打乱元素顺序。需要保序时只能用 remove。

🔄 对比：Rust 的 Vec ≈ C++ 的 std::vector / Go 的 slice / Java 的 ArrayList，但所有权系统保证不会出现悬空引用——持有 &v[i] 时编译器会阻止 push 新元素（因为 push 可能触发重分配使引用失效）。

VecDeque<T>：双端队列

VecDeque 基于环形缓冲（ring buffer），两端插入/删除都是 O(1) 均摊。适合队列、滑动窗口等场景：

use std::collections::VecDeque;

let mut deque = VecDeque::new();
deque.push_back(2);
deque.push_front(1);     // [1, 2]
deque.push_back(3);      // [1, 2, 3]
assert_eq!(deque.pop_front(), Some(1));
assert_eq!(deque.pop_back(), Some(3));

💡 提示：需要 FIFO 队列时优先选 VecDeque 而非 Vec——Vec 的 remove(0) 是 O(n)，而 VecDeque 的 pop_front 是 O(1)。

HashMap<K, V>：哈希表

HashMap 用哈希表实现键值映射，平均 O(1) 的查找/插入/删除，但无序。

1
2
3

use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);

⚠️ 注意：键类型必须实现 Hash + Eq。所有整数、String/&str、元组（元素均实现 Hash+Eq）等自动满足；自定义类型需 derive 或手动实现。

哈希算法（进阶）

默认使用 SipHash-1-3，抗哈希碰撞攻击（防止恶意输入触发最坏 O(n) 退化），但相对慢。若性能敏感且键可信，可换更快的 hasher：

1 2	`use std::hash::BuildHasherDefault; type FastMap<K, V> = HashMap<K, V, BuildHasherDefault<fnv::FnvHasher>>;`

🔄 对比：Go 的 map 和 Java 的 HashMap 也使用类似策略，但 Rust 默认选择安全优先的 SipHash，而 C++ std::unordered_map 默认哈希函数不抗碰撞攻击。

Entry API

entry API 是 HashMap 最惯用的技巧——一次查找完成「存在则读，不存在则写」，避免重复查找：

let mut counts: HashMap<&str, u32> = HashMap::new();
for word in ["a", "b", "a", "c", "b", "a"] {
    *counts.entry(word).or_insert(0) += 1; // 不存在则插入 0
}
// {"a": 3, "b": 2, "c": 1}

💡 提示：or_insert(v) 总会求值 v（即使键已存在）；若默认值计算昂贵，用 or_insert_with(|| expensive()) 只在需要时才计算。值为 Default 时可用 or_default() 更简洁。

BTreeMap<K, V>：有序映射

BTreeMap 基于 B 树，按键有序排列，查找/插入/删除为 O(log n)，支持按范围遍历。当需要按键排序或范围查询时用它替代 HashMap：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert("banana", 2);
map.insert("apple", 5);
map.insert("cherry", 3);

for (k, v) in &map { /* 按 key 字典序：apple, banana, cherry */ }

// 范围查询
for (k, v) in map.range("apple".."cherry") { /* [apple, banana) */ }

⚠️ 注意：键类型必须实现 Ord。BTreeMap 的插入/删除比 HashMap 慢（O(log n) vs O(1) 均摊），但遍历有序且无哈希开销。不需要顺序时优先用 HashMap。

🔄 对比：BTreeMap ≈ C++ 的 std::map / Java 的 TreeMap，但 B 树节点通常比 C++ 红黑树节点缓存更友好（B 树节点存多个元素）。

HashSet 与 BTreeSet

HashSet<T> 和 BTreeSet<T> 分别是 HashMap<T, ()> 和 BTreeMap<T, ()> 的集合版本，只存键，用于去重与成员判断：

use std::collections::HashSet;

let mut set = HashSet::new();
set.insert(1);
set.insert(2);
set.insert(1); // 重复，返回 false
assert_eq!(set.len(), 2);

// 集合运算
let a: HashSet<_> = [1, 2, 3].into_iter().collect();
let b: HashSet<_> = [2, 3, 4].into_iter().collect();
let inter: HashSet<_> = a.intersection(&b).cloned().collect();   // {2, 3}
let union:  HashSet<_> = a.union(&b).cloned().collect();         // {1,2,3,4}
let diff:   HashSet<_> = a.difference(&b).cloned().collect();    // {1}

💡 提示：集合运算返回的是引用的迭代器，需要 .cloned().collect() 才能得到新的 HashSet。BTreeSet 同样支持 intersection/union/difference/symmetric_difference，且结果保持有序。

LinkedList<T>：双向链表（慎用）

LinkedList<T> 两端 O(1) 操作，但缓存不友好、随机访问 O(n)。绝大多数「想用链表」的场景用 Vec/VecDeque 更快更简单。

⚠️ 注意：LinkedList 主要在需要频繁从中间拆分/拼接（split_off/append）时才考虑。官方也建议谨慎使用——所有权模型使链表操作比 C/C++ 更繁琐（需要 unsafe 或 Rc<RefCell<>> 才能实现双向引用）。

🔄 对比：C++ 的 std::list 在中间插入 O(1) 常被使用，但 Rust 的 LinkedList 因所有权限制几乎无法直接操作中间节点，实用性远低于 C++ 版本。

BinaryHeap<T>：二叉堆

BinaryHeap<T> 是最大二叉堆，常作优先队列：peek O(1)，push/pop O(log n)。

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(2);
assert_eq!(heap.peek(), Some(&3)); // 最大值在堆顶
assert_eq!(heap.pop(), Some(3));   // 按降序弹出

要最小堆或自定义顺序，用 Reverse 包装或实现自定义 Ord：

use std::cmp::Reverse;
let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(3));
min_heap.push(Reverse(1));
assert_eq!(min_heap.pop(), Some(Reverse(1))); // 最小值

💡 提示：BinaryHeap 要求元素实现 Ord。自定义优先级时，推荐用 Reverse 包装（零开销）而非实现反向 Ord——后者容易在别处引起混淆。

性能对比

容器	索引/查找	插入/删除	备注
`[T; N]`	O(1) 索引	不支持	长度固定，栈上分配
`Vec<T>`	O(1) 索引	末尾 O(1) 均摊；中间 O(n)	连续内存，缓存友好
`VecDeque<T>`	O(1) 索引	两端 O(1) 均摊；中间 O(n)	环形缓冲
`HashMap<K,V>`	O(1) 均摊	O(1) 均摊	无序，需 `Hash` + `Eq`
`BTreeMap<K,V>`	O(log n)	O(log n)	有序，需 `Ord`
`HashSet`/`BTreeSet`	同对应 Map	同对应 Map	无值
`LinkedList<T>`	O(n)	两端 O(1)；中间 O(1)（已知游标）	缓存不友好，慎用
`BinaryHeap<T>`	peek O(1)	push/pop O(log n)	最大堆

选用指南

需求	推荐
元素数量固定、编译期已知	`[T; N]` 数组（函数参数用 `&[T]`）
一组同类型元素，按下标访问	`Vec`
两端频繁增删（队列/滑动窗口）	`VecDeque`
键值映射、查找为主、不关心顺序	`HashMap`
键值映射、需要按键排序或范围查询	`BTreeMap`
去重 / 成员判断 / 集合运算	`HashSet`（无序）或 `BTreeSet`（有序）
取最值 / 优先队列	`BinaryHeap`
频繁从中间拆分/拼接	`LinkedList`（默认优先考虑 `Vec`）

并发集合

标准库的集合不是线程安全的——它们没有实现内部同步，跨线程共享可变集合需要外部锁。

use std::sync::{Arc, Mutex};
use std::collections::HashMap;

let counts = Arc::new(Mutex::new(HashMap::<u32, u32>::new()));
let c = Arc::clone(&counts);
std::thread::spawn(move || {
    let mut m = c.lock().unwrap();
    *m.entry(1).or_insert(0) += 1;
});

⚠️ 注意：Arc<Mutex<HashMap<...>>> 简单但锁粒度粗，竞争激烈时性能差。读多写少可用 Arc<RwLock<...>>，但注意 RwLock 可能导致写饥饿。

🔬 进阶：更高吞吐可使用第三方并发数据结构如 dashmap，它采用分片锁（sharded locking）显著降低锁竞争：

1
2
3

use dashmap::DashMap;
let map = DashMap::new();
map.insert("a", 1); // 多线程可直接并发写入，无需外部 Mutex

🔄 对比：Java 有 ConcurrentHashMap、Go 有 sync.Map，Rust 标准库没有内置并发 map——这是 Rust 的设计哲学：零成本抽象意味着不为单线程场景支付同步开销，并发需求交给第三方 crate。

与迭代器配合

集合与迭代器适配器天然契合，collect() 可把迭代器结果收集回任意实现了 FromIterator 的集合：

let v = vec![1, 2, 3, 4, 5];
let doubled: Vec<i32> = v.iter().map(|x| x * 2).collect();
let evens: Vec<&i32> = v.iter().filter(|x| *x % 2 == 0).collect();

// 直接收集成不同容器
let set: std::collections::HashSet<i32> = v.iter().cloned().collect();
let map: std::collections::HashMap<i32, i32> = v.iter().cloned().map(|x| (x, x * x)).collect();