Rust Containers

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);
}

创建方法

方法	说明
Vec::new()	创建空 Vec
vec![...]	宏创建，如 vec![1, 2, 3]
Vec::with_capacity(n)	预分配 n 个元素的容量
vec![0; 10]	创建包含 10 个 0 的 Vec
iter.collect()	从迭代器收集，如 (0..5).collect::<Vec<_>>()

常用方法

方法	签名	说明
添加
push	push(x: T)	尾部添加元素
pop	pop() -> Option<T>	尾部弹出元素
insert	insert(index: usize, element: T)	在指定位置插入
append	append(&mut other: Vec<T>)	追加另一个 Vec（清空 other）
extend	extend(iter: I)	扩展迭代器元素
删除
remove	remove(index: usize) -> T	删除并返回指定位置元素
swap_remove	swap_remove(index: usize) -> T	用最后一个替换并删除，O(1)
truncate	truncate(len: usize)	截断到指定长度
clear	clear()	清空所有元素
drain	drain(range: R) -> Drain<T>	删除并返回范围内元素
split_off	split_off(at: usize) -> Vec<T>	从指定位置分割为两个 Vec
访问
get	get(index: usize) -> Option<&T>	安全索引访问
first	first() -> Option<&T>	获取首元素
last	last() -> Option<&T>	获取尾元素
get_mut	get_mut(index: usize) -> Option<&mut T>	安全可变访问
查询
len	len() -> usize	元素数量
is_empty	is_empty() -> bool	是否为空
contains	contains(&T) -> bool	是否包含元素（需 PartialEq）
capacity	capacity() -> usize	当前容量
容量管理
reserve	reserve(additional: usize)	预留额外空间
shrink_to_fit	shrink_to_fit()	释放多余容量
with_capacity	with_capacity(capacity: usize)	创建时指定容量
变换
sort	sort()	原地排序（需 Ord）
sort_by	sort_by(cmp: F)	自定义比较器排序
reverse	reverse()	原地反转
dedup	dedup()	删除连续重复元素（需 PartialEq）
retain	retain(f: F)	保留满足条件的元素
resize	resize(new_len: usize, value: T)	调整大小，新增位置填充 value

性能特点

• 尾部操作: 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();

// 容量管理
deque.reserve(10);
deque.shrink_to_fit();

// 旋转操作
deque.rotate_left(2);  // 向左旋转 2 个位置
deque.rotate_right(1); // 向右旋转 1 个位置

// 使内存连续（返回连续切片）
let (a, b) = deque.as_slices();  // 可能返回两个不连续切片
let slice = deque.make_contiguous();  // 整理为连续内存

创建方法

方法	说明
VecDeque::new()	创建空双端队列
VecDeque::with_capacity(n)	预分配 n 个元素的容量
iter.collect()	从迭代器收集

常用方法

方法	签名	说明
头部操作
push_front	push_front(x: T)	头部添加
pop_front	pop_front() -> Option<T>	头部弹出
front	front() -> Option<&T>	获取头部元素
front_mut	front_mut() -> Option<&mut T>	获取头部可变引用
尾部操作
push_back	push_back(x: T)	尾部添加
pop_back	pop_back() -> Option<T>	尾部弹出
back	back() -> Option<&T>	获取尾部元素
back_mut	back_mut() -> Option<&mut T>	获取尾部可变引用
通用操作
get	get(index: usize) -> Option<&T>	按索引访问
get_mut	get_mut(index: usize) -> Option<&mut T>	按索引可变访问
swap	swap(i: usize, j: usize)	交换两个位置的元素
len	len() -> usize	元素数量
is_empty	is_empty() -> bool	是否为空
clear	clear()	清空
contains	contains(&T) -> bool	是否包含（需 PartialEq）
capacity	capacity() -> usize	当前容量
reserve	reserve(additional: usize)	预留空间
shrink_to_fit	shrink_to_fit()	释放多余容量
特殊操作
rotate_left	rotate_left(n: usize)	向左旋转 n 个位置
rotate_right	rotate_right(n: usize)	向右旋转 n 个位置
make_contiguous	make_contiguous() -> &mut [T]	整理为连续内存，返回切片
as_slices	as_slices() -> (&[T], &[T])	返回可能不连续的两个切片

