集合：从访问模式选择 Vec、Map、Set 与队列

课程概览 · 第 11 章

上一篇：泛型与 trait：复用行为，同时保持接口清晰

下一篇：迭代器与闭包：让数据转换可组合

任务列表要按顺序展示、要按 ID 查找、要统计标签出现次数、还要按优先级取“下一个要做的”。每一种访问模式都指向不同的容器；从访问模式出发选集合，而不是从“哪个理论复杂度最好”出发。多数场景先选 Vec 或 HashMap，只有排序、双端队列、优先队列等需求明确时再换容器。

图：集合先匹配访问模式；迭代再决定元素是借用、修改还是被消费。

学习目标与默认选择

学完本章你应当能够：

• 按访问模式（顺序、按键、有序、去重、优先级、FIFO）推导出容器选择；
• 用 Vec::with_capacity、swap_remove、HashMap::entry、get 写出正确且可预期的集合代码；
• 区分借用、可变、owned 三种迭代方式的所有权后果；
• 用 sort/dedup/retain/drain 做 Vec 的原地处理，为自定义键派生 Hash/Eq；
• 用 intersection/union/difference 与 BTreeMap::range 替代手写循环；
• 解释为什么 LinkedList 几乎从来不是正确的默认，以及 len 与 capacity 的区别。

默认选择：不确定时用 Vec；需要按键查找时用 HashMap；输出必须确定有序时用 BTreeMap 或排序。

选型决策规则

问题	容器	顺序保证	关键复杂度
只需按位置/顺序存取？	Vec<T>	插入顺序	下标 O(1)；尾部 push 摊销 O(1)；中间插入/删除 O(n)
头尾都要进出（FIFO 队列）？	VecDeque<T>	入队顺序	两端 O(1)
按键查找即可，不关心顺序？	HashMap<K, V>	无（遍历顺序不稳定）	平均 O(1)，最坏 O(n)（哈希碰撞）
按键有序遍历或范围查询？	BTreeMap<K, V>	键升序	O(log n)
只需要“存在与否”？	HashSet<T>	无	平均 O(1)
去重且要有序遍历/范围查询？	BTreeSet<T>	元素升序	O(log n)
反复取最大/最小？	BinaryHeap<T>	只有堆顶有序	push/pop O(log n)，peek O(1)
只需后进先出（LIFO 栈）？	Vec<T> 尾部 push/pop	入栈逆序	摊销 O(1)
稳定节点引用且频繁中间插入（罕见）？	LinkedList<T>	插入顺序	两端 O(1)；定位中间节点 O(n)

注意事项：

• HashMap/HashSet 遍历顺序不稳定：同一份代码两次运行顺序可能不同（迭代器实现有意加了随机化种子之外的布局依赖）。输出要确定时，收集键后排序，或直接用 BTreeMap。
• 平均与最坏：哈希表平均 O(1) 依赖良好的哈希分布；BTreeMap/BTreeSet 用 O(log n) 换确定性与有序性。
• Set 是 Map 的特例：HashSet<T> 就是“值为 () 的 HashMap<T, ()>”，BTreeSet 同理；两者的顺序保证、复杂度、键的 trait 要求（Eq + Hash / Ord）与对应 Map 完全一致。
• LinkedList 不是默认：缓存局部性差、随机访问 O(n)、即使头尾操作也没有比 VecDeque 更好的实际表现。只在“需要稳定引用且频繁中间插入”这类罕见场景考虑。

一个完整的任务列表示例

下面的程序覆盖了任务列表的常见操作：预分配容量、追加、两种删除、三种迭代、频率统计、不可信下标、确定性输出：

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

#[derive(Debug, Clone, PartialEq)]
struct TaskId(u64);

#[derive(Debug, Clone, PartialEq)]
#[allow(dead_code)] // 完整状态机见第 8 章；本例只用 Todo / InProgress。
enum TaskState {
    Todo,
    InProgress { started_at: u64 },
    Done { finished_at: u64 },
    Cancelled { reason: String },
}

