今日学习：STL 容器与算法

STL（Standard Template Library）是 C++ 标准库的精华：约 20 个容器、60 多个算法、5 类迭代器，共同构成一套"数据结构 + 算法"的完整体系。它是前四天所学一切（模板、RAII、移动语义、lambda）的集大成者——std::vector 是模板 + RAII + 移动语义的完美结晶，std::sort 是模板 + 迭代器的经典应用。

今天学习 STL 容器与算法，是因为：第一，它是 Qt 开发者的日常——Qt6 的 QList、QHash 与 STL 容器同源同构，理解 STL 等于理解 Qt 容器的一半；第二，它是性能优化的第一战场——Chrome、微信、QQ 这些大型客户端的性能问题，十有八九能追溯到"选错了容器"；第三，它是最容易暴露 Web 思维惯性盲区的地方——JavaScript 的数组和对象让你养成了"数据结构随便用"的习惯，而 C++ 中一个错误选择就是 100 倍的性能差距。

一句话说清 STL：一套"用模板写成的、以迭代器为粘合剂"的通用数据结构与算法库。容器管"存储"，算法管"处理"，迭代器管"遍历"——三者解耦，却因为统一的设计而能自由组合。这是软件工程"高内聚、低耦合"的教科书级范例。

1. 容器家族：先分类，再选择

STL 容器按底层数据结构分为三大类：

• 序列容器（sequence containers）——元素按插入顺序排列：vector（动态数组）、deque（双端队列）、list（双向链表）、forward_list（单向链表）、array（定长数组）、basic_string（字符串本质也是容器）。
• 有序关联容器（ordered associative containers）——基于红黑树，按键自动排序：set、map、multiset、multimap。查找、插入、删除均为 O(log n)。
• 无序关联容器（unordered associative containers）——基于哈希表：unordered_set、unordered_map。平均 O(1) 查找，最坏 O(n)。

关键认知：STL 容器存储的是"值"（value semantics），不是引用。往 std::vector<MyClass> 里 push 一个对象，容器里存的是它的拷贝（或移动后的新对象），而不是指向原对象的指针。这和 JavaScript 的"一切皆引用"有本质区别——稍后在 Web 对比部分展开。

2. vector 为什么是"默认容器"

std::vector 的底层是一块连续内存上的动态数组。它有三个关键机制：

• 容量增长（capacity growth）：当元素数超过 capacity 时，vector 会分配一块更大的内存（通常翻倍），把旧元素移动过去，再释放旧内存。这就是为什么 push_back 均摊（amortized）复杂度是 O(1)。
• 缓存友好（cache-friendly）：元素在内存中紧挨着，遍历时 CPU 缓存命中率极高。现代 CPU 上，顺序遍历 vector 比遍历 list 快几十倍——即使两者的时间复杂度相同。
• 随机访问 O(1)：vec[i] 就是一次指针算术：*(data + i)。

// vector 的基本用法：RAII + 移动语义的完美协作
std::vector<std::string> names;
names.reserve(1000);            // 预分配，避免反复扩容移动
names.emplace_back("Alice");      // emplace_back：原地构造，省一次移动
names.push_back("Bob");

// 范围 for：底层就是迭代器（第3天学过 auto 与范围语义）
for (const auto& name : names) {
    std::cout << name << '\n';
}

// 访问元素：operator[] 不做边界检查（快）；at() 抛异常（安全）
const auto& first = names[0];   // O(1) 随机访问

3. 迭代器：算法与容器之间的"万能插头"

迭代器是 STL 设计中最精妙的一环。它把"怎么遍历"抽象成统一接口，让 std::sort 既能排序 vector 又能排序 deque（甚至原生的 C 数组）：

// 同一个算法，作用在不同容器上
std::vector<int> v = {3, 1, 4, 1, 5};
int c_array[] = {9, 2, 7};

std::sort(v.begin(), v.end());            // 排序 vector
std::sort(std::begin(c_array), std::end(c_array));  // 排序 C 数组！

迭代器按能力分为五类（由弱到强）：input / output → forward → bidirectional → random-access。能力越强，能用的算法越多。例如 std::sort 要求随机访问迭代器——所以它不能排序 std::list（list 只有双向迭代器），list 只能用自己的 list::sort() 成员函数。这个限制不是缺陷，而是设计：算法对迭代器能力的要求，暴露了数据结构的真实能力。

4. 算法库：能交给标准库的，别自己写

<algorithm> 提供了 60+ 个算法，按用途分类：

• 查找：find、find_if、binary_search（要求有序）、lower_bound / upper_bound
• 排序与重排：sort（快排，不稳定）、stable_sort（归并，稳定）、partial_sort、nth_element、reverse、rotate
• 修改：copy、transform、fill、replace、remove、unique
• 数值：accumulate、inner_product、iota
• C++20 ranges：std::ranges::sort、views::filter、views::transform——管道语法，像极了 JavaScript 的链式调用