性能特点

• 头部/尾部操作: 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);
}

// 在指定节点前后插入（需要可变游标）
{
    let mut cursor = list.cursor_mut();
    cursor.move_next();
    cursor.insert_after(99);
}

创建方法

方法	说明
LinkedList::new()	创建空链表
iter.collect()	从迭代器收集

常用方法

方法	签名	说明
添加
push_front	push_front(x: T)	头部添加
push_back	push_back(x: T)	尾部添加
append	append(&mut other: LinkedList<T>)	追加另一个链表（清空 other）
prepend	prepend(&mut other: LinkedList<T>)	在头部前置另一个链表
删除
pop_front	pop_front() -> Option<T>	头部弹出
pop_back	pop_back() -> Option<T>	尾部弹出
clear	clear()	清空链表
访问
front	front() -> Option<&T>	获取头部元素
front_mut	front_mut() -> Option<&mut T>	获取头部可变引用
back	back() -> Option<&T>	获取尾部元素
back_mut	back_mut() -> Option<&mut T>	获取尾部可变引用
查询
len	len() -> usize	元素数量
is_empty	is_empty() -> bool	是否为空
contains	contains(&T) -> bool	是否包含（需 PartialEq）
特殊操作
split_off	split_off(at: usize) -> LinkedList<T>	从指定位置分割
cursor_mut	cursor_mut() -> CursorMut<T>	获取可变游标，支持在游标位置插入/删除

性能特点

• 头部/尾部操作: 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);
}

// 批量操作
let has_key = map.contains_key("key1");
let len = map.len();
map.clear();

// Entry API 高级用法
map.entry("key3")
    .and_modify(|v| *v += 1)    // 存在时修改
    .or_insert(0);              // 不存在时插入

创建方法

方法	说明
HashMap::new()	创建空 HashMap
HashMap::with_capacity(n)	预分配容量
iter.collect()	从迭代器收集，如 (0..5).map(|i| (i, i*i)).collect::<HashMap<_, _>>()
From<[(K, V); N]>	从数组创建，如 HashMap::from([("a", 1), ("b", 2)])

常用方法

方法	签名	说明
插入/删除
insert	insert(k: K, v: V) -> Option<V>	插入键值对，返回旧值（如有）
remove	remove(&k) -> Option<V>	删除并返回值
remove_entry	remove_entry(&k) -> Option<(K, V)>	删除并返回键值对
clear	clear()	清空
retain	retain(f: F)	保留满足条件的键值对
查找
get	get(&k) -> Option<&V>	获取值引用
get_mut	get_mut(&k) -> Option<&mut V>	获取可变引用
contains_key	contains_key(&k) -> bool	是否包含键
entry	entry(k: K) -> Entry<K, V>	获取 Entry（见下文）
批量操作
keys	keys() -> Keys<K, V>	返回所有键的迭代器
values	values() -> Values<K, V>	返回所有值的迭代器
values_mut	values_mut() -> ValuesMut<K, V>	返回所有可变值的迭代器
into_keys	into_keys() -> IntoKeys<K, V>	消耗 map，返回键的迭代器
into_values	into_values() -> IntoValues<K, V>	消耗 map，返回值的迭代器
extend	extend(iter: I)	扩展迭代器
查询
len	len() -> usize	键值对数量
is_empty	is_empty() -> bool	是否为空
capacity	capacity() -> usize	当前容量
reserve	reserve(additional: usize)	预留空间
shrink_to_fit	shrink_to_fit()	释放多余容量

Entry API

Entry API 提供了一种高效的方式来处理"如果不存在则插入，存在则更新"的逻辑：

方法	说明
or_insert(v)	不存在时插入 v，返回 &mut V
or_insert_with(f)	不存在时用闭包计算值插入，返回 &mut V
or_default()	不存在时插入默认值，返回 &mut V
and_modify(f)	存在时用闭包修改值，返回 Self 支持链式调用
key()	获取 entry 的键引用

性能特点

• 插入/查找/删除: 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);
}