#[derive(Debug, Clone, PartialEq)]
struct Task {
    id: TaskId,
    title: String,
    state: TaskState,
    labels: Vec<String>,
}

fn main() {
    // 1. 已知大致数量时用 with_capacity 预分配，避免多次扩容拷贝。
    let mut tasks: Vec<Task> = Vec::with_capacity(4);
    tasks.push(Task {
        id: TaskId(1),
        title: String::from("write docs"),
        state: TaskState::Todo,
        labels: vec![String::from("docs")],
    });
    tasks.push(Task {
        id: TaskId(2),
        title: String::from("fix build"),
        state: TaskState::InProgress { started_at: 100 },
        labels: vec![String::from("ci"), String::from("urgent")],
    });
    tasks.push(Task {
        id: TaskId(3),
        title: String::from("review pr"),
        state: TaskState::Todo,
        labels: vec![String::from("urgent")],
    });
    assert_eq!(tasks.len(), 3);

    // 2. 删除：remove 保序但搬动后续元素 O(n)；swap_remove O(1) 但打乱顺序。
    //    需要保持展示顺序时用 remove；只从尾部删或不在乎顺序时用 swap_remove。
    let removed = tasks.remove(0); // 删除第一个，后面元素前移。
    assert_eq!(removed.title, "write docs");
    assert_eq!(tasks.len(), 2);
    assert_eq!(tasks[0].title, "fix build"); // 保序：fix build 现在是第一个。

    // 3. 三种迭代方式：
    // 3a. 借用迭代：拿到 &Task，tasks 之后还能用。
    let titles: Vec<&str> = tasks.iter().map(|t| t.title.as_str()).collect();
    assert_eq!(titles, ["fix build", "review pr"]);

    // 3b. 可变迭代：原地修改每个元素。
    for task in &mut tasks {
        if let TaskState::Todo = task.state {
            task.labels.push(String::from("unassigned"));
        }
    }
    assert!(tasks[1].labels.contains(&String::from("unassigned")));

    // 3c. owned 迭代：消耗 tasks，元素被移出。此后 tasks 不可再用。
    let total_labels: usize = tasks
        .into_iter()
        .map(|task| task.labels.len())
        .sum();
    assert_eq!(total_labels, 4); // fix build 2 个 + review pr 2 个。

    // 4. 重新建数据做统计：HashMap::entry 把“存在则更新，不存在则初始化”变成一次查找。
    let labels = ["urgent", "ci", "urgent", "docs", "urgent"];
    let mut counts: HashMap<&str, usize> = HashMap::new();
    for label in labels {
        *counts.entry(label).or_insert(0) += 1;
    }
    assert_eq!(counts.get("missing"), None); // 缺键是正常缺失，不是错误。

    // 5. HashMap 遍历顺序不稳定：需要确定输出时收集键并排序……
    let mut sorted_pairs: Vec<(&str, usize)> =
        counts.iter().map(|(k, v)| (*k, *v)).collect();
    sorted_pairs.sort();
    assert_eq!(sorted_pairs, [("ci", 1), ("docs", 1), ("urgent", 3)]);

    // 6. ……或者一开始就选 BTreeMap，天然按键有序。
    let mut ordered: BTreeMap<&str, usize> = BTreeMap::new();
    for label in labels {
        *ordered.entry(label).or_insert(0) += 1;
    }
    let ordered_keys: Vec<&str> = ordered.keys().copied().collect();
    assert_eq!(ordered_keys, ["ci", "docs", "urgent"]);

    // 7. 不可信下标：用户输入的序号必须用 get，而不是 []（越界会 panic）。
    let titles = ["fix build", "review pr", "write docs"];
    let user_index: usize = 7; // 假装来自命令行参数。
    match titles.get(user_index) {
        Some(title) => println!("selected: {title}"),
        None => println!("no task at index {user_index}"),
    }
    assert_eq!(titles.get(user_index), None);
    assert_eq!(titles.get(1), Some(&"review pr"));

    println!("collections ok");
}

