1. 第三篇的“其他”，到底指哪一类结构
1.1 前两篇划过的边界，先简单对齐
这系列做到第三篇，手感比刚开始顺了不少。前两篇把数组、链表、二叉树这些需要自己动手磨的结构基本过了一遍，到这一篇，标题里的“其他数据结构”其实是一个信号：必须手写实现的部分已经告一段落，后面的对手是 Rust 标准库里早就封装好的容器族——HashMap、BTreeMap、HashSet、BTreeSet、BinaryHeap、VecDeque。换句话说，考察重心从“怎么把结构造出来”挪到了“怎么把结构选对、用熟”上。
很多从 C++ 转过来的朋友会下意识去找“Rust 版的 map、set、priority_queue”，然后发现名字差不多，但用起来处处受所有权和 trait 的约束。有人干脆自己撸一个数据结构，结果代码越写越长，调试时间翻倍。我的建议很直接：OJ 题比赛的是算法正确性和复杂度，不是内存布局表演。除了并查集这种标准库确实没有的结构，以及少数被常数逼到墙角的情况，你几乎没有理由在 OJ 上徒手重写二叉堆或哈希表。
这一篇的目标读者分两类。一类是刚把 Rust 语法啃完、打算拿 OJ 练手的初学者，你需要的是“什么场景对应什么容器”的判断模型；另一类是已经写过几道题、但总在借用检查器面前卡住的人，这篇会重点讲那些最容易翻车的 API 用法和边界条件。两种需求都覆盖到，读完你至少能把标准容器在 OJ 里的常规姿势直接抄走。
1.2 标准库优先，手写兜底
做 OJ 题时我脑中有一套选择顺序，基本是倒着来的：第一问，能不能用Vec加排序搞定？第二问，需不需要“某个值是否存在”这类 O(1) 查询？第三问，需不需要实时知道当前最大或最小？第四问，需不需要维护一个有序集合，并且经常做“找前驱、找后继”这种操作？这四问下来，80% 的数据结构题已经落在标准库范围内了。
只有两种情况我会考虑手写：一种是并查集、单调队列、Trie、Segment Tree 这类标准库没提供、但题目明摆着要你自建的结构；另一种是像哈希表被针对性卡死这种极少见的场景，得换自写哈希或调整策略。平时把标准库用对，复杂度是明牌：HashMap 均摊 O(1)，BTreeMap 严格 O(log n)，BinaryHeap 进出堆 O(log n)，VecDeque 头尾操作 O(1)。这些复杂度在 OJ 里足够你估算出能不能过，而不必陷入实现细节的泥潭。
2. 先盘点 Rust 容器家族：它们各自解决什么问题
2.1 键值映射：HashMap 与 BTreeMap
HashMap和BTreeMap都存键值对，但底层模型完全不同。HashMap 是无序的，靠哈希函数把键映射到桶里，适合“我只想立刻知道 key 对应的 value 是什么”的场景，比如统计频率、记录出现位置、记忆化搜索。BTreeMap 底层是 B 树，键始终有序，适合“我需要按键从小到大遍历、取前驱后继、做区间查询”的场景。
选择时有一条很实用的经验：**如果题目输出不要求排序，优先 HashMap；一旦涉及有序输出、求最接近的键、按范围统计，就换 BTreeMap。**比如“给定若干区间，合并后输出有序结果”，你当然可以把区间丢进 Vec 排序再合并，但如果你需要边插入边保持有序，BTreeMap 更顺手。另外注意 trait 约束：HashMap 要求键实现Hash + Eq，BTreeMap 要求键实现Ord。基本类型和 String 都满足，但自定义结构体要想当键，得自己 derive 或实现这些 trait。
Rust 的 HashMap 默认用 SipHash 作为哈希算法，带随机种子。好处是能防御针对哈希表的碰撞攻击，坏处是常数比简单哈希稍大。OJ 上绝大多数题目感知不到这个差距，但如果你发现某道哈希题整体算法正确却超时，确实可以怀疑一下这里。真要优化，别一上来就换自定义哈希，先确认是不是数据量或者死循环问题。后续我会在踩坑部分展开。
2.2 集合：HashSet 与 BTreeSet
HashSet 和 BTreeSet 可以理解成只关心键、不关心值的 HashMap 和 BTreeMap。问题里只要出现“这个元素出现过没有”“哪些元素不重复”这类诉求，就用HashSet。如果还要求“把不重复元素按顺序输出”或“找到比 x 大的最小元素”，就用BTreeSet。
这里有个新手容易忽略的点：Rust 的 HashSet 本身支持集合运算，比如union、intersection、difference、symmetric_difference，返回的是迭代器。OJ 里遇到“两个数组的交集”“统计两个集合的差异”这类题，如果直接用这些方法，代码量小，逻辑也清晰。需要注意返回的是迭代器，得.collect()到 Vec 或直接遍历，而且迭代器的顺序依然受底层结构影响，HashSet 别依赖顺序，BTreeSet 可以。
2.3 特殊队列：BinaryHeap 与 VecDeque
BinaryHeap 在 Rust 里默认是最大堆，peek()和pop()拿到的都是堆里最大的元素。很多算法题需要的恰恰是“始终取最小”，这时候标准解法是套一层Reverse，也就是BinaryHeap<Reverse<T>>。这个细节单独拆出来讲，因为它是 Rust 做题时最容易栽进去的坑之一。后面第三部分和第四部分都会反复用到。
VecDeque 是双端队列，头部和尾部都能 O(1) 进出。它的地位在 OJ 里经常被低估：BFS 需要队列，滑动窗口需要维护窗口内最大最小值，这些场景VecDeque比Vec更合适。用Vec做队列时，remove(0)是 O(n) 的，数据一大就超时。许多人 debug 阶段没感觉，换大数据就崩，根源就在这里。我用 VecDeque 时习惯只记住四个方法：push_back、pop_front、push_front、pop_back，足以覆盖绝大多数滑动窗口和 BFS 场景。
2.4 一张表把区别说清楚
| 容器 | 底层结构 | 是否有序 | 键/元素唯一 | 核心操作复杂度 | 典型场景 | | --- | --- | --- | --- | --- | | HashMap | 哈希表 | 否 | 键唯一 | 均摊 O(1) | 计数、映射、缓存 | | BTreeMap | B 树 | 是 | 键唯一 | O(log n) | 有序键、区间查询、前驱后继 | | HashSet | 哈希表 | 否 | 元素唯一 | 均摊 O(1) | 去重、存在性检查 | | BTreeSet | B 树 | 是 | 元素唯一 | O(log n) | 有序集合、范围遍历 | | BinaryHeap | 二叉堆 | 部分（堆序） | 可重复 | 插入/弹出 O(log n) | 最大最小优先队列 | | VecDeque | 双端队列 | 否 | 可重复 | 头尾 O(1) | 队列、BFS、滑动窗口 |
这张表不是让你背下来，而是做题时对照着用。看到“最大”“最小”“前 K 个”就往 BinaryHeap 想，看到“是否出现过”“统计次数”就往 HashMap 想，看到“有序”“区间”就往 BTree 系列想，看到“一层一层扩展”“窗口往右滑”就往 VecDeque 想。表格是地图，不是考试大纲。
3. 做题前先背下来的三个高频套路
3.1 计数与 TopK：HashMap 的 entry 接口
统计频率是 OJ 的常客。C++ 选手写unordered_map<int,int> cnt; cnt[x]++;特别自然，但 Rust 的 HashMap 只提供了只读索引，没有赋值索引，所以map[x] += 1是编译不过的。正确姿势是用entry接口：
use std::collections::HashMap; fn count_words(text: &str) -> HashMap<&str, i32> { let mut cnt = HashMap::new(); for word in text.split_whitespace() { cnt.entry(word) .and_modify(|c| *c += 1) .or_insert(1); } cnt }这里entry(word)返回的是枚举Entry，and_modify负责“如果键已存在就对值做闭包操作”，or_insert负责“如果键不存在就插入默认值”。新手最爱写的or_insert(0)配合解引用递增也可以：
*cnt.entry(word).or_insert(0) += 1;两种写法等效，前者更明确，后者更短。说实话我在 OJ 上多数时候用后者，因为少写几行。要明白的是：entry返回的是一个“借用了 map 的可变引用”的枚举，所以一定要在同一个表达式里完成修改，拆成两行容易触发借用冲突。
光会统计还不够，题目经常让输出出现次数最多的前 K 个元素。这时就需要堆登场。先把所有键值对放进BinaryHeap，因为元组默认先比较第一个元素，所以把(次数, 元素)压进去，每次pop拿到的就是“次数最多且元素值最大”的那一项。如果希望次数相同时按元素升序输出，就得在这个元组上动点手脚，或者直接用最小堆维护前 K 个，这部分我在第四题里给完整代码。
3.2 逐层扩展：VecDeque 的入队出队姿势
BFS（广度优先搜索）是图论和网格题的基础。Rust 里实现 BFS 的标准姿势是VecDeque+ 一个visited记录。网格题里常见的是“从某个位置出发，能扩展到哪些相邻位置”。这里有两个新手坑：一是坐标类型，数组下标是 usize，做加减法时容易越界，要用 isize 或者显式判断边界；二是标记访问的时机，应该在入队时立刻标记，而不是在弹出时才标记，否则同一个坐标会被重复入队很多次，直接超时。
写对 BFS 队列的要点只有三个：push_back放新节点，pop_front取当前节点，入队同时标记。不要用Vec + remove(0)，那是灾难性的 O(n) 操作；数据规模一大，光这个就会让复杂度从 O(rowscols) 膨胀成 O(rowscolsrowscols)。
3.3 有序维护：BTreeSet 的 range 查询
BTreeSet和BTreeMap在 OJ 里最漂亮的能力是有序和范围查询。比如“给定一个集合，反复插入和删除整数，每次问大于等于 x 的最小值是多少”，没有有序容器就得每次排序，有了 BTreeSet 就完全不同：
use std::collections::BTreeSet; fn main() { let mut set = BTreeSet::new(); set.insert(3); set.insert(7); set.insert(12); if let Some(&v) = set.range(5..).next() { println!(">= 5 的最小值是 {}", v); } if let Some(&v) = set.range(..=7).next_back() { println!("<= 7 的最大值是 {}", v); } }range(5..)是左闭右开区间，表示从 5 开始到无穷；range(..=7)是左负无穷到 7 的闭区间。next()拿区间里第一个元素，next_back()拿最后一个，正好对应“后继”和“前驱”两种查询。还有range(3..8)这种标准范围写法。这类模板在处理“有序插入 + 查询相邻元素”的问题时极其好用，比如日程安排、区间插入、最近可用编号等。如果你想维护的是键值对而不是简单元素，那就用BTreeMap，它也有同样的range方法，返回的是(键, 值)迭代器。
4. 三道 OJ 原题级拆解：从读入到输出
4.1 前 K 个高频元素：HashMap + BinaryHeap 组合
题目做完简单复盘：“给定 n 个整数和一个 k，输出出现次数最多的 k 个数。”我按 OJ 常见输入格式处理：第一行是n k，第二行是 n 个数。完整代码如下：
use std::collections::{BinaryHeap, HashMap}; use std::io::{self, Read}; fn solve(input: &str) -> String { let mut it = input.split_whitespace().map(|s| s.parse::<i32>().unwrap()); let n = it.next().unwrap() as usize; let k = it.next().unwrap() as usize; let mut cnt = HashMap::new(); for _ in 0..n { let x = it.next().unwrap(); *cnt.entry(x).or_insert(0) += 1; } let mut heap = BinaryHeap::new(); for (num, c) in cnt { heap.push((c, num)); } let mut ans = Vec::new(); for _ in 0..k { if let Some((_, num)) = heap.pop() { ans.push(num.to_string()); } } ans.join(" ") } fn main() { let mut input = String::new(); io::stdin().read_to_string(&mut input).unwrap(); println!("{}", solve(&input)); }为什么heap.push((c, num))而不是(num, c)？因为 BinaryHeap 默认最大堆，元组比较先看第一个字段。如果先放num再放c，堆顶就会变成“数值最大的元素”而不是“次数最多的元素”，整道题就错了。这个顺序问题值得反复强调，真有人在这里栽过。
复杂度上，统计一遍是 O(n)，把所有(次数, 元素)全部入堆是 O(m log m)，m 是不同元素的个数。如果 k 远小于 m，可以改进为维护一个大小为 k 的最小堆，每个新元素和堆顶比较，堆顶是最小次数，这样复杂度变成 O(m log k)，空间也小。需要取最小堆时，把BinaryHeap<(Reverse<u32>, ...)>或者直接包一层Reverse按需求做。但多数题目 m 不大，全量入堆也能过，写起来反而简单。
4.2 合并 K 个有序数组：Reverse 包一层的堆
这个问题的 OJ 版本通常长这样：给 K 个升序数组，合并成一个升序数组。朴素做法是把所有元素装进一个 Vec 再排序，复杂度是 O(total log total)，听起来也不是不行，但问题往往是“K 较大、每个数组较长”，面试和 OJ 真正想考的其实是多路归并：利用每路都有序的特性，用优先队列每次选出当前最小的“队头”。核心代码：
use std::cmp::Reverse; use std::collections::BinaryHeap; fn merge_k_sorted(arrs: &[Vec<i32>]) -> Vec<i32> { let mut heap = BinaryHeap::new(); for (arr_id, arr) in arrs.iter().enumerate() { if let Some(&first) = arr.first() { heap.push(Reverse((first, arr_id, 0))); } } let mut result = Vec::new(); while let Some(Reverse((val, arr_id, idx))) = heap.pop() { result.push(val); if idx + 1 < arrs[arr_id].len() { heap.push(Reverse((arrs[arr_id][idx + 1], arr_id, idx + 1))); } } result }这里Reverse是整个元组包进去的，不是只包值。这么做的原因是堆里比较时按元组顺序比较：先看数值，数值相同再看数组编号，再相同看下标。三个字段顺序很讲究：(val, arr_id, idx)保证堆顶永远是当前所有数组中“最小的那个值”；如果把arr_id放最前面，堆顶会变成“编号最大的数组的最小值”，那可就错了。整个思路是：每个数组先各取第一个元素入堆；弹出最小的那个后，从同一个数组里继续取下一位补进去。就像 K 路队伍各自报数，你每次喊最小号的出列，然后让那个队伍补下一个数字，直到所有队伍都空了。整个过程每个元素入堆一次、弹出一次，复杂度 O(total log K)，比“全排完”优雅得多。
4.3 岛屿数量：网格 BFS 中 VecDeque 和原地标记
岛屿数量是另一个高频题：二维字符矩阵里，'1'表示陆地，'0'表示水，上下左右相邻的'1'算同一个岛屿，问有几个岛。思路也很标准：遍历每个格子，遇到没访问过的陆地就把它当成新岛屿，然后从它开始 BFS，把整个岛屿全部标记为已访问。为了省掉额外的 visited 数组，我选择原地把访问过的陆地改成'0'，等价于“淹掉这个岛”。
use std::collections::VecDeque; fn num_islands(mut grid: Vec<Vec<char>>) -> i32 { let rows = grid.len(); let cols = grid[0].len(); let mut count = 0; for i in 0..rows { for j in 0..cols { if grid[i][j] != '1' { continue; } count += 1; grid[i][j] = '0'; let mut queue = VecDeque::new(); queue.push_back((i, j)); while let Some((r, c)) = queue.pop_front() { for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] { let nr = r as isize + dr; let nc = c as isize + dc; if nr < 0 || nr >= rows as isize { continue; } if nc < 0 || nc >= cols as isize { continue; } let nr = nr as usize; let nc = nc as usize; if grid[nr][nc] == '1' { grid[nr][nc] = '0'; queue.push_back((nr, nc)); } } } } } count }这段代码里最关键的是“在入队时立刻把陆地改成'0'”。如果改成“弹出时才标记”，同一个格子可能被周围四个格子重复入队，队列里会有大量重复元素，最坏情况能直接打爆时间。我见过不少人在这道题上 TLE，就是因为少了这一句话。另一个细节是坐标计算：r和c是 usize，不能直接减 1，所以先as isize做加减，判断完边界后再转会 usize。这个 isize 往返看着有点啰嗦，但在二维网格题里是标准防御姿势，写习惯了就不觉得麻烦。
上面三道题覆盖了 HashMap、BinaryHeap、Reverse、VecDeque 四个最常用的容器组合。题目本身不是难点，难点是把每个结构放在它最合适的位置：计数用 HashMap，优先级用堆，逐层扩散用队列。剩下的 BTree 系列，我放到了前面的模板里，你遇到“有序 + 区间”题时直接套。
5. 实战里最容易翻车的几个点
5.1 所有权和借用：不是 C++ 的引用
Rust 做题最大的心智负担就是借用检查器。最常见的一句报错是cannot borrow cnt as mutable because it is also borrowed as immutable，基本都出现在“遍历一个容器时又试图修改它”。比如你想统计完再顺手清理某个键，写出类似这样的代码：
let mut cnt = HashMap::new(); // 中间省略 for (k, &v) in cnt.iter() { if v == 1 { cnt.remove(k); // 编译错误：不可变借用和可变借用同时存在 } }这种写法 C++ 里没事，Rust 里就是不行。OJ 场景下我的处理办法很简单：先遍历收集需要删除或修改的键到临时 Vec，再根据这个 Vec 去操作原容器。多一次遍历通常不影响复杂度，但把借用的痛苦降到最低。记住一个心智模型：iter()会把整个容器“借”给你，你在借期内不能做任何可变操作。想边遍历边修改时，问问自己“能不能分两步做”。
还有一种很常见的场景是“遍历数组同时更新 HashMap”。数组本身在 for 循环里默认按值取，如果你需要索引又需要修改 map，最好这样写：
for (i, x) in nums.iter().enumerate() { // i 是索引，x 是 &i32 map.insert(*x, i); }这里nums.iter()借的是 nums，map.insert借的是 map，两个对象不同，不会冲突。所以很多时候不是不能改，是别在同一个容器上同时做不可变迭代和可变写入。
5.2 BinaryHeap 的默认方向：为什么总看到 Reverse
BinaryHeap默认是最大堆，这跟很多算法竞赛选手用惯的最小堆正好反着。解决方式不是自己写一个最小堆，而是包装Reverse。Reverse会把元素的比较结果翻转，放进堆里之后，堆顶反而是“按原比较规则最小”的元素。很多人一开始不知道能这么干，硬是手写堆，其实标准库已经给你留了后门。
不过Reverse不是万能的。它要求内部类型实现Ord。对于整数、字符串、元组这些类型没问题，但如果你创建了自己的结构体，就需要手动实现PartialOrd、Ord、PartialEq、Eq四个 trait 才能塞进 BinaryHeap。我的建议是：做题时尽量用元组而不是自定义结构体。比如堆元素需要三个字段时，直接用(i32, usize, usize)，配合Reverse玩顺序，比写结构体再 impl 一堆 trait 省心得多。
还有一个小细节：当你只想取“当前最大值但不想弹出”，用peek()，它返回Option<&T>。如果你对这个引用修改，就需要注意借用问题。OJ 里多数场景是“先 peek 比较，再 pop”，这两步分开写就没问题。
5.3 读入和输出的习惯姿势
OJ 上 Rust 读入不要用read_line一行行拼，那很慢且容易写乱。我长期用的是：
use std::io::{self, Read}; fn main() { let mut input = String::new(); io::stdin().read_to_string(&mut input).unwrap(); // 把 input 交给 solve 函数处理 }这样会把所有输入一次性读进一个字符串，然后split_whitespace()加parse()，既能应对跨行输入，也不会被空白符干扰。解析整数时可以用习惯的 chain：input.split_whitespace().map(|s| s.parse::<i64>().unwrap())，把结果当成一个迭代器一个个取。这个技巧在题目第一行给 n、后面给 n 行数据时尤其好用，因为你不必维护“当前读了几行”的状态。
输出方面，最容易忽略的是顺序问题。HashMap 迭代顺序不保证，所以凡是输出要求按原始顺序或按值排序的结果，必须先把结果整理进 Vec 排序，再用 join 拼接。我见过有人直接遍历 HashMap 输出，本地跑没问题，一提交就 Wrong Answer，原因就是随机种子让每次运行顺序都不一样。既然输出不稳定，正确性当然无从谈起。
5.4 性能上容易被忽略的小开销
标准库容器在算法正确的前提下很少拖后腿，但有几个小开销还是值得注意。第一，HashMap的默认哈希是 SipHash，随机种子让每次程序运行哈希分布都不一样，理论上能防碰撞攻击，常数也比简单哈希慢。OJ 数据一般是静态构造的，不太可能刻意卡你，但我真遇到过一道“数据量大到 HashMap 过不了”的题，换成排序 + 双指针直接过了。所以遇到哈希超时，不要死磕HashMap，考虑一下能否用排序换掉它。
第二，String 做键尽量用&str借用，避免多余的克隆。比如HashMap<&str, i32>在遍历时会借入，而不是复制整个字符串。如果键的所有权来自输入字符串，用借用关系既能过编译，又少一次分配。不过注意生命周期：HashMap 存活期间，借用来源的 String 不能提前销毁。理解这一点之后，你会少很多“为什么不让我用 HashMap<&str, _>”的疑问。
第三，提前设置容量。能预估数据量时用Vec::with_capacity(n)、HashMap::with_capacity(n)，可以减少扩容时反复分配内存。扩容虽然均摊 O(1)，但常数也不小，在大数据面前能省一点是一点。
6. 关于“数据结构题”我自己的一些体会
做这一系列题，最大的收获不是背会了哪个 API，而是慢慢建立起一种“判断模型”：每个题目陈述里的关键词，都在暗示你应该用哪种结构。“出现次数”指向 HashMap，“前 K 大”指向堆，“覆盖区间”指向排序或 BTree，“上下左右扩散”指向 BFS 队列。把这些信号识别出来，剩下的就是把模板填进去。
我也有一些固执的小习惯。比如能用排序解决的题，我不会优先考虑复杂的平衡树；能用Vec干完的事，不会为了炫技上 HashMap；堆里能塞元组，就绝不自定义结构体。这些选择不是“正确”，而是省时间、少 debug、降低心智负担。OJ 实战到了一定阶段，比的不是谁会的结构多，而是谁在正确的地方选择正确的结构，并且能一次写对。这套“其他数据结构”的模板，我个人是从第三篇开始真正找到感觉的，希望你也能顺着这几个套路，把手里的题刷明白。
