集合

是什么，为什么存在

集合（collection）把数量在运行时才能确定的同类值组织起来。 数组把长度写进类型，元组可以容纳不同类型；标准集合则为增长、删除、按键查找或排队等操作提供拥有型容器。 它们管理自己的元素，并在容器离开作用域时释放这些元素。

集合类型表达的不只是存储方式，也表达调用方依赖的语义。 Vec<T> 保留插入顺序并提供整数索引，HashSet<T> 表达唯一成员，HashMap<K, V> 表达从键到值的关系。 如果键顺序或范围查询属于契约，应选择 BTreeSet<T> 或 BTreeMap<K, V>；队列通常使用 VecDeque<T>。

String 也拥有可增长的缓冲区，但它维护 UTF-8 不变量，不属于 std::collections 模块。 文本索引与切片规则应单独学习，相关主题见 rust/strings。 BinaryHeap<T> 用于按优先级取出元素，本页只把它放进选择表，不展开其堆操作。

你会在解析输入、按标识符查找记录、去重、调度任务和构造响应时遇到集合。 先把所需语义说清楚，再选类型；仅仅因为 HashMap 看起来通用就默认使用它，往往会把顺序要求藏到输出阶段。

工作原理

Vec<T> 拥有一段连续的元素缓冲区，并分别记录长度与容量。 长度是已经初始化的元素数，容量是当前分配在重新分配前至少可以容纳的元素数。 push 增加长度；空间不足时，向量可以申请更大的缓冲区并搬移元素。

映射与集合围绕键的相等关系工作。 HashMap 与 HashSet 使用 哈希表（hash table） ，键要实现 Eq 和 Hash，而且相等的键必须产生相同哈希值。 BTreeMap 与 BTreeSet 使用 B 树（B-tree） 组织有序键，所以键要实现 Ord。

哈希集合不提供稳定的遍历顺序。 相同输入在另一次运行、换一个集合实例或发生修改后，都不应假定得到相同顺序。 B 树集合按键的 Ord 顺序遍历，因此更适合范围查询和必须可重复的键序列。

集合拥有插入其中的值。 把 String 插入 Vec<String> 会移动这个 String，除非代码插入的是克隆值；调用 iter() 则借用元素，调用 into_iter() 会消费容器并产出拥有型元素。 具体产出类型还取决于接收者是 T、&T 还是 &mut T。

从迭代器构造集合时，collect() 需要知道目标类型。 有时赋值左侧已经提供类型，有时要写 collect::<HashSet<_>>()。 这个类型信息决定重复项是否保留、键值对如何组织，以及结果是否保留顺序。

HashMap::entry 把“键已存在”和“键不存在”表示成同一个 条目 API（Entry API） 入口。 or_insert、or_default 与 and_modify 都在这项状态判断之上工作，并返回或操作映射中的值。 因此，计数和分组不必先调用 contains_key 再做第二次查找。

示例

用 Vec 完成一条数据流水线

第一个例子丢弃无效读数，再把摄氏度转换成十分之一华氏度。 into_iter() 消费原向量，collect() 的目标类型由 Vec<i32> 标注确定。

filter 的闭包接收对候选元素的引用，所以条件中解引用了 value。 map 随后取得通过筛选的 i32，结果仍按输入中有效读数的相对顺序排列。

get(1) 返回 Option<&i32>，不会因索引越界而 panic。 这里的元素实现 Copy，所以 copied() 把结果变成 Option<i32>；对 String 等非 Copy 类型，应根据需要保留借用或显式克隆。

用 HashMap::entry 计数

事件名作为借用的 &str 插入映射，因为它们都来自程序内的静态字符串。 每次 entry 调用只描述一次键，并直接取得对应计数器的可变引用。

use std::collections::HashMap;

fn main() {
    let events = ["view", "click", "view", "view", "click"];
    let mut counts: HashMap<&str, usize> = HashMap::new();

    for event in events {
        *counts.entry(event).or_insert(0) += 1;
    }

    // HashMap 不承诺顺序；输出前显式排序。
    let mut summary: Vec<_> = counts.into_iter().collect();
    summary.sort_by_key(|(event, _)| *event);

    for (event, count) in summary {
        println!("{event}: {count}");
    }
}

click: 2
view: 3

or_insert(0) 在键缺失时插入 0，随后无论原来是否存在，都返回 &mut usize。 解引用这个引用后，+= 1 更新的是映射里的值，而不是临时副本。

排序发生在输出边界，而不是假装 HashMap 自带顺序。 如果整个程序都依赖键顺序，下一例中的 BTreeMap 通常能更直接地表达契约。

用 BTreeMap 查询键范围

BTreeMap 的迭代器按键排序，range 接受 Rust 的范围边界。 下面只读取编号 20 到 30 的作业，并展示 insert 返回被替换的旧值。

use std::collections::BTreeMap;

fn main() {
    let mut jobs = BTreeMap::from([
        (30, "running"),
        (10, "done"),
        (20, "queued"),
        (40, "blocked"),
    ]);

    for (id, state) in jobs.range(20..=30) {
        println!("job {id}: {state}");
    }

    let previous = jobs.insert(20, "running");
    println!("replaced: {previous:?}");
}

job 20: queued
job 30: running
replaced: Some("queued")

输出次序来自键的 Ord 实现，不依赖插入次序。 范围的开始与结束都包含在内，所以编号 20 和 30 都会出现。

insert 会移动新值并返回 Option<V>。 调用方可以区分首次插入与覆盖已有值；忽略返回值则表示业务逻辑不关心被替换的内容。

用 VecDeque 表达队列

队列从尾部接收任务，从头部取出任务。 VecDeque 直接提供这两个方向的操作，不需要把 Vec 的首元素反复删除。

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::from(["parse", "index", "publish"]);

    if let Some(task) = queue.pop_front() {
        println!("running: {task}");
    }

    queue.push_back("notify");

    while let Some(task) = queue.pop_front() {
        println!("next: {task}");
    }

    println!("empty: {}", queue.is_empty());
}

running: parse
next: index
next: publish
next: notify
empty: true

pop_front() 返回 Option<T>，同时把元素所有权移出队列。 while let 在队列变空时自然结束，不需要先检查长度再弹出。

队列的逻辑顺序不意味着底层内存始终是一段连续切片。 需要把内容交给要求连续切片的 API 时，应使用 make_contiguous()，而不是依赖内部布局。

陷阱

修复方法： 使用 get 或 get_mut，并在 None 分支返回领域错误或跳过记录。 只有程序不变量已经证明索引有效，而且违反不变量确实应当终止当前执行时，才使用直接索引。

修复方法： 若顺序贯穿整个业务逻辑，使用 B 树集合；若只在边界需要稳定输出，则先收集并按明确键排序。 测试映射本身时，可以比较键值关系，不要比较偶然的调试字符串。

修复方法： 只读遍历使用 iter()，消费容器才使用 into_iter()；字符串键通常可以直接用 &str 查找。 确实需要让新容器长期拥有独立数据时再克隆，并在类型签名中表达这个所有权边界。

修复方法： 使用 entry(key)，在 Occupied 与 Vacant 状态上完成一次更新。 简单计数使用 or_insert，分组容器常可使用 or_default，存在时修改则可组合 and_modify。

修复方法： 延迟构造使用 or_insert_with(build_value)，默认值就是 Default::default() 时使用 or_default()。 审查时要区分“传入一个已经算好的值”和“传入一个只在缺失时调用的闭包”。

延伸阅读

• Rust 标准库：集合
• Rust 标准库：Vec
• Rust 标准库：Entry
• Rust 标准库：BTreeMap
• Rust 标准库：VecDeque