空集合、缺键、重复、FIFO（边界与失败场景）

四个必须显式处理的边界：

• 空集合：max()/min()/first()/pop() 在空集合上返回 None，不 panic；用 Option 处理或断言非空，别假设输入一定有元素。
• 缺键：map.get(&k) 返回 Option；map[&k] 在缺键时 panic。缺键若是正常情况（可选字段），用 get；若是程序 bug（键必须存在），[] 的 panic 反而是正确的失败方式。
• 重复：HashSet/BTreeSet 自动去重（依赖 Eq + Hash / Ord）；Vec 保留重复。需要“出现过没有”语义时用 set，不要在 Vec 里线性查找。
• FIFO：用 VecDeque，不要反复 Vec::remove(0)（每次都是 O(n) 搬移）：

use std::collections::VecDeque;

fn main() {
    // 任务队列：先来先做。
    let mut queue: VecDeque<&str> = VecDeque::new();
    queue.push_back("t1");
    queue.push_back("t2");
    queue.push_back("t3");

    assert_eq!(queue.pop_front(), Some("t1")); // FIFO：最先入队的先出。
    assert_eq!(queue.pop_front(), Some("t2"));
    assert_eq!(queue.pop_front(), Some("t3"));
    assert_eq!(queue.pop_front(), None); // 空队列返回 None，不 panic。

    // 对比：Vec 头部删除是 O(n)，元素整体前移。
    let mut vec_queue = vec![1, 2, 3];
    assert_eq!(vec_queue.remove(0), 1);
    assert_eq!(vec_queue, [2, 3]);

    println!("FIFO ok");
}

Vec 的原地操作集

排序、去重、条件删除、移出迭代、二分查找、分块——这六个操作覆盖了 Vec 日常用法的八成，全部原地完成、不分配新容器：

use std::cmp::Reverse;

fn main() {
    let mut titles = vec!["review pr", "fix build", "write docs", "fix build"];

    // 1. 排序：sort 稳定（相等元素保持原相对顺序）；sort_unstable 略快但不保序。
    titles.sort();
    assert_eq!(titles, ["fix build", "fix build", "review pr", "write docs"]);

    // 2. 去重：dedup 只移除“相邻”重复，所以必须先排序。
    titles.dedup();
    assert_eq!(titles, ["fix build", "review pr", "write docs"]);

    // 3. 条件删除：retain 原地保留满足条件的元素，一次遍历 O(n)，无额外分配。
    titles.retain(|t| !t.contains("build"));
    assert_eq!(titles, ["review pr", "write docs"]);

    // 4. 按派生键排序：sort_by_key 对每个元素算一次键再比较。
    let mut tasks = vec![
        ("write docs", 2u8),
        ("fix build", 5u8),
        ("review pr", 3u8),
    ];
    tasks.sort_by_key(|(_, priority)| Reverse(*priority)); // 优先级降序。
    assert_eq!(tasks[0].0, "fix build");

    // 5. drain：边迭代边移出，结束后原 Vec 为空。
    //    与 into_iter 的区别：drain 是借用，容器本身还在（可复用其容量）。
    let mut inbox = vec!["t1", "t2", "t3"];
    let drained: Vec<&str> = inbox.drain(..).collect();
    assert_eq!(drained, ["t1", "t2", "t3"]);
    assert!(inbox.is_empty());
    assert!(inbox.capacity() >= 3); // 容量保留，可直接复用。

    // 6. 有序 Vec 的二分查找：binary_search 前提是有序，Ok(位置) / Err(应插入位置)。
    let sorted_ids = [1u64, 3, 5, 7];
    assert_eq!(sorted_ids.binary_search(&5), Ok(2));
    assert_eq!(sorted_ids.binary_search(&4), Err(2)); // 4 应该插在下标 2。

    // 7. chunks / windows：定长分块（不重叠）与滑窗（重叠），常用于批处理。
    let ids = [1, 2, 3, 4, 5];
    let batches: Vec<&[i32]> = ids.chunks(2).collect();
    assert_eq!(batches, [&[1, 2][..], &[3, 4][..], &[5][..]]);
    let pair_sums: Vec<i32> = ids.windows(2).map(|w| w[0] + w[1]).collect();
    assert_eq!(pair_sums, [3, 5, 7, 9]);

    println!("vec ops ok");
}

