5
STL：C++ 的瑞士军刀
STL · Containers · Algorithms · Lambda
上一页我们用 C 手撸链表、栈、队列——在 C++ 里这些全部现成。STL = 容器（装数据）+ 算法（处理数据）+ 迭代器（连接两者）。你不用再自己造轮子，会用 vector 和 map，日常开发就够了一大半。
常用容器速查
| 容器 | 特点与适用 |
|---|---|
vector<T> | 动态数组，首选。尾部增删 O(1)，随机访问快。会自动扩容。 |
deque<T> | 双端队列，头尾都能高效增删。 |
list<T> | 双向链表，中间插入删除快，但不支持随机访问。 |
map<K,V> | 有序键值对（红黑树），key 不重复，查找 O(log n)。 |
set<T> | 有序集合，去重。 |
unordered_map | 哈希表实现，平均 O(1) 查找，用得极多。 |
stack / queue / priority_queue | 容器适配器：栈、队列、优先队列（堆）。 |
vector 和 unordered_map 的典型用法
#include <vector>
#include <unordered_map>
#include <iostream>
int main() {
std::vector<int> v = {3, 1, 4, 1, 5};
v.push_back(9); // 尾部追加
for (auto x : v) std::cout << x << " ";
// 键值对：姓名 -> 成绩
std::unordered_map<std::string, double> score;
score["小明"] = 92.5;
score["小红"] = 88.0;
std::cout << "小明成绩：" << score["小明"] << "\n";
}
常用算法（<algorithm>）+ Lambda
算法对容器做批量操作：排序、查找、去重、过滤。搭配 lambda（匿名函数），可以就地写"我想怎么处理"。lambda 语法是 [捕获](参数){ 函数体 }。
sort + lambda + count_if
#include <algorithm>
#include <vector>
std::vector<int> v = {5, 2, 9, 1, 7};
// 排序：默认升序
std::sort(v.begin(), v.end());
// 用 lambda 改成降序：[](int a,int b){ return a>b; }
std::sort(v.begin(), v.end(),
[](int a, int b) { return a > b; });
// 数一下大于 5 的有几个
int cnt = std::count_if(v.begin(), v.end(),
[](int x) { return x > 5; });
// lambda 的 [ ] 是"捕获"：[&] 按引用捕获外面变量，[=] 按值捕获副本
有序容器的二分查找：lower_bound / upper_bound
std::find 从头挨个找是 O(n)。如果数据已经排好序（vector 排过序，或 map/set 本身有序），就用二分查找家族，O(log n)：
| 算法 | 返回什么 |
|---|---|
lower_bound(beg,end,x) | 第一个 >= x 的位置（下界）。 |
upper_bound(beg,end,x) | 第一个 > x 的位置（上界）。 |
equal_range | 一次拿到 [lower, upper)，等于 x 的元素区间。 |
binary_search(beg,end,x) | 只判断"存不存在"，返回 bool。 |
lower_bound：找插入位置 / 统计有序数组里 >= x 的个数
std::vector<int> v = {1, 3, 3, 5, 8};
// 找第一个 >= 4 的位置：指向 5
auto it = std::lower_bound(v.begin(), v.end(), 4);
std::cout << *it; // 5
// set/map 也有同名成员函数，比通用版更快（内部树结构直接走）
std::set<int> s = {1,2,3,4};
auto p = s.lower_bound(3); // 指向 3，O(log n) 且不用先找 end
防坑：这些算法要求区间已经按相同规则排好序，传个乱序 vector 进去是未定义行为。对 std::unordered_map（哈希表）别用二分算法，它无序，用 .find()。