引言

https://github.com/0voice

• STL（Standard Template Library）简介及其在C++中的重要性
• 容器类概述及其分类（序列容器、关联容器、无序关联容器等）
• 迭代器的介绍
• 本文重点讨论的三种容器：vector、deque、stack

---

迭代器

用于遍历容器中的元素，无需关系容器的底层实现细节。

1. 输入迭代器（Input Iterator）
   仅支持单向遍历（++）和读取元素（*），例如istream_iterator。
2. 输出迭代器（Output Iterator）
   仅支持单向遍历和写入元素，例如ostream_iterator。
3. 前向迭代器（Forward Iterator）
   支持多次读写和单向遍历，例如forward_list的迭代器。
4. 双向迭代器（Bidirectional Iterator）
   支持双向遍历（++和--），例如list的迭代器。
5. 随机访问迭代器（Random Access Iterator）
   支持随机访问（+n、-n、[]等），例如vector和deque的迭代器。

vector容器

基本特性

• 动态数组实现，支持随机访问
• 内存连续分配，自动扩容机制
• 时间复杂度分析：尾部操作O(1)，中间插入/删除O(n)

常用操作

• 初始化与赋值：push_back()、emplace_back()、assign()
• 元素访问：operator[]、at()、front()、back()
• 容量管理：reserve()、capacity()、shrink_to_fit()
• 迭代器支持：begin()、end()、反向迭代器

应用场景

• 需要频繁随机访问的场景
• 数据量动态变化但尾部操作居多的情况
• 性能优化技巧（预分配空间、避免中间插入）

---

deque容器

基本特性

• 双端队列实现，支持头尾高效操作
• 分段连续内存结构，非严格连续存储
• 时间复杂度分析：头尾操作O(1)，中间操作O(n)

常用操作

• 头尾操作：push_front()、pop_front()、push_back()、pop_back()
• 元素访问：operator[]、at()、front()、back()
• 容量管理：shrink_to_fit()（与vector差异）
• 迭代器支持：随机访问迭代器

与vector对比

• 内存结构差异（分段数组 vs 连续数组）
• 头插性能优势（deque O(1) vs vector O(n)）
• 适用场景：需要频繁头尾操作的队列结构

---

stack容器

基本特性

• 后进先出（LIFO）的适配器容器
• 默认基于deque实现，可指定底层容器（如vector、list）
• 不支持随机访问和迭代器

常用操作

• 栈操作：push()、pop()、top()
• 容量查询：empty()、size()
• 底层容器切换示例代码：

  stack<int, vector<int>> custom_stack;
  

应用场景

• 函数调用栈模拟
• 表达式求值、括号匹配等算法
• 与queue的对比（LIFO vs FIFO）

---

性能对比与选型建议

• 随机访问性能：vector ≈ deque > stack
• 头尾操作性能：deque > vector（头部）
• 内存效率：vector（连续） > deque（分段）
• 选型决策树：
  • 需要随机访问且尾部操作为主 → vector
  • 频繁头尾操作 → deque
  • 严格LIFO逻辑且无需遍历 → stack

---

进阶话题

• 容器适配器的设计思想（stack/queue基于其他容器）
• C++11/17新特性：emplace操作、非成员函数size()等
• 线程安全考虑（需外部同步）

---

总结

• 三种容器的核心差异总结
• 典型误用场景与避免方法
• 推荐学习资源（cppreference、Effective STL等）
• 推荐c++stl学习网站cplusplus.com/reference/vector/vector/