C++ STL 常用容器实战指南
STL（Standard Template Library）是 C++ 标准库的核心组成部分，提供了丰富的数据结构与算法。掌握这些容器不仅能提升开发效率，更是理解底层内存管理与性能优化的关键。
Vector：动态数组的倍增策略
vector 是最常用的序列容器，底层基于连续内存空间。它的核心优势在于支持随机访问，但扩容机制需要特别注意。
为什么会有倍增思想？
系统分配内存的时间主要取决于申请次数而非总大小。如果频繁申请小块内存，开销巨大。因此 vector 在容量不足时通常采用倍增策略（例如容量翻倍），这样均摊下来插入操作的复杂度接近 O(1)。
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
// 预分配空间可以减少扩容次数
v.reserve(1000);
for (int i = 0; i < 1000; ++i) {
v.push_back(i);
}
return 0;
}
常用操作：
size()/empty()：获取元素个数或判断是否为空。push_back()/pop_back()：尾部增删。front()/back()：访问首尾元素。begin()/end()：迭代器遍历。[]：支持下标访问，且 vector 整体支持字典序比较运算。
Pair：二元组结构体
pair 可以看作是一个包含两个变量的结构体，常用于存储关联数据（如坐标、键值对）。它内部定义了比较运算符，排序时默认以 first 为第一关键字，second 为第二关键字进行字典序比较。
#include <utility>
#include <algorithm>
std::pair<int, int> p = {1, 2};
// 嵌套 pair 处理多属性
std::pair<int, std::pair<int, int>> complex_p = {1, {2, 3}};
使用场景：
当某个对象具有两种不同属性，且需要按其中一种属性排序时，pair 非常高效。例如在图论中存储边权与节点索引。
String：字符串封装
C++ 将字符串进行了面向对象封装，比 C 风格字符数组更安全便捷。
#include <string>
std::string s = "hello";
s.substr(0, 3); // 获取子串 "hel"
const char* c_str_ptr = s.c_str(); // 获取 C 风格指针
序列容器：队列与栈
Queue & Stack
遵循先进先出（FIFO）和后进先出（LIFO）原则。
#include <queue>
#include <stack>
std::queue<int> q;
q.push(1); // 入队
int head = q.front(); // 取头
q.pop(); // 出队
std::stack<int> st;
st.push(1); // 入栈
int top = st.top(); // 取顶
st.pop(); // 出栈
Priority Queue：优先队列
底层基于堆实现，默认是大根堆。若需小根堆，可指定比较函数。
#include <queue>
#include <functional>
// 大根堆（默认）
std::priority_queue<int> pq_max;
// 小根堆
std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;
Deque：双端队列
功能类似加强版 vector，支持两端高效插入删除，但时间开销略高于 vector，视场景选用。
关联容器：有序与无序
Set & Map
基于平衡二叉树（红黑树）实现，维护有序序列。所有操作时间复杂度为 O(log n)。
insert()：插入元素。find()/count()：查找与计数。erase()：删除元素。lower_bound()/upper_bound()：二分查找边界。
注意：multiset/multimap 允许重复元素，而 set/map 不允许。
Unordered 系列
基于哈希表实现，增删改查平均复杂度为 O(1)。但失去了有序性，不支持 lower_bound 及迭代器的自增自减操作。
#include <unordered_map>
std::unordered_map<int, int> umap;
umap[1] = 10; // O(1)
Bitset：位运算优化
适用于状态压缩或大量布尔值存储。
#include <bitset>
std::bitset<10000> bs;
bs.set(k, v); // 第 k 位设为 v
bs.flip(); // 全部取反
bs.count(); // 统计 1 的个数
总结
选择容器时需权衡时间与空间。追求有序查询用 map/set，追求极致速度用 unordered，频繁尾部操作首选 vector。理解底层原理，才能在工程实践中做出最优决策。
