容器选择的三维决策模型

在 C++ 中选择 std::vector、std::list 或 std::deque 时，需权衡以下三个维度：

访问模式

• 随机访问（通过索引）：vector 和 deque 效率高（O(1)），list 效率低（O(n)）。
• 头尾操作：deque 的 push_front/pop_front 和 push_back/pop_back 均为 O(1)，vector 的 push_front 是 O(n)。
• 遍历：三者均为 O(n)，但 vector 和 deque 因内存连续，缓存命中率更高。

修改模式

• 中间插入/删除：list 为 O(1)，vector 和 deque 为 O(n)。
• 频繁扩容：vector 扩容可能导致拷贝开销，deque 和 list 无此问题。
• 元素大小：大对象在 vector 中移动成本高，适合用 list。

迭代器稳定性

• vector：插入/删除可能使所有迭代器失效。
• deque：中间修改使所有迭代器失效，头尾操作仅影响局部。
• list：迭代器始终稳定（除非元素被删除）。

---

std::list：双向链表

结构特征

• 节点存储：每个元素独立分配内存，通过指针连接。
• 内存开销：每个节点需额外存储前后指针（通常 8~16 字节）。

核心优势

• 任意位置插入/删除：O(1) 时间复杂度。
• 迭代器稳定性：除非元素被删除，否则迭代器永不失效。

适用场景

• 需要频繁在中间插入/删除（如 LRU 缓存）。
• 元素较大且移动成本高。
• 需要长期有效的迭代器（如多步骤处理）。

---

std::deque：双端队列

结构特征

• 分块存储：由多个固定大小的块（chunk）组成，支持动态扩展。
• 内存局部性：优于 list，但弱于 vector。

核心优势

• 高效头尾操作：push_front/pop_front 和 push_back/pop_back 均为 O(1)。
• 随机访问：通过索引访问为 O(1)，但比 vector 稍慢。

适用场景

• 需要频繁在头尾增减数据（如任务队列）。
• 避免 vector 扩容时的拷贝开销。

---

三容器对比表

特性	vector	deque	list
随机访问	O(1)	O(1)	O(n)
头部插入/删除	O(n)	O(1)	O(1)
中间插入/删除	O(n)	O(n)	O(1)
迭代器稳定性	低	中等	高
内存连续性	连续	分段连续	不连续

---

决策逻辑

默认选择 vector

• 适合大多数场景：随机访问频繁、修改较少、内存连续性强。

换用 deque 的情况

• 需要高效的头尾操作（如滑动窗口算法）。
• 避免 vector 扩容时的性能抖动。

换用 list 的情况

• 频繁在中间插入/删除（如链表合并）。
• 元素较大或迭代器需长期有效。

---

性能实测建议

• 对小规模数据（<1KB），优先测试 vector。
• 对大规模数据或频繁修改场景，实测 list 和 deque 的缓存影响。

---

快速决策表

需求	推荐容器
高频随机访问	vector
高频头尾操作	deque
高频中间插入/删除	list
需要长期有效的迭代器	list
元素体积大且移动成本高	list

通过上述维度和场景分析，可快速选择最适合的容器。