两个容易踩的约束：

• dedup/binary_search 都假设已排序；无序 Vec 上调用不会报错，只会得到错误结果。
• 遍历的同时增删元素会被借用检查拦住（迭代器持有借用）；正确姿势是 retain（条件删）、drain（移出）、或先 collect 出下标再改。

自定义键与 entry 进阶

自定义类型当 HashMap 的键需要 Eq + Hash（BTreeMap 需要 Ord），全部派生即可。契约：Hash 与 Eq 必须一致——相等的键必须有相同的哈希值；派生实现天然满足，手写实现破坏这条契约会导致“键明明存在却查不到”：

use std::collections::HashMap;

#[derive(Debug, Clone, PartialEq, Eq, Hash)] // Eq + Hash 是当键的门槛。
struct TaskId(u64);

fn main() {
    let mut title_of: HashMap<TaskId, String> = HashMap::new();
    title_of.insert(TaskId(1), String::from("write docs"));
    title_of.insert(TaskId(2), String::from("fix build"));

    // 查找时构造临时 TaskId 是廉价的；自定义键没有这步就无法避免。
    assert_eq!(title_of.get(&TaskId(2)).map(String::as_str), Some("fix build"));

    // HashMap<String, _> 可以直接用 &str 查找，无需构造 String（Borrow<str>）。
    let mut labels: HashMap<String, usize> = HashMap::new();
    labels.insert(String::from("urgent"), 1);
    assert_eq!(labels.get("urgent"), Some(&1)); // 参数是 &str，不是 &String。
    assert_eq!(labels.get("docs"), None);

    // entry 进阶：and_modify + or_insert 一次查找完成“存在则改，缺省则建”。
    let mut counts: HashMap<&str, usize> = HashMap::new();
    for label in ["urgent", "ci", "urgent"] {
        counts.entry(label).and_modify(|c| *c += 1).or_insert(1);
    }
    assert_eq!(counts["urgent"], 2);
    assert_eq!(counts["ci"], 1);

    // or_insert_with：初始值需要计算时用闭包，只在缺键时执行一次。
    let mut index: HashMap<&str, Vec<u64>> = HashMap::new();
    index.entry("urgent").or_insert_with(Vec::new).push(1);
    index.entry("urgent").or_insert_with(Vec::new).push(2);
    index.entry("ci").or_insert_with(Vec::new).push(3);
    assert_eq!(index["urgent"], vec![1, 2]);
    assert_eq!(index["ci"], vec![3]);

    println!("custom key ok");
}

entry 的价值不只是少写分支：它把键的哈希计算从“查一次 + 插一次”压缩到一次，也消除了 get 之后 insert 之间的竞态窗口（多线程包装下尤其重要）。

集合运算与范围查询

