470 lines
4.8 KiB
Markdown
470 lines
4.8 KiB
Markdown
在 Rust 里，`std::collections` 其实不只有 `HashMap` 和 `HashSet`。标准库给的集合虽然不多，但**每一个都很经典，而且用途非常明确**。整体大概可以分成三类：
|
||
|
||
1️⃣ **哈希结构**
|
||
2️⃣ **有序结构（树）**
|
||
3️⃣ **队列 / 双端结构**
|
||
|
||
我给你**完整列一遍，并且说明用途和核心方法**。
|
||
|
||
---
|
||
|
||
# 一、Hash 类（你已经在用）
|
||
|
||
```rust
|
||
use std::collections::{HashMap, HashSet};
|
||
```
|
||
|
||
## 1 `HashMap<K,V>`
|
||
|
||
哈希表键值对。
|
||
|
||
特点：
|
||
|
||
* O(1) 平均查找
|
||
* 无序
|
||
* 最常用
|
||
|
||
常见用途：
|
||
|
||
* 字典
|
||
* 统计
|
||
* cache
|
||
|
||
你已经基本掌握。
|
||
|
||
---
|
||
|
||
## 2 `HashSet<T>`
|
||
|
||
哈希集合。
|
||
|
||
特点：
|
||
|
||
* 元素唯一
|
||
* 无序
|
||
* 基于 HashMap 实现
|
||
|
||
常见用途：
|
||
|
||
* 去重
|
||
* 集合运算
|
||
|
||
---
|
||
|
||
# 二、有序结构（基于红黑树）
|
||
|
||
```rust
|
||
use std::collections::{BTreeMap, BTreeSet};
|
||
```
|
||
|
||
Rust 标准库没有 `TreeMap`，而是 **BTree**。
|
||
|
||
原因：
|
||
|
||
BTree 对 CPU cache 更友好。
|
||
|
||
---
|
||
|
||
## 3 `BTreeMap<K,V>`
|
||
|
||
有序 map。
|
||
|
||
特点：
|
||
|
||
* key 自动排序
|
||
* O(log n) 查询
|
||
|
||
例子：
|
||
|
||
```rust
|
||
use std::collections::BTreeMap;
|
||
|
||
let mut map = BTreeMap::new();
|
||
map.insert(3, "c");
|
||
map.insert(1, "a");
|
||
map.insert(2, "b");
|
||
|
||
for (k,v) in &map {
|
||
println!("{} {}", k, v);
|
||
}
|
||
```
|
||
|
||
输出：
|
||
|
||
```
|
||
1 a
|
||
2 b
|
||
3 c
|
||
```
|
||
|
||
---
|
||
|
||
### 常见方法
|
||
|
||
基本和 HashMap 一样：
|
||
|
||
```
|
||
insert
|
||
get
|
||
remove
|
||
contains_key
|
||
entry
|
||
```
|
||
|
||
但多了 **范围查询**：
|
||
|
||
```rust
|
||
map.range(2..5)
|
||
```
|
||
|
||
这个功能非常强。
|
||
|
||
例如：
|
||
|
||
```rust
|
||
for (k,v) in map.range(10..20) {
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
### 使用场景
|
||
|
||
* 排序数据
|
||
* 区间查询
|
||
* ordered dictionary
|
||
|
||
---
|
||
|
||
## 4 `BTreeSet<T>`
|
||
|
||
有序集合。
|
||
|
||
特点：
|
||
|
||
* 自动排序
|
||
* 唯一元素
|
||
|
||
例子：
|
||
|
||
```rust
|
||
use std::collections::BTreeSet;
|
||
|
||
let mut set = BTreeSet::new();
|
||
|
||
set.insert(3);
|
||
set.insert(1);
|
||
set.insert(2);
|
||
|
||
for v in &set {
|
||
println!("{}", v);
|
||
}
|
||
```
|
||
|
||
输出：
|
||
|
||
```
|
||
1
|
||
2
|
||
3
|
||
```
|
||
|
||
---
|
||
|
||
# 三、队列结构
|
||
|
||
## 5 `VecDeque<T>`
|
||
|
||
双端队列。
|
||
|
||
```rust
|
||
use std::collections::VecDeque;
|
||
```
|
||
|
||
结构：
|
||
|
||
```
|
||
head -> circular buffer <- tail
|
||
```
|
||
|
||
特点：
|
||
|
||
* 两端 O(1) 插入删除
|
||
* 比 `Vec` 更适合做队列
|
||
|
||
---
|
||
|
||
### 常见方法
|
||
|
||
插入：
|
||
|
||
```rust
|
||
push_back()
|
||
push_front()
|
||
```
|
||
|
||
删除：
|
||
|
||
```rust
|
||
pop_back()
|
||
pop_front()
|
||
```
|
||
|
||
查看：
|
||
|
||
```rust
|
||
front()
|
||
back()
|
||
```
|
||
|
||
例子：
|
||
|
||
```rust
|
||
let mut q = VecDeque::new();
|
||
|
||
q.push_back(1);
|
||
q.push_back(2);
|
||
q.push_front(0);
|
||
|
||
println!("{:?}", q);
|
||
```
|
||
|
||
---
|
||
|
||
### 使用场景
|
||
|
||
* BFS
|
||
* 任务队列
|
||
* sliding window
|
||
|
||
---
|
||
|
||
# 四、链表
|
||
|
||
## 6 `LinkedList<T>`
|
||
|
||
```rust
|
||
use std::collections::LinkedList;
|
||
```
|
||
|
||
双向链表。
|
||
|
||
操作：
|
||
|
||
```
|
||
push_back
|
||
push_front
|
||
pop_back
|
||
pop_front
|
||
```
|
||
|
||
例子：
|
||
|
||
```rust
|
||
let mut list = LinkedList::new();
|
||
|
||
list.push_back(1);
|
||
list.push_back(2);
|
||
list.push_front(0);
|
||
```
|
||
|
||
---
|
||
|
||
⚠️ Rust 官方建议：
|
||
|
||
**尽量不要用 LinkedList。**
|
||
|
||
原因：
|
||
|
||
* cache locality 差
|
||
* VecDeque 更快
|
||
|
||
除非：
|
||
|
||
* 频繁 splice
|
||
* 复杂链表操作
|
||
|
||
---
|
||
|
||
# 五、BinaryHeap（非常重要）
|
||
|
||
## 7 `BinaryHeap<T>`
|
||
|
||
```rust
|
||
use std::collections::BinaryHeap;
|
||
```
|
||
|
||
二叉堆。
|
||
|
||
默认：
|
||
|
||
```
|
||
最大堆
|
||
```
|
||
|
||
例子：
|
||
|
||
```rust
|
||
let mut heap = BinaryHeap::new();
|
||
|
||
heap.push(3);
|
||
heap.push(1);
|
||
heap.push(5);
|
||
|
||
println!("{:?}", heap.pop());
|
||
```
|
||
|
||
输出：
|
||
|
||
```
|
||
Some(5)
|
||
```
|
||
|
||
---
|
||
|
||
### 常见方法
|
||
|
||
```
|
||
push
|
||
pop
|
||
peek
|
||
len
|
||
is_empty
|
||
```
|
||
|
||
---
|
||
|
||
### 变成最小堆
|
||
|
||
使用：
|
||
|
||
```
|
||
std::cmp::Reverse
|
||
```
|
||
|
||
例子：
|
||
|
||
```rust
|
||
use std::cmp::Reverse;
|
||
|
||
let mut heap = BinaryHeap::new();
|
||
|
||
heap.push(Reverse(3));
|
||
heap.push(Reverse(1));
|
||
|
||
println!("{:?}", heap.pop());
|
||
```
|
||
|
||
---
|
||
|
||
### 使用场景
|
||
|
||
* Dijkstra
|
||
* 优先队列
|
||
* 调度系统
|
||
|
||
---
|
||
|
||
# 六、collections 全部结构总结
|
||
|
||
Rust 标准库集合其实只有 **7 个核心结构**：
|
||
|
||
```
|
||
HashMap
|
||
HashSet
|
||
BTreeMap
|
||
BTreeSet
|
||
VecDeque
|
||
LinkedList
|
||
BinaryHeap
|
||
```
|
||
|
||
---
|
||
|
||
# 七、Rust collections 使用频率排行（真实项目）
|
||
|
||
大致是：
|
||
|
||
```
|
||
HashMap ⭐⭐⭐⭐⭐
|
||
VecDeque ⭐⭐⭐⭐
|
||
HashSet ⭐⭐⭐⭐
|
||
BinaryHeap ⭐⭐⭐
|
||
BTreeMap ⭐⭐
|
||
BTreeSet ⭐⭐
|
||
LinkedList ⭐
|
||
```
|
||
|
||
---
|
||
|
||
# 八、很多人不知道的一点
|
||
|
||
Rust **最常用容器其实是 `Vec`**：
|
||
|
||
```
|
||
Vec<T>
|
||
```
|
||
|
||
但它在：
|
||
|
||
```
|
||
std::vec
|
||
```
|
||
|
||
不是 `collections`。
|
||
|
||
原因：
|
||
|
||
Vec 太重要了，直接放 core。
|
||
|
||
---
|
||
|
||
# 九、如果你想系统练习 Rust collections
|
||
|
||
我非常推荐你写这几个小项目：
|
||
|
||
1️⃣ **词频统计**
|
||
|
||
```
|
||
HashMap
|
||
```
|
||
|
||
2️⃣ **LRU Cache**
|
||
|
||
```
|
||
HashMap + LinkedList
|
||
```
|
||
|
||
3️⃣ **Dijkstra**
|
||
|
||
```
|
||
BinaryHeap
|
||
```
|
||
|
||
4️⃣ **任务调度器**
|
||
|
||
```
|
||
BinaryHeap + HashMap
|
||
```
|
||
|
||
5️⃣ **滑动窗口最大值**
|
||
|
||
```
|
||
VecDeque
|
||
```
|
||
|
||
---
|
||
|
||
如果你愿意，我可以再给你一个：
|
||
|
||
**🔥「Rust collections 深度指南（90% Rust 程序员不知道的细节）」**
|
||
|
||
比如：
|
||
|
||
* 为什么 Rust 没有 `TreeMap`
|
||
* 为什么 `LinkedList` 几乎没人用
|
||
* `HashMap` 为什么这么快
|
||
* `BTreeMap` 内部结构其实不是二叉树
|
||
|
||
这些底层实现其实非常有意思。
|