Rust 的标准库提供了丰富的容器类型，每个容器都有其特定的使用场景和性能特征。理解这些容器的特性对于编写高效、安全的 Rust 代码至关重要。

Vec- 动态数组

Vec<T> 是最常用的容器，类似于 C++ 的 std::vector 或 Python 的 list。它在堆上分配连续内存，支持动态扩容。

基本用法

// 创建
let mut vec = Vec::new();
let vec2 = vec![1, 2, 3];  // 宏创建
let vec3: Vec<i32> = Vec::with_capacity(10);  // 预分配容量

// 添加元素
vec.push(4);
vec.extend(&[5, 6]);

// 访问元素
let first = vec[0];           // 索引访问，越界会 panic
let second = vec.get(1);      // 安全访问，返回 Option<&T>

// 修改元素
vec[0] = 10;

// 删除元素
let last = vec.pop();         // 删除并返回最后一个元素
vec.remove(0);                // 删除指定位置元素

// 迭代
for item in &vec {
    println!("{}", item);
}

性能特点

  • 尾部操作: O(1) 均摊时间
  • 中间插入/删除: O(n)
  • 随机访问: O(1)
  • 内存: 连续分配，缓存友好

适用场景

  • 需要频繁尾部操作
  • 需要随机访问
  • 元素数量动态变化

VecDeque- 双端队列

VecDeque<T> 是双端队列，支持在头部和尾部高效地插入和删除元素。

基本用法

use std::collections::VecDeque;

let mut deque = VecDeque::new();

// 头部操作
deque.push_front(1);
let front = deque.pop_front();

// 尾部操作
deque.push_back(2);
let back = deque.pop_back();

// 访问
let first = deque.front();
let last = deque.back();

性能特点

  • 头部/尾部操作: O(1)
  • 中间操作: O(n)
  • 随机访问: O(1)

适用场景

  • 需要在两端频繁操作
  • 实现队列或栈
  • 滑动窗口算法

LinkedList- 双向链表

LinkedList<T> 是双向链表，每个节点独立分配内存。

基本用法

use std::collections::LinkedList;

let mut list = LinkedList::new();

list.push_back(1);
list.push_front(0);

// 迭代
for item in &list {
    println!("{}", item);
}

性能特点

  • 头部/尾部操作: O(1)
  • 中间操作: O(n)
  • 随机访问: O(n)
  • 内存: 不连续，缓存不友好

适用场景

  • 几乎不用。现代 CPU 的缓存机制使得链表性能很差
  • 除非确实需要频繁在中间插入/删除且不需要随机访问

HashMap<K, V> - 哈希表

HashMap<K, V> 提供键值对存储，基于哈希实现，平均 O(1) 的查找性能。

基本用法

use std::collections::HashMap;

let mut map = HashMap::new();

// 插入
map.insert("key1", 1);
map.entry("key2").or_insert(2);  // 不存在时插入

// 查找
if let Some(value) = map.get("key1") {
    println!("{}", value);
}

// 更新
*map.get_mut("key1").unwrap() = 10;

// 删除
map.remove("key1");

// 遍历
for (key, value) in &map {
    println!("{}: {}", key, value);
}

性能特点

  • 插入/查找/删除: O(1) 平均，O(n) 最坏
  • 内存: 额外存储哈希值

适用场景

  • 需要快速查找
  • 键无序要求
  • 键实现了 Hash 和 Eq

BTreeMap<K, V> - 有序映射

BTreeMap<K, V> 基于红黑树实现，按键排序存储。

基本用法

use std::collections::BTreeMap;

let mut map = BTreeMap::new();

map.insert(3, "c");
map.insert(1, "a");
map.insert(2, "b");

// 自动排序
for (key, value) in &map {
    println!("{}: {}", key, value);  // 输出: 1:a, 2:b, 3:c
}

// 范围查询
for (key, value) in map.range(2..=3) {
    println!("{}: {}", key, value);
}

性能特点

  • 插入/查找/删除: O(log n)
  • 范围查询: 高效
  • 内存: 比 HashMap 稍高

适用场景

  • 需要有序遍历
  • 需要范围查询
  • 键实现了 Ord

HashSet- 哈希集合

HashSet<T> 是只存储唯一值的集合，基于 HashMap 实现。

基本用法

use std::collections::HashSet;

let mut set = HashSet::new();

set.insert(1);
set.insert(2);
set.insert(1);  // 重复值会被忽略

// 查找
if set.contains(&1) {
    println!("Found 1");
}

// 集合运算
let set1: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
let set2: HashSet<i32> = [2, 3, 4].iter().cloned().collect();

let union: HashSet<_> = set1.union(&set2).cloned().collect();
let intersection: HashSet<_> = set1.intersection(&set2).cloned().collect();
let difference: HashSet<_> = set1.difference(&set2).cloned().collect();

适用场景

  • 去重
  • 快速判断元素是否存在
  • 集合运算

BTreeSet- 有序集合

BTreeSet<T> 是有序集合，基于 BTreeMap 实现。

基本用法

use std::collections::BTreeSet;

let mut set = BTreeSet::new();

set.insert(3);
set.insert(1);
set.insert(2);

// 自动排序
for item in &set {
    println!("{}", item);  // 输出: 1, 2, 3
}

// 范围查询
for item in set.range(2..=3) {
    println!("{}", item);
}

适用场景

  • 需要有序的唯一值
  • 需要范围查询

BinaryHeap- 二叉堆

BinaryHeap<T> 是最大堆，总是能快速获取最大值。

基本用法

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();

heap.push(1);
heap.push(5);
heap.push(3);

// 获取最大值
let max = heap.peek();  // Some(&5)

// 弹出最大值
let max = heap.pop();   // Some(5)

// 转换为排序的 Vec
let sorted: Vec<_> = heap.into_iter().collect();

性能特点

  • 插入: O(log n)
  • 获取最大值: O(1)
  • 弹出最大值: O(log n)

适用场景

  • 优先队列
  • Top K 问题
  • 堆排序

容器选择指南

需求推荐容器
动态数组，尾部操作Vec<T>
双端操作VecDeque<T>
快速查找HashMap<K, V>
有序查找BTreeMap<K, V>
去重HashSet<T>
优先队列BinaryHeap<T>