“两个标签集合的交集”“Alice 有而 Bob 没有的标签”“优先级 3 到 5 之间的任务”——这些都有现成方法，不要手写循环：

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let alice: BTreeSet<&str> = ["docs", "ci", "urgent"].into_iter().collect();
    let bob: BTreeSet<&str> = ["ci", "review"].into_iter().collect();

    // 四种集合运算，HashSet 上同名存在；返回惰性迭代器，collect 成新集合。
    let both: BTreeSet<&str> = alice.intersection(&bob).copied().collect();
    assert_eq!(both, BTreeSet::from(["ci"]));

    let either: BTreeSet<&str> = alice.union(&bob).copied().collect();
    assert_eq!(either, BTreeSet::from(["ci", "docs", "review", "urgent"]));

    let only_alice: BTreeSet<&str> = alice.difference(&bob).copied().collect();
    assert_eq!(only_alice, BTreeSet::from(["docs", "urgent"]));

    let exclusive: BTreeSet<&str> =
        alice.symmetric_difference(&bob).copied().collect();
    assert_eq!(exclusive, BTreeSet::from(["docs", "review", "urgent"]));

    // 子集/超集/不相交判断。
    assert!(BTreeSet::from(["ci"]).is_subset(&alice));
    assert!(alice.is_disjoint(&BTreeSet::from(["review"])));

    // BTreeMap::range：按键区间查询，支持 ..、a..b、a..=b、a.. 等各种区间。
    let mut by_priority: BTreeMap<u8, &str> = BTreeMap::new();
    by_priority.insert(2, "write docs");
    by_priority.insert(5, "fix build");
    by_priority.insert(3, "review pr");
    by_priority.insert(8, "release");

    let mid: Vec<(&u8, &&str)> = by_priority.range(3..=5).collect();
    assert_eq!(mid, [(&3, &"review pr"), (&5, &"fix build")]);

    println!("set ops ok");
}

选型含义：如果业务里频繁出现交集/并集，数据就应该放在 HashSet/BTreeSet 里，而不是 Vec 里再手写 contains 双重循环（O(n·m)）。

组合容器：主存 Vec + 索引 HashMap

单一容器常常满足不了多种访问模式。任务应用的真实需求是“按顺序展示”+“按 ID 秒查”，标准解法是双索引：

use std::collections::HashMap;

fn main() {
    // Vec 负责顺序与下标访问；HashMap<Id, 下标> 负责按 ID O(1) 定位。
    let tasks = ["write docs", "fix build", "review pr"];
    let index_of: HashMap<u64, usize> = tasks
        .iter()
        .enumerate()
        .map(|(i, _)| (i as u64 + 1, i)) // 假设 ID = 位置 + 1。
        .collect();

    let pos = index_of.get(&2).copied().expect("id 2 exists");
    assert_eq!(tasks[pos], "fix build");

    // 代价：Vec 中间删除/插入会让下标整体漂移，索引必须同步重建。
    // 删除频繁或 ID 与位置无关时，干脆用 HashMap<Id, Task> 做主存，
    // 顺序需求另存一个 Vec<Id> 当“目录”。
    println!("dual index ok");
}

判断标准：谁是真实数据源，谁是派生视图。只保留一份数据，另一份存引用/键；每次修改后要么同步更新索引，要么接受重建成本。

优先队列：BinaryHeap

“下一步做哪个任务”是最大堆的经典场景。BinaryHeap 只保证堆顶是最值，其余元素无序：

use std::collections::BinaryHeap;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Prioritized {
    priority: i32, // Ord 按字段顺序比较：priority 大的先出堆。
    title: String,
}

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(Prioritized { priority: 2, title: String::from("write docs") });
    heap.push(Prioritized { priority: 5, title: String::from("fix build") });
    heap.push(Prioritized { priority: 3, title: String::from("review pr") });

    // 堆顶始终是当前优先级最高的任务。
    let top = heap.pop().expect("heap is non-empty");
    assert_eq!(top.title, "fix build");
    assert_eq!(heap.peek().map(|t| t.priority), Some(3));

    // 其余元素不保证有序，只保证下一个 pop 出来的仍是最大。
    let next = heap.pop().expect("two items remain");
    assert_eq!(next.title, "review pr");
    let last = heap.pop().expect("one item remains");
    assert_eq!(last.title, "write docs");
    assert!(heap.pop().is_none()); // 空堆返回 None。

    println!("priority queue ok");
}

