C++ 标准库

原理

STL 六大组件

容器：存储数据（vector, map, unordered_set 等）
算法：操作容器中数据（sort, find, transform 等）
迭代器：连接容器和算法的桥梁，提供统一访问接口
函数对象：重载了 operator() 的类
适配器：修改容器/迭代器/函数对象的接口
分配器：控制内存分配策略

各容器的底层数据结构

vector：连续数组。三层指针（start, finish, end_of_storage）。增长策略通常为 2 倍或 1.5 倍扩容——此时所有迭代器/指针/引用失效。随机访问 O(1)；末尾插入均摊 O(1)；中间插入 O(n)。

list：双向循环链表。每个节点是独立的堆分配块——sizeof(T) + 2×sizeof(void*) + malloc 元数据。任意位置插入/删除 O(1)；访问第 n 个元素 O(n)。

deque：分段连续数组。中控器（指针数组）指向多个固定大小块。头尾插入 O(1) 均摊；随机访问 O(1)（比 vector 多一次间接寻址）。

map/set：红黑树（自平衡二叉搜索树）。所有操作 O(log n)，迭代器稳定，支持有序遍历和范围查询。每个节点含：键 + 值（map）+ 左右孩子指针 + 父指针 + 颜色标记——空间开销较大。

unordered_map/unordered_set：哈希表，开链法。平均查找/插入/删除 O(1)；最坏 O(n)（全碰撞）；负载因子超过阈值时 rehash O(n)。

string：类似 vector<char>，但现代实现包含 SSO（短字符串优化）——15 字符以下的字符串存储在对象内部（栈上），无堆分配。GCC libstdc++ 64-bit 上 sizeof(string) = 32 字节。

迭代器类别（能力递增）

输入迭代器：单向读取（istream_iterator）
输出迭代器：单向写入（ostream_iterator）
前向迭代器：单向读写（forward_list）
双向迭代器：双向读写（list, map）
随机访问迭代器：随机位置 + 双向（vector, deque, array）

每种算法的复杂度要求对应最低的迭代器类别——比如 sort 需要随机访问迭代器，不能用于 list（list 有自己的 sort 方法）。

迭代器失效规则

容器	插入失效	删除失效
vector	capacity 变化时全部失效；否则只失效插入位置及之后	删除位置及之后全部失效
deque	中间插入全部失效；两端插入可能使所有迭代器失效	两端删除仅失效删除端；中间删除全部失效
list	不失效	仅失效被删除节点
map/set	不失效	仅失效被删除节点
unordered_map/set	rehash 时全部失效	仅失效被删除节点

Erase-Remove Idiom 是删除元素的安全模式：

v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());

语法

序列容器

std::vector<int> v = {1,2,3};
v.push_back(4); v.emplace_back(5);       // 插入
v.pop_back(); v.erase(v.begin());         // 删除
v.reserve(100); v.shrink_to_fit();        // 容量管理
 
std::deque<int> dq;
dq.push_front(0); dq.pop_front();         // 高效双端操作
 
std::list<int> lst = {1,2,3};
lst.splice(lst.begin(), other);           // O(1) 拼接
lst.sort(); lst.unique();                 // list 专用操作
 
std::array<int, 5> arr = {1,2,3,4,5};    // 固定大小，不退化指针

关联容器

std::set<int> s = {3,1,2};               // 自动排序
s.insert(4); s.erase(2);
auto it = s.find(3);                      // 查找 O(log n)
auto lb = s.lower_bound(2);              // 范围查询
 
std::map<std::string, int> m;
m["key"] = 42; m.at("key");              // 访问
m.insert({"k2", 99}); m.emplace("k3", 77);
if (auto it = m.find("key"); it != m.end()) { /* ... */ }

无序容器

std::unordered_map<std::string, int> um;
// 平均 O(1) 查找，需自定义 hash 函数
um.rehash(100); um.reserve(1000);         // 预分配桶

算法（, ）

std::sort(v.begin(), v.end());            // O(n log n)
std::find(v.begin(), v.end(), 7);        // 线性查找
std::copy(src.begin(), src.end(), dst.begin());
std::transform(v.begin(), v.end(), v.begin(), [](int x){ return x*x; });
std::count_if(v.begin(), v.end(), pred);
auto it = std::remove_if(v.begin(), v.end(), pred); // 配合 erase 使用
std::lower_bound(v.begin(), v.end(), x); // 二分（需已排序）
int sum = std::accumulate(v.begin(), v.end(), 0);
std::iota(v.begin(), v.end(), 1);        // 递增填充 1,2,3...

Lambda 表达式

// [capture](params) -> ret { body }
auto add = [](int a, int b) { return a + b; };
[=]  { /* 按值捕获所有 */ };
[&]  { /* 按引用捕获所有 */ };
[x, &y] { /* x 按值，y 按引用 */ };
[p = std::move(ptr)] { /* C++14 初始化捕获 */ };
[](auto a, auto b) { return a + b; };    // C++14 泛型 lambda

C++17 类型工具

std::optional<int> find(int id) { /* 或无值 */ }
std::variant<int, double, std::string> data;
std::any a = 42; a = "hello";
std::string_view sv = "Hello World";     // 非持有引用，不分配内存
std::visit(visitor, variant);             // variant 访问器
auto [a, b, c] = std::tuple(1, 2.0, "3"); // 结构化绑定

<chrono> 时间库

auto start = std::chrono::steady_clock::now();
auto elapsed = std::chrono::steady_clock::now() - start;
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(elapsed).count();
using namespace std::chrono_literals;
auto wait = 100ms + 5s;

实践

力扣题目：力扣去重排序（set 的去重排序），力扣排序（vector + sort + Lambda），力扣第k小（nth_element），力扣堆（priority_queue），力扣单调栈（stack 容器适配器），力扣并查集（unordered_map）。

AI 自检：1) 问 AI 为什么 list 不能用 std::sort，必须用自己的 sort 方法——从迭代器类别角度回答；2) 给 AI 一个 vector<int> 和一段在遍历中调用 erase(it) 的错误代码，要求指出问题并提供 Erase-Remove 的正确写法；3) 问 map 和 unordered_map 在什么场景下选择哪一个——要求从底层数据结构和复杂度角度回答。

建议先阅读：09_函数模板 — STL 全部是模板实现，理解模板是理解 STL 设计的前提；04_动态内存 — allocator 与内存管理的底层机制。

RootStack

探索

15_C++标准库