最重要的惯用法是 erase-remove 惯用法（remove-erase idiom）——std::remove 并不真正删除元素，它只是把"要保留的元素"往前搬，返回新的逻辑末尾，真正的删除要靠 erase：

// ❌ 新手直觉：remove 就完事了
// std::remove(v.begin(), v.end(), 3);  // 元素还在！只是被搬到后面

// ✅ erase-remove 惯用法：真正删除
v.erase(std::remove(v.begin(), v.end(), 3), v.end());

// ✅ C++20 的 erase 自由函数：一行搞定（推荐）
std::erase(v, 3);   // C++20 新增，容器 + 值
std::erase_if(v, [](auto x) { return x % 2 == 0; });

为什么 remove 不直接删除？因为算法不知道容器如何释放内存——算法只操作迭代器，不拥有容器。这再次体现了"算法与容器解耦"的设计哲学：remove 可以作用于数组、vector、list 的任何一段区间，代价就是它只能"搬运"不能"删除"。

5. map vs unordered_map：红黑树与哈希表之争

经验法则：默认用 unordered_map，需要"按键有序遍历"或"范围查询"时才用 map。但要注意：数据量小时（几百个元素），map 的红黑树可能反而更快——因为哈希函数计算也有开销，且小数据集下缓存优势不明显。

案例1：Qt6 的容器体系——STL 的近亲

Qt6 的容器（QList、QVector、QMap、QHash、QSet、QStringList）与 STL 容器设计同源：QMap 对应 std::map（红黑树），QHash 对应 std::unordered_map（哈希表）。但 Qt 容器有一个 STL 没有的杀手锏——隐式共享（implicit sharing）/ 写时复制（copy-on-write）：

// Qt 容器：拷贝是 O(1) 的！真正复制发生在"写"的时候
QList<int> a = {1, 2, 3};
QList<int> b = a;        // 只拷贝一个指针 + 引用计数，O(1)
b.append(4);            // 此时才深拷贝（detach）

这解释了为什么 Qt 老代码到处"按值传 QList"而不心疼——Qt6 中 QList 与 QVector 已合并（QList 即 QVector 的别名），都基于连续存储的 QArrayData。而 std::vector 拷贝就是实打实的深拷贝。理解这一点，你才能读懂为什么 Qt 的信号槽参数建议"按 const 引用传对象、按值传小对象"，以及为什么跨线程用 Qt::QueuedConnection 时容器要拷贝。

案例2：Chromium 的容器选择哲学

Chromium 的代码规范（C++ Style Guide）明确要求：能用 std::vector 就不用链表；能用 flat_map 就不用 std::map。Chromium 的 base::flat_map 是一个"排序 vector + 二分查找"的结构：查找 O(log n)，但内存完全连续、缓存友好，在元素量 < 1000 时实测比 std::map 快 2~5 倍。为什么不直接用 std::map？因为浏览器每帧都要遍历 DOM 属性、样式映射等大量小映射表——缓存命中的收益远超红黑树的渐进复杂度优势。

同样的思想也体现在 V8 引擎中：JavaScript 对象属性存储用了"隐藏类 + 描述数组"的布局优化，本质上就是把"哈希表"改造成"类数组的连续结构"——与 flat_map 异曲同工。行业共识：在数据量小的场景，连续内存 + 线性/二分查找往往胜过"理论上更优"的复杂结构。

案例3：微信/QQ 聊天列表的增量更新

桌面 IM（如微信 PC 版、QQ）的会话列表是一个经典场景：需要按时间排序、频繁插入新消息、按会话 ID 快速定位。如果天真地用 std::vector 存会话对象、每次新消息来了 sort 一下，就是 O(n log n) × 消息数——会话一多就卡。工程上的典型方案：用 std::unordered_map<QString, SessionItem> 存会话（O(1) 定位），同时维护一个"按时间排序的 id 数组"，插入新消息时只需局部调整（二分查找插入点 + 局部移动），把 O(n log n) 降为 O(n)。这就是"两个容器协同"解决单一容器性能瓶颈的经典套路——也解释了为什么大型客户端里"索引 + 数据分离"是标配（数据库、搜索引擎都是这个思想）。

❌ 错误1：迭代器/引用失效后继续使用

// ❌ 扩容后引用失效 —— UB！
std::vector<int> v = {1, 2, 3};
auto& ref = v[0];            // 引用指向元素 0
v.push_back(4);               // 扩容！内存被重新分配
std::cout << ref;              // ⚠ ref 已悬空 —— 读野内存