最小堆：Reverse 翻转比较方向

BinaryHeap 默认是最大堆，没有参数能改成最小堆——标准做法是包一层 std::cmp::Reverse，把比较结果反转：

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    // “最早截止的任务先做”：截止时间最小的先出堆。
    let mut earliest: BinaryHeap<Reverse<u64>> = BinaryHeap::new();
    earliest.push(Reverse(5));
    earliest.push(Reverse(2));
    earliest.push(Reverse(8));

    assert_eq!(earliest.pop(), Some(Reverse(2))); // 最小的先出。
    assert_eq!(earliest.peek().map(|r| r.0), Some(5));
    assert_eq!(earliest.len(), 2);

    println!("min heap ok");
}

Reverse 是零成本 newtype：Reverse(a) < Reverse(b) 当且仅当 a > b，编译后没有额外开销。自定义 struct 当堆元素时同理——要么调整 Ord 实现让“更紧急”的比较结果为 Greater，要么包 Reverse。

容量管理：len 与 capacity

len 是元素个数，capacity 是不扩容还能装的个数；扩容时 Vec 按几何级数增长容量（通常翻倍），这正是尾部 push 摊销 O(1) 的来源——单次 push 可能触发 O(n) 拷贝，但分摊到每次操作是常数：

fn main() {
    let mut ids: Vec<u64> = Vec::new();
    assert_eq!(ids.len(), 0);
    assert_eq!(ids.capacity(), 0); // 空 Vec 不分配堆内存，第一 push 才分配。

    // reserve(n)：保证至少还能再装 n 个而不扩容；数量可预估时避免中途搬迁。
    ids.reserve(10);
    assert!(ids.capacity() >= 10);

    ids.extend(0..10);
    assert_eq!(ids.len(), 10);
    assert!(ids.capacity() >= 10); // 预留充足，extend 没有触发扩容。

    // 超量写入后容量会富余；shrink_to_fit 把多余部分还给分配器。
    ids.extend(10..200);
    let before = ids.capacity();
    ids.truncate(10); // len 回到 10，capacity 不变。
    ids.shrink_to_fit();
    assert!(ids.capacity() < before);
    assert!(ids.capacity() >= ids.len()); // 收缩是尽力而为，只保证不小于 len。

    println!("capacity ok");
}

三个实践规则：

• 循环里 push 已知数量的元素，先 with_capacity/reserve，把 log n 次扩容拷贝降到零；
• 大批量删除后容器要长期持有（缓存、常驻服务），shrink_to_fit 释放富余内存；
• reserve/shrink_to_fit 只承诺下界，具体容量是实现细节，不要写依赖精确值的断言。

为什么可行

容器行为是存储布局的直接结果。Vec 把元素连续放置，所以下标访问是 O(1)、遍历对缓存友好，代价是中间插入要搬移元素。哈希表把键散列到桶里，所以平均查找 O(1)，代价是顺序信息完全丢失、扩容时需要重哈希。B 树把键维护在有序平衡结构里，用 O(log n) 换取有序遍历与范围查询。堆用部分有序的数组保证“最值在堆顶”，比完全排序便宜。

原地操作同样来自布局：sort/retain/dedup 在连续的 Vec 上只做指针读写，缓存友好；drain 利用“移出后整体前移”一次性完成搬移，比逐个 remove(0) 少 n 倍搬动。几何扩容把 push 的搬迁成本摊销成常数，代价是容量可能富余一倍——reserve/shrink_to_fit 就是让你在这个时间-空间权衡上手动落子。集合运算与 range 之所以比手写循环快，是因为它们直接利用哈希桶或 B 树节点的内部结构批量比较，而不是逐元素走公共迭代器。选型决策规则之所以可靠，是因为每条规则都对应一种布局的天然优势；违背访问模式选容器，就要为不匹配的布局付持续的代价。

常见误区

