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

课程概览 · 第 11 章
上一篇：泛型与 trait：复用行为，同时保持接口清晰
下一篇：迭代器与闭包：让数据转换可组合

任务列表按顺序展示、按 ID 查找、统计标签、按优先级调度，是四种不同的访问模式。先确定访问方式、顺序要求与修改成本，再比较容器；不要只凭一行理论复杂度选型。本章示例各自独立，不沿用前面章节的完整状态模型。

按顺序、按键、去重和优先级访问时的集合选择，以及 entry、迭代所有权和容量管理 — 图：先匹配访问模式，再决定元素借用、修改或移出的方式。

前置知识与学习目标

需要理解所有权、Option 与第 10 章的 trait 约束。学完本章应能：

根据顺序、按键、唯一性与 FIFO 需求选择容器；
预测 Vec 删除、移出与空集合访问的结果；
使用 entry、集合运算与范围查询，并说明键的契约；
区分内容、容量和派生索引的一致性要求。

从访问模式选型

访问需求	容器	顺序与主要成本
顺序展示、尾部追加、按下标读取	`Vec<T>`	连续存储；下标 `O(1)`，push 摊销 `O(1)`，中间增删 `O(n)`
FIFO 或两端进出	`VecDeque<T>`	两端进出通常为常数时间，扩容可能搬移
按键查找、无需排序	`HashMap<K, V>`	无稳定遍历顺序；平均查找 `O(1)`，最坏可为 `O(n)`
按键有序输出、范围查询	`BTreeMap<K, V>`	键升序；查找 `O(log n)`
存在性与去重	`HashSet<T>` / `BTreeSet<T>`	前者无序，后者有序；键要求对应 Map
反复取最大或最小	`BinaryHeap<T>`	仅堆顶有序；peek `O(1)`，pop `O(log n)`
LIFO	`Vec<T>`	尾部 push/pop

不确定时先用 Vec，按键查询频繁时用 HashMap，要求确定顺序时用 BTreeMap 或显式排序。哈希表不承诺遍历顺序，随机种子与内部布局都可能影响它；测试应比较键值关系，而不是未排序的键列表。Set 可以理解为只关心键、不关心值的 Map，但应依赖各自公开 API，不依赖内部实现。

LinkedList 有节点分配和指针跳转成本，定位节点仍需遍历，通常不是列表或队列的默认选项。只有明确需要节点级操作并测量过实际工作负载时再考虑它；“插入 O(1)”并不包含查找插入位置的成本。

任务列表主例

只保留本例用到的 Todo 与 InProgress。remove 保序并移动后续元素；swap_remove 把尾元素放到被删位置，通常不保序。只读标题借用、修改标签和移出统计在这里仅展示使用方式，迭代器机制留给第 12 章。

独立示例（仅标准库；完整内容放 src/main.rs，Edition 2024；执行 cargo +stable run）。

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

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

#[derive(Debug, PartialEq)]
enum TaskState {
  Todo,
  InProgress { started_at: u64 },
}

struct Task {
  id: TaskId,
  title: String,
  state: TaskState,
  labels: Vec<String>,
}

fn main() {
  let mut tasks = Vec::with_capacity(4);
  tasks.push(Task {
    id: TaskId(1),
    title: "write docs".into(),
    state: TaskState::Todo,
    labels: vec!["docs".into()],
  });
  tasks.push(Task {
    id: TaskId(2),
    title: "fix build".into(),
    state: TaskState::InProgress { started_at: 100 },
    labels: vec!["ci".into(), "urgent".into()],
  });
  tasks.push(Task {
    id: TaskId(3),
    title: "review pr".into(),
    state: TaskState::Todo,
    labels: vec!["urgent".into()],
  });
  let removed = tasks.remove(0);
  assert_eq!(removed.id, TaskId(1));
  assert_eq!(tasks[0].title, "fix build");
  let titles: Vec<&str> = tasks.iter().map(|t| t.title.as_str()).collect();
  assert_eq!(titles, ["fix build", "review pr"]);
  for task in &mut tasks {
    if matches!(task.state, TaskState::Todo) {
      task.labels.push("unassigned".into());
    }
  }
  assert_eq!(tasks[1].labels, ["urgent", "unassigned"]);
  let total: usize = tasks.into_iter().map(|t| t.labels.len()).sum();
  assert_eq!(total, 4);

  let mut counts = HashMap::new();
  for label in ["urgent", "ci", "urgent", "docs", "urgent"] {
    *counts.entry(label).or_insert(0usize) += 1;
  }
  assert_eq!(counts.get("missing"), None);
  let mut pairs: Vec<_> = counts.iter().map(|(k, v)| (*k, *v)).collect();
  pairs.sort();
  assert_eq!(pairs, [("ci", 1), ("docs", 1), ("urgent", 3)]);
  let ordered: BTreeMap<_, _> = counts.into_iter().collect();
  assert_eq!(ordered.keys().copied().collect::<Vec<_>>(),
    ["ci", "docs", "urgent"]);

  let titles = ["fix build", "review pr"];
  assert_eq!(titles.get(7), None);
  assert_eq!(titles.get(1), Some(&"review pr"));
  let mut ids = vec![1, 2, 3];
  assert_eq!(ids.swap_remove(0), 1);
  assert_eq!(ids, [3, 2]);
}

空集合、缺键与 FIFO

空 Vec 的 first/pop、空堆的 peek/pop 返回 None。map.get 的缺键也是 None；索引 map[&key] 则可能 panic。外部未验证下标优先 get，内部已证明边界的索引可以直接访问。重复键的 insert 返回旧值并替换该键的值，Set 会去重，Vec 保留重复。