// 获取首尾元素
if let Some((&first_k, &first_v)) = map.first_key_value() {
    println!("first: {} = {}", first_k, first_v);
}
if let Some((&last_k, &last_v)) = map.last_key_value() {
    println!("last: {} = {}", last_k, last_v);
}

// 分割
let map2 = map.split_off(&2);  // 键 >= 2 的元素移动到 map2

创建方法

方法	说明
BTreeMap::new()	创建空 BTreeMap
iter.collect()	从迭代器收集
From<[(K, V); N]>	从数组创建

常用方法

方法	签名	说明
插入/删除
insert	insert(k: K, v: V) -> Option<V>	插入键值对，返回旧值
remove	remove(&k) -> Option<V>	删除并返回值
remove_entry	remove_entry(&k) -> Option<(K, V)>	删除并返回键值对
clear	clear()	清空
retain	retain(f: F)	保留满足条件的键值对
查找
get	get(&k) -> Option<&V>	获取值引用
get_mut	get_mut(&k) -> Option<&mut V>	获取可变引用
contains_key	contains_key(&k) -> bool	是否包含键
entry	entry(k: K) -> Entry<K, V>	获取 Entry
范围操作
range	range(range: R) -> Range<K, V>	返回范围内的键值对迭代器
range_mut	range_mut(range: R) -> RangeMut<K, V>	返回范围内的可变迭代器
边界访问
first_key_value	first_key_value() -> Option<(&K, &V)>	获取最小键值对
last_key_value	last_key_value() -> Option<(&K, &V)>	获取最大键值对
pop_first	pop_first() -> Option<(K, V)>	删除并返回最小键值对
pop_last	pop_last() -> Option<(K, V)>	删除并返回最大键值对
分割/追加
split_off	split_off(&K) -> BTreeMap<K, V>	从指定键分割为两个 map
append	append(&mut other: BTreeMap<K, V>)	合并另一个 map
批量操作
keys	keys() -> Keys<K, V>	返回所有键的迭代器
values	values() -> Values<K, V>	返回所有值的迭代器
values_mut	values_mut() -> ValuesMut<K, V>	返回所有可变值的迭代器
查询
len	len() -> usize	键值对数量
is_empty	is_empty() -> bool	是否为空

性能特点

• 插入/查找/删除: 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();

// 其他操作
let is_subset = set1.is_subset(&set2);      // set1 是否是 set2 的子集
let is_superset = set1.is_superset(&set2);  // set1 是否是 set2 的超集
let is_disjoint = set1.is_disjoint(&set2);  // 两个集合是否不相交

创建方法

方法	说明
HashSet::new()	创建空 HashSet
HashSet::with_capacity(n)	预分配容量
iter.collect()	从迭代器收集
From<[T; N]>	从数组创建

常用方法

方法	签名	说明
添加/删除
insert	insert(T) -> bool	插入元素，返回是否为新元素
remove	remove(&T) -> bool	删除元素，返回是否成功
take	take(&T) -> Option<T>	删除并返回元素
clear	clear()	清空
retain	retain(f: F)	保留满足条件的元素
查找
contains	contains(&T) -> bool	是否包含元素
get	get(&T) -> Option<&T>	获取元素引用（可用于自定义类型的等价比较）
集合运算
union	union(&HashSet<T>) -> Union<T>	并集迭代器
intersection	intersection(&HashSet<T>) -> Intersection<T>	交集迭代器
difference	difference(&HashSet<T>) -> Difference<T>	差集迭代器
symmetric_difference	symmetric_difference(&HashSet<T>) -> SymmetricDifference<T>	对称差集迭代器
关系判断
is_subset	is_subset(&HashSet<T>) -> bool	是否为子集
is_superset	is_superset(&HashSet<T>) -> bool	是否为超集
is_disjoint	is_disjoint(&HashSet<T>) -> bool	是否不相交
批量操作
iter	iter() -> Iter<T>	返回迭代器
drain	drain() -> Drain<T>	清空并返回所有元素
extend	extend(iter: I)	扩展迭代器
查询
len	len() -> usize	元素数量
is_empty	is_empty() -> bool	是否为空
capacity	capacity() -> usize	当前容量
reserve	reserve(additional: usize)	预留空间
shrink_to_fit	shrink_to_fit()	释放多余容量

