本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-09 08:02:08
在 C++ STL 中，vector、list 和 deque 是三种常用的顺序容器，它们的相同点与不同点对比如下：
相同点
- 动态容器
均支持动态扩容/缩容，无需手动管理内存，容量随元素增减自动变化。 - 顺序存储
元素按插入顺序存储（逻辑连续），支持顺序遍历。 - 迭代器支持
提供随机访问迭代器（vector、deque）或双向迭代器（list），支持begin()/end()遍历。 - 通用操作
支持push_back()、pop_back()、insert()、erase()、size()、empty()等基本操作。
不同点
| 特性 | vector | list | deque |
|---|---|---|---|
| 底层结构 | 动态数组 | 双向链表 | 分块数组（多个连续块） |
| 随机访问 | ✅ O(1) | ❌ O(n) | ✅ O(1)（接近 vector） |
| 中间插入/删除 | ❌ O(n)（需移动元素） | ✅ O(1)（已知迭代器位置） | ❌ O(n)（需移动元素） |
| 头尾插入/删除 | ✅ 尾端 O(1)，头端 O(n) | ✅ 头尾 O(1) | ✅ 头尾 O(1) |
| 内存连续性 | ✅ 完全连续 | ❌ 非连续（节点分散） | ❌ 逻辑连续，物理分块 |
| 内存分配策略 | 扩容时重新分配整个数组 | 按需分配单个节点 | 按需分配内存块（无需全拷贝） |
| 迭代器失效场景 | 扩容后全部失效 | 删除时仅当前元素迭代器失效 | 中间插入/删除可能导致失效 |
| 内存占用 | 最低（仅元素内存） | 较高（含前后指针） | 中等（含块指针表） |
核心差异总结
访问模式
vector：适合频繁随机访问（如v[i]）和尾部操作。deque：适合频繁头尾插入/删除，随机访问性能接近vector。list：适合频繁中间插入/删除，但无法快速随机访问。
内存效率
vector：内存紧凑，缓存友好，但扩容成本高。list：内存碎片化，但无扩容开销。deque：折中设计，兼顾头尾操作和随机访问。
迭代器稳定性
list的迭代器最稳定（除非元素被删除）。vector扩容后所有迭代器失效。deque在中间修改时可能局部失效。
典型应用场景
vector：需要快速随机访问（如数值计算、动态数组）。list：需要频繁中间插入/删除（如 LRU 缓存链表）。deque：需要高效头尾操作（如任务队列、滑动窗口）。
根据具体需求选择容器，可显著优化程序性能和内存效率。
鲁ICP备2025150228号