为什么：vector 扩容 = 换一块更大的内存，旧地址失效。JS 里数组扩容是"悄悄换内部 buffer"，但因为元素是引用所以外部引用不受影响；C++ 存的是值本身，引用就是地址，地址变了引用就废了。避免：先 reserve() 预分配；或在结构性操作之后重新获取迭代器/引用。

❌ 错误2：循环中边遍历边删除

// ❌ 删除元素后迭代器失效，++it 是 UB
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) v.erase(it);   // ⚠ erase 后 it 失效
}

// ✅ 正确：erase 返回下一个有效迭代器
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);
    else ++it;
}

// ✅ 更现代：erase_if（C++20）或 remove-erase 惯用法
std::erase_if(v, [](auto x) { return x % 2 == 0; });

❌ 错误3：把 list 当"万能容器"（来自 JS 的思维惯性）

JS 里 splice 插删自如，于是新手在 C++ 里也倾向用 std::list 存一切。但 std::list 的每个元素是一个独立分配的节点——遍历时每次都要跳指针，缓存全部打空，实际性能可能比 vector 慢 10~50 倍。绝大多数场景，vector 才是正确答案：push_back 均摊 O(1)、缓存友好、随机访问。只有"需要频繁在中间插入/删除 + 大量元素 + 不需要随机访问"时，list 才值得考虑（而且通常 deque 或分段结构更优）。

❌ 错误4：循环里用 operator[] 反复查 map

// ❌ 一次循环两次哈希查找（operator[] 找不到还会插入默认值！）
for (const auto& item : items) {
    count_map[item.key] = count_map[item.key] + 1;  // 查找 + 可能插入 + 再查找
}

// ✅ 一次查找
for (const auto& item : items) {
    auto [it, inserted] = count_map.try_emplace(item.key, 1);
    if (!inserted) ++it->second;   // C++17 try_emplace
}

另一个隐蔽坑：map[key] 在键不存在时会插入一个默认构造的值——如果你只是想"查一下在不在"，这会在 map 里留下垃圾键。查找请用 find() 或 contains()（C++20）。

❌ 错误5：字符串拼接用 + 造出 O(n²)

str = str + "a" 每次都要重新分配并拷贝整个字符串。循环 10 万次就是灾难。避免：用 std::string::reserve 预分配 + append/+=，或 std::ostringstream。这和 JS 里"数组 join 优于字符串 += "是同一个教训，只是 C++ 里差距更夸张（因为 string 的 COW 已被标准禁止，拷贝是实打实的）。

容器选择决策树

现代 C++ 容器使用准则

• reserve 先行：知道大概规模就先 reserve()，消灭反复扩容（一次扩容 = 一次分配 + 全员移动）。
• emplace_back 优先于 push_back：原地构造参数，省掉一次临时对象构造 + 移动。
• 能存值不存指针：容器存值，内存连续、缓存友好、无所有权问题。vector<unique_ptr<T>> 只在该类型不可拷贝/移动代价高时用。
• 算法优先于手写循环：std::find_if 表达意图比 for + if 更清晰，且编译器优化更好。C++20 ranges 让代码更像声明式。
• const 正确性：只读遍历用 const auto&；要修改用 auto&；小对象（int、指针）按值 auto。
• 容器引用绝不长期持有：迭代器/引用是"短期租约"，跨函数保存迭代器 = 埋雷（参考第 4 天的"借用 vs 拥有"）。

性能验证优于直觉：所有容器选择都应建立在 std::chrono 微基准或 profiler 数据之上。C++ 社区共识：复杂度（Big-O）决定规模增长后的命运，缓存行为决定同一量级下的胜负——两者都要看。

JS 数组 vs std::vector：看起来像，其实完全不同

JavaScript 的 Array 和 std::vector 表面上都是"动态数组"，但语义天差地别：

• JS 数组是"对象"：元素是引用（指针），可以混装任意类型，arr[0] = 1; arr[1] = "x" 都合法。V8 底层为了优化，会尝试用连续的同构存储（PACKED_SMI_ELEMENTS 等），但一旦混入不同类型就会"降级"为慢速的字典模式。
• C++ vector 是"值数组"：所有元素同类型、连续存储，sizeof(vector) 是固定的（3 个指针），元素就在内存里紧挨着。

对 Web 开发者的迁移提示：你在 JS 里用 arr.push(obj) 存的其实是"指向 obj 的引用"，后续 obj.xxx = 1 数组里的"对象"也跟着变；在 C++ 里 v.push_back(obj) 存的是拷贝，改原对象不影响容器里的副本——除非你 push 的是指针/引用。这是最容易踩的语义坑。

算法思维的迁移：从"手写循环"到"声明式"

Vue/React 开发者熟悉 arr.filter(x => ...).map(x => ...).reduce(...) 的链式管道。C++20 的 ranges 几乎就是同一个东西：

