rust 源码版本: 1.72.0
文件位置
介绍
rust 标准库实现了一些常见的数据结构:
- 数组
Vec - 双端数组
VecDeque - 链表
LinkedList - 哈希map
HashMap - 按键排序map
BTreeMap - 哈希set
HashSet - 按键排序set
BTreeSet - 优先队列
BinaryHeap
Tips
Performance
Sequences :
| get(i) | insert(i) | remove(i) | append | split_off(i) | |
|---|---|---|---|---|---|
[Vec] |
O(1) | O(n-i)* | O(n-i) | O(m)* | O(n-i) |
[VecDeque] |
O(1) | O(min(i, n-i))* | O(min(i, n-i)) | O(m)* | O(min(i, n-i)) |
[LinkedList] |
O(min(i, n-i)) | O(min(i, n-i)) | O(min(i, n-i)) | O(1) | O(min(i, n-i)) |
Map :
| get | insert | remove | range | append | |
|---|---|---|---|---|---|
[HashMap] |
O(1)~ | O(1)~* | O(1)~ | N/A | N/A |
[BTreeMap] |
O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n+m) |
其中带 * 的为均摊复杂度，带 ~ 为期望复杂度。
Capacity Management
-
使用
with_capacity方法预先分配容器内存。 -
使用
reserve方法扩容。 -
使用
shrink_to_fit缩容。
Iterators
通常用 iter 、 iter_mut 、into_iter 迭代容器。