常用集合

在 Rust 标准库 std::collections 模块下，集合被分为四大通用类型 线性序列 、Key-Value 映射表 、集合类型和 优先队列 。这些集合存储在堆内存中，并通过指针（如引用、智能指针）进行管理。

一、 线性序列 (Linear Sequences)

这类集合按顺序存储数据，适合处理列表、队列等逻辑。

• 向量 (Vec) ：最常用的动态数组。支持快速随机访问，在末尾插入/删除效率最高。
• 双端队列 (VecDeque) ：基于循环缓冲区实现。在序列的头部和尾部插入或删除数据都非常高效。
• 链表 (LinkedList) ：双向链表。虽然支持快速合并和拆分，但由于内存不连续，现代硬件上性能通常不如 Vec。

代码示例：Vec 与 VecDeque

use std::collections::VecDeque;

fn main() {
    // 1. Vec: 动态数组
    let mut v = vec![1, 2, 3];
    v.push(4); 
    println!("Vec 第三个元素: {}", v[2]); // 随机访问

    // 2. VecDeque: 双端操作
    let mut dq = VecDeque::new();
    dq.push_back(10); // 尾部插入
    dq.push_front(20); // 头部插入
    println!("Deque 头部: {:?}", dq.front()); // 输出 Some(20)
}

二、 Key-Value 映射表 (Key-Value Maps)

映射表用于存储“键-值”对，通过键来快速查找对应的值。

• 无序哈希表 (HashMap) ：通过哈希函数存储。查找速度极快（平均 $O(1)$），但由于哈希冲突和重新分配，内部顺序是无序的。
• 有序哈希表 (BTreeMap) ：基于 B 树实现。键（Key）必须实现 Ord 特征，数据会按键的大小自动排序存储。

代码示例：HashMap 与 BTreeMap

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

fn main() {
    // 1. HashMap: 无序
    let mut scores = HashMap::new();
    scores.insert("Alice", 90);
    scores.insert("Bob", 85);

    // 2. BTreeMap: 自动排序
    let mut sorted_map = BTreeMap::new();
    sorted_map.insert(3, "c");
    sorted_map.insert(1, "a");
    sorted_map.insert(2, "b");

    // 遍历 BTreeMap 时，顺序始终是 1, 2, 3
    for (key, value) in &sorted_map {
        println!("{}: {}", key, value);
    }
}

三、 集合类型 (Set Types)

集合类型实际上是不带“值”的映射表，主要用于保证元素的 唯一性 。

• 无序集合 (HashSet) ：基于 HashMap 实现。用于快速去重或检查某个元素是否存在。
• 有序集合 (BTreeSet) ：基于 BTreeMap 实现。元素会根据自身顺序进行 排序 。

代码示例：HashSet 的去重功能

use std::collections::HashSet;

fn main() {
    let mut books = HashSet::new();
    books.insert("Rust Programming");
    books.insert("Rust Programming"); // 重复插入会被忽略

    if !books.contains("C++") {
        println!("我们没有找到关于 C++ 的书。");
    }
}

四、 优先队列 (Priority Queues)

当需要始终优先处理“最大”或“最小”的元素时，使用此类集合。

• 二叉堆 (BinaryHeap) ：默认是 最大堆 。无论插入顺序如何，每次弹出的总是集合中最大的元素。

代码示例：BinaryHeap

use std::collections::BinaryHeap;

fn main() {
    let mut heap = BinaryHeap::new();

    // 乱序插入
    heap.push(1);
    heap.push(5);
    heap.push(2);

    // 总是弹出当前最大的值
    println!("弹出最大值: {:?}", heap.pop()); // 输出 Some(5)
    println!("再次弹出: {:?}", heap.pop());   // 输出 Some(2)
}

总结：如何选择集合？