适用场景

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

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);
}

// 获取首尾元素
if let Some(&first) = set.first() {
    println!("first: {}", first);
}
if let Some(&last) = set.last() {
    println!("last: {}", last);
}

// 弹出元素
let min = set.pop_first();  // 删除并返回最小值
let max = set.pop_last();   // 删除并返回最大值

创建方法

方法	说明
BTreeSet::new()	创建空 BTreeSet
iter.collect()	从迭代器收集
From<[T; N]>	从数组创建

常用方法

方法	签名	说明
添加/删除
insert	insert(T) -> bool	插入元素，返回是否为新元素
remove	remove(&T) -> bool	删除元素，返回是否成功
take	take(&T) -> Option<T>	删除并返回元素
clear	clear()	清空
retain	retain(f: F)	保留满足条件的元素
查找
contains	contains(&T) -> bool	是否包含元素
range	range(range: R) -> Range<T>	返回范围内的迭代器
边界访问
first	first() -> Option<&T>	获取最小元素
last	last() -> Option<&T>	获取最大元素
pop_first	pop_first() -> Option<T>	删除并返回最小元素
pop_last	pop_last() -> Option<T>	删除并返回最大元素
集合运算
union	union(&BTreeSet<T>) -> Union<T>	并集迭代器
intersection	intersection(&BTreeSet<T>) -> Intersection<T>	交集迭代器
difference	difference(&BTreeSet<T>) -> Difference<T>	差集迭代器
symmetric_difference	symmetric_difference(&BTreeSet<T>) -> SymmetricDifference<T>	对称差集迭代器
关系判断
is_subset	is_subset(&BTreeSet<T>) -> bool	是否为子集
is_superset	is_superset(&BTreeSet<T>) -> bool	是否为超集
is_disjoint	is_disjoint(&BTreeSet<T>) -> bool	是否不相交
分割/追加
split_off	split_off(&T) -> BTreeSet<T>	从指定元素分割为两个集合
append	append(&mut other: BTreeSet<T>)	合并另一个集合
批量操作
iter	iter() -> Iter<T>	返回迭代器
查询
len	len() -> usize	元素数量
is_empty	is_empty() -> bool	是否为空

适用场景

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

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();

// 其他方法
let len = heap.len();
heap.clear();

创建方法

方法	说明
BinaryHeap::new()	创建空堆
BinaryHeap::with_capacity(n)	预分配容量
iter.collect()	从迭代器收集
From<Vec<T>>	从 Vec 创建（高效 O(n)）
From<[T; N]>	从数组创建

常用方法

方法	签名	说明
添加/删除
push	push(item: T)	添加元素
pop	pop() -> Option<T>	弹出最大元素
clear	clear()	清空
访问
peek	peek() -> Option<&T>	查看最大元素（不移除）
peek_mut	peek_mut() -> Option<PeekMut<T>>	查看并可变修改最大元素
变换
into_sorted_vec	into_sorted_vec() -> Vec<T>	消耗堆，返回排序后的 Vec
into_iter	into_iter() -> IntoIter<T>	消耗堆，返回迭代器（返回顺序不确定）
批量操作
append	append(&mut other: BinaryHeap<T>)	合并另一个堆
extend	extend(iter: I)	扩展迭代器
查询
len	len() -> usize	元素数量
is_empty	is_empty() -> bool	是否为空
capacity	capacity() -> usize	当前容量
reserve	reserve(additional: usize)	预留空间
shrink_to_fit	shrink_to_fit()	释放多余容量

自定义比较

默认是最大堆，可以通过实现 Ord trait 或使用 std::cmp::Reverse 创建最小堆：

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

// 最小堆
let mut min_heap = BinaryHeap::new();
min_heap.push(Reverse(5));
min_heap.push(Reverse(1));
min_heap.push(Reverse(3));

while let Some(Reverse(x)) = min_heap.pop() {
    println!("{}", x);  // 输出: 1, 3, 5
}

性能特点

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

适用场景

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

容器选择指南

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