概述
C++ STL（标准模板库）由容器、算法、迭代器三部分组成。掌握它的正确姿势不是背 API，而是理解每个容器的时间复杂度与适用场景，以及算法与容器的搭配。
一、序列容器
vector（动态数组）
vector<int> v = {1, 2, 3};
v.push_back(4); // 末尾 O(1) 摊还
v.pop_back();
v[0]; // 随机访问 O(1)，不检查边界
v.at(0); // 带边界检查，越界抛异常
v.insert(v.begin()+1, 5); // 中间插入 O(n)
v.erase(v.begin()+1); // 中间删除 O(n)
deque（双端队列）
头尾插入删除都是 O(1)，随机访问 O(1)。适合”两头操作”的队列场景。
list（双向链表）
任意位置插入删除 O(1)（已知迭代器），但没有随机访问、缓存不友好。大部分”想用链表”的场景，用 vector 或 deque 性能更好。
二、关联容器
set / map（有序，红黑树）
map<string, int> m = {{"Alice", 25}, {"Bob", 30}};
m["Charlie"] = 28; // 插入或修改
m.count("Alice"); // 0 或 1
for (auto& [k, v] : m) // 按 key 有序遍历
unordered_set / unordered_map（哈希表）
unordered_map<string, int> um = {{"Alice", 25}};
// 接口与 map 类似，但无序；平均 O(1)，最坏 O(n)
选型：需要有序遍历或范围查询用 map/set；纯查找用 unordered 系列（平均更快）。
三、容器适配器
stack<int> st; st.push(1); st.top(); st.pop(); // 栈
queue<int> q; q.push(1); q.front(); q.pop(); // 队列
priority_queue<int> pq; // 默认大顶堆
pq.push(3); pq.top(); // 访问最大元素
// 小顶堆
priority_queue<int, vector<int>, greater<int>> min_pq;
四、常用算法
#include <algorithm>
sort(v.begin(), v.end()); // 排序 O(n log n)
binary_search(v.begin(), v.end(), 3); // 二分（需已排序）
auto it = lower_bound(v.begin(), v.end(), 2); // 第一个 ≥ 2
auto it = upper_bound(v.begin(), v.end(), 2); // 第一个 > 2
find(v.begin(), v.end(), 3); // 线性查找
count_if(v.begin(), v.end(), [](int x){ return x%2==0; });
reverse(v.begin(), v.end());
fill(v.begin(), v.end(), 0);
// 去重（先排序）
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // erase-remove 惯用法
// 数值算法
accumulate(v.begin(), v.end(), 0); // 求和
partial_sum(v.begin(), v.end(), out.begin()); // 前缀和
// 变换
transform(v.begin(), v.end(), out.begin(), [](int x){ return x*x; });
iota(nums.begin(), nums.end(), 10); // 生成递增序列
五、迭代器与 Lambda
for (auto it = v.begin(); it != v.end(); ++it) { } // 正向
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) { } // 反向
sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // Lambda 作比较器
六、实用技巧
// emplace 代替 push/insert：原地构造，避免临时对象拷贝
vector<pair<int, string>> v;
v.emplace_back(1, "one");
// 移动而非拷贝
vector<string> vs;
string s = "data";
vs.push_back(std::move(s));
// 智能指针（C++11/14）
auto ptr = std::make_shared<int>(42);
auto uptr = std::make_unique<vector<int>>(10, 1);
实战体会
reserve 预分配是性价比最高的优化。连续 push_back 几万次而没提前 reserve，vector 会反复扩容、搬移、释放，实测能慢好几倍。凡是能预估规模的容器，先 reserve 再填数据。
vector 头部的操作别硬扛。在 vector 头部反复 erase 是 O(n) 且每次搬移所有元素；我写服务器内存队列时因此卡顿过，后来换 deque 或用 erase-remove 惯用法一次性清理，问题立刻消失。
map 和 unordered_map 的选择要看访问模式。需要有序遍历用 map；纯查找用 unordered_map。我踩过的坑：哈希表在特定输入下退化（哈希冲突加剧），定位了很久才发现是输入数据恰好命中了同一个桶。
range-based for 里按值迭代会悄悄拷贝整个元素。遍历大对象容器时忘了写 &，每个元素被拷贝一遍，内存和耗时都翻倍。代码规范里默认写 const auto&，只有明确要修改才去掉 const。
