C++ STL 常用容器与数据结构实战指南
Vector：动态数组与倍增思想
在使用 vector 时，理解其内存分配机制很重要。系统分配空间的时间主要取决于申请次数而非单次大小。因此，变长数组应尽量减小申请次数。当空间不足时，vector 通常采用倍增策略（如长度 * 2）重新分配，这比频繁申请小块内存效率高得多。此外，vector 支持字典序比较运算。
常用函数与操作
- size()：返回元素个数
- empty()：判断是否为空
- clear()：清空容器
- front()/back()：访问首尾元素
- push_back()/pop_back()：尾部插入与弹出
- begin()/end()：迭代器范围
- []：下标访问
遍历方式
支持标准迭代器遍历，也可通过索引直接访问。由于支持比较运算，vector 整体可按字典序进行排序比较。
Pair：二元组结构
pair 可视为包含两个变量的结构体，内部已定义比较逻辑。排序时以 first 为第一关键字，second 为第二关键字（字典序）。适用于需要同时存储两种属性并按其中一种排序的场景。若需更多属性，可使用嵌套 pair，例如 pair<int, int> p;。
构造与取值
- 定义：
pair<int, int> p; - 取值：p.first, p.second
String：字符串封装
C++ 对字符串进行了封装，提供了丰富的操作接口。
常用函数
- size()/length()：返回字符串长度
- empty()：判断是否为空
- clear()：清空内容
- substr(起始下标，子串长度)：截取子串
- c_str()：获取 C 风格字符串地址
线性容器：Queue, Priority Queue, Stack, Deque
Queue 队列
遵循先进先出原则。
- size(), empty()
- push()：队尾插入
- pop()：队头弹出
- front(), back()：访问首尾
Priority Queue 优先队列
底层基于堆实现，默认是大根堆。
- top()：获取堆顶元素
- pop()：弹出堆顶
- 小根堆构造：
priority_queue<int, vector<int>, greater<int>> q; - 技巧：push 负值或利用 greater 模板参数
Stack 栈
遵循后进先出原则。
- push(), pop(), top()
- size(), empty()
Deque 双端队列
功能类似加强版 vector，支持两端插入删除。
- push_front()/pop_front()
- push_back()/pop_back()
- 注意：虽然功能强大，但在某些极端性能要求下可能不如 vector 高效。
关联容器：Set, Map, Unordered Set, Map
Set, Multiset, Map, Multimap
基于平衡二叉树（红黑树）实现，动态维护有序序列。
- 时间复杂度：O(log n)