• 在 HashMap 上依赖遍历顺序：测试里比较“键列表”而顺序不稳定，测试会随机失败。排序后再比，或用 BTreeMap。
• 对不可信下标用 []：tasks[user_index] 越界直接 panic；用户输入一律 get。
• 反复 Vec::remove(0) 实现队列：每次都是 O(n)；FIFO 用 VecDeque。
• 在 Vec 里做“包含判断”：vec.contains(&x) 是线性扫描；频繁存在性检查用 HashSet。
• 为“性能”选 LinkedList：理论上插入 O(1)，实际上缓存局部性差、无随机访问；几乎所有场景 Vec/VecDeque 都更快。
• 忘记 into_iter 消耗了集合：for task in tasks 之后 tasks 已被移走；还要用就 for task in &tasks。
• 在无序 Vec 上 dedup/binary_search：两者都以“已排序”为前提；无序时结果静默错误，没有 panic 也没有警告。
• 遍历中增删元素：for t in &tasks { tasks.push(..) } 直接编译失败（借用冲突）；用 retain/drain/先收集下标。
• 手写 Hash/Eq 破坏一致性：相等的键哈希值不同，会出现“插得进、查不到”；当键的类型一律 #[derive(PartialEq, Eq, Hash)]。
• 用 String 键却每次构造临时 String 查找：map.get(&String::from(k)) 白白分配；HashMap<String, _> 的 get 直接接受 &str（Borrow）。
• 手写集合交并差：双重循环 contains 是 O(n·m)；数据放进 HashSet/BTreeSet 用 intersection/union。
• 把 capacity 当 len：v.capacity() 是分配量不是元素数；判断“有没有元素”用 is_empty()/len()。

自测

1. 输出必须按字母顺序稳定列出所有标签计数，HashMap 和 BTreeMap 各该怎么写？
   方向：HashMap 收集键后 sort() 再输出；BTreeMap 直接按序遍历。
2. remove(i) 和 swap_remove(i) 各自的复杂度与副作用是什么？什么场景选哪个？
   方向：remove O(n) 保序；swap_remove O(1) 把尾元素换过来打乱顺序；展示顺序重要用 remove，只删不展示用 swap_remove。
3. 用户传入的序号如何安全访问 Vec？缺键的 HashMap 查询呢？
   方向：Vec::get(i) 返回 Option；map.get(&k) 同理；[] 形式在越界/缺键时 panic，只适合“必须是程序 bug”的场景。
4. 为什么 LinkedList 不是默认？
   方向：缓存局部性差、无随机访问、实际基准几乎总输给 Vec/VecDeque；只有需要稳定节点引用且频繁中间插入的罕见场景才考虑。
5. for x in &v、for x in &mut v、for x in v 之后 v 分别还能不能用？
   方向：前两个可以（借用结束）；第三个不行，元素所有权已被移走。
6. dedup 之前为什么必须先 sort？无序 Vec 上调用会怎样？
   方向：dedup 只比较相邻元素；无序时相同元素不相邻，去重不完整且不报错。
7. HashMap<String, usize> 为什么能用 map.get("urgent") 这种 &str 直接查找？
   方向：get 的键参数泛型为 K: Borrow<Q>，String: Borrow<str>，所以 &str 可用且无需分配。
8. 自定义类型当 HashMap 键需要什么？手写实现时最大的坑是什么？
   方向：Eq + Hash，通常全派生；手写时若相等的键哈希值不同，会“插得进、查不到”。
9. “最早截止的任务先做”怎么用 BinaryHeap 实现？
   方向：BinaryHeap<Reverse<Deadline>>；Reverse 翻转 Ord 使最大堆表现为最小堆，零成本。
10. Vec 的 len 与 capacity 有什么区别？为什么尾部 push 是摊销 O(1)？
    方向：len 是元素数，capacity 是不扩容可装的数；几何增长（通常翻倍）使扩容拷贝成本分摊到每次 push 为常数。