// JS（你熟悉的世界）
// const result = arr.filter(x => x > 0).map(x => x * 2).sort((a,b) => a - b);

// C++20 Ranges（同一个世界，另一种语法）
namespace rv = std::ranges::views;
auto result = arr
    | rv::filter([](auto x) { return x > 0; })
    | rv::transform([](auto x) { return x * 2; })
    | rv::take(10);   // 惰性求值：像极了 RxJS 的管道

区别与联系：JS 的 filter/map 是立即求值——每步都生成一个全新数组（内存开销）；C++20 ranges 是惰性求值——管道只是"视图"，遍历时才真正计算，零中间分配。思想上完全同构（函数式管道），工程上 C++ 更抠内存。你已经会了思想，只需学语法。

类比映射表

最重要的迁移认知：在 Web 里你几乎不用关心"数据存在哪、怎么排布"——V8 替你优化。在 C++ 里，内存布局（memory layout）就是性能本身。学会在写代码前问自己一句："这些数据该怎么排布？谁拥有谁？"——这是从"会写 JS"到"会设计系统"的分水岭。

作为 Team Leader，容器与算法规范是团队代码质量和性能的第一道防线——因为容器选型错误会在代码评审时一眼看穿，却会在线上放大百倍。

🔍 如何 Code Review

• 看容器选型：看到 std::list 就追问"为什么不用 vector/deque？"；看到 std::map 而代码只做按键查找，提示换成 unordered_map；看到 vector<shared_ptr<T>> 而 T 不是多态基类，直接打回（应存值）。
• 看循环里的容器操作：循环体内出现 map[key] 双查找、vector.erase(it) 且未使用返回值、字符串 += 拼接——都是需要指出的问题。
• 看迭代器生命周期：函数返回迭代器/引用、成员变量存迭代器——高危信号，要求改为"索引 + 校验"或存值。
• 要求性能证据：当有人声称"这里必须用 list/map 因为插入频繁"，要求给出 profiler 数据。经验法则："性能敏感"的说法必须有基准支撑，否则按默认规范（vector + unordered_map）执行。

📋 制定规范

• 容器默认表：把"决策树"写进团队 Wiki：默认 vector；按键查找用 unordered_map；需要有序遍历用 map；Qt 层用 QList/QHash 并说明理由。
• 禁止裸 new 数组：一律 std::vector / std::array，与第 1 天 RAII 规范呼应。
• 热路径规则：性能敏感路径禁用手写循环替代算法；要求 reserve 预分配；要求 const 引用传参避免拷贝。
• 代码评审清单化：把上述条目做成 Review Checklist（像 ESLint 规则一样逐条勾），新人也能高效评审，同时沉淀团队共识。

👥 如何培养新人

• 安排一次"容器性能工作坊"：让新人用 std::chrono 分别测 vector/list/map/unordered_map 在 10 万次操作下的耗时，亲眼看到 100 倍差距——体验比说教深刻十倍。
• 带新人读 Qt 源码里的容器用法（如 QListView 的 model 缓存），理解"真实项目如何选型"。
• 约定"选型三问"：① 数据量多大？② 增删查哪个最频繁？③ 需要有序遍历吗？——三问之后，容器自然选对。
• 把第 6 节的类比映射表发给 Web 转岗的新人，他们看懂 JS ↔ C++ 的对应关系后，学习曲线会平缓很多。

• 《Effective STL》— Scott Meyers — 50 条 STL 实战准则，条条都是血泪教训（"容器 vs 算法 vs 迭代器"的 50 个坑）。推荐理由：STL 领域无可替代的进阶读物，与《Effective Modern C++》配套。
• 《C++ Primer》第 5 版 第 9~11 章 — 顺序容器、泛型算法、关联容器三章连读。推荐理由：Web 转 C++ 最平滑的入门路径，第 10 章算法部分配图极佳。
• cppreference.com：Containers / Algorithms — en.cppreference.com/w/cpp/container 与 en.cppreference.com/w/cpp/algorithm。每个容器的复杂度表、迭代器失效规则一应俱全——查失效规则请永远以这里为准。
• C++ Core Guidelines：SL.con / SL.str — isocpp.github.io/CppCoreGuidelines 的容器与字符串章节。推荐理由：Bjarne 亲自定的容器使用规范，团队规范可直接引用。
• Abseil C++ Guide：Containers — abseil.io/docs/cpp/guides/container。Google 对容器选型的权威论述（flat_hash_map 思路），Chromium flat_map 思想的同门文献。推荐理由：工业级容器选型决策树。
• Qt 官方文档：Container Classes — doc.qt.io/qt-6/containers.html。Qt6 容器与 STL 的对照表、隐式共享详解。推荐理由：直接对接你的 Qt 学习主线。