STL 容器与算法

这一课你将能做到

1. 用 vector / string / map / unordered_map 完成增删查改，并按「有序性 vs 速度」正确选型
2. 用 <algorithm> 里的 sort / find_if / count_if / accumulate 干掉手写循环
3. 说出 C++ 容器与 Java 集合类的对应关系，以及 at 与 []、迭代器失效这两个易错点

为什么要学

Java 的生产力一半在集合框架，C++ 同理在 STL（Standard Template Library）。判题沙箱的每个模块都在用 STL：测试点列表是 vector，用户耗时到题目 ID 的排行榜是 map，输出比对缓冲是 string，筛出超时提交靠 std::find_if。STL 不仅是「能用的轮子」，还是模板编程的活教材——你天天调用的 std::vector<int>，本身就是下一课要学的类模板。

选型口诀先记住：默认 vector；要按键查用 map（有序）/ unordered_map（快）；中间插入多才考虑 list（极少用）。这和 Java 里「默认 ArrayList、要排序字典用 TreeMap、只求快用 HashMap」完全同构。

先建立图像

C++ 容器 ↔ Java 集合 对照表：

std::vector<T>      ↔ ArrayList<T>     动态数组，随机访问 O(1)
std::string         ↔ String/StringBuilder  可变字符串（Java 的 String 不可变）
std::map<K,V>       ↔ TreeMap<K,V>     红黑树，按 key 有序，操作 O(log n)
std::unordered_map  ↔ HashMap<K,V>     哈希表，平均 O(1)
std::set            ↔ TreeSet          有序去重集合
std::deque          ↔ ArrayDeque       双端队列
std::stack/queue    ↔ Stack/LinkedList 用法近似

最大思维差异：Java 集合只装对象（基本类型走装箱）；
C++ 容器直接装值——std::vector<int> 就是连续的 int 内存块，零装箱开销。

跟着做

步骤 1：vector——默认容器

新建 stl.cpp：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores;              // 空容器
    scores.push_back(60);                 // 尾部追加
    scores.push_back(87);
    scores.emplace_back(95);              // 原地构造，少一次移动，C++ 首选

    std::cout << "大小 " << scores.size()
              << " 容量 " << scores.capacity() << "\n";

    // 下标访问：快但不检查边界；at()：越界抛 std::out_of_range
    std::cout << scores[1] << " / " << scores.at(2) << "\n";

    // 遍历（现代写法：范围 for，第 8 课细讲，先记形式）
    for (int s : scores) std::cout << s << " ";
    std::cout << "\n";

    scores.pop_back();                    // 删尾元素
    scores.clear();                       // 清空（size 归 0，capacity 不缩）
    return 0;
}

vector 的核心性能特征：内存连续 → 缓存友好、随机访问 O(1)；尾部增删 O(1)，中间插入删除 O(n)（要搬移元素）。这和 ArrayList 一致。

步骤 2：string——可变字符串

#include <iostream>
#include <string>

int main() {
    std::string line = "1001,AC,128";     // 一条提交记录：ID,结果,耗时
    line += ",cpp";                       // 追加（对应 StringBuilder.append）
    std::cout << line << "\n";

    // 手动按逗号切分——判题日志解析的最小实现
    size_t pos = 0;
    while ((pos = line.find(',')) != std::string::npos) {
        std::cout << line.substr(0, pos) << "\n";
        line.erase(0, pos + 1);
    }
    std::cout << line << "\n";            // 最后一段
    return 0;
}

注意 std::string 是可变的值类型（s += x 修改自身），Java 的 String 不可变、拼接靠 StringBuilder——语义对齐就好。find 找不到返回 std::string::npos（全 1 的特殊值，不是 -1，比较时别写 >= 0）。

步骤 3：map / unordered_map——按键查询

#include <iostream>
#include <map>
#include <string>

int main() {
    // 统计每个用户提交次数
    std::map<std::string, int> submits;
    submits["zhang"]++;                   // [] 不存在时自动插入 0，再 ++，非常好用
    submits["li"]++;
    submits["zhang"]++;
    submits["wang"]++;

    // map 按 key 字典序有序遍历（底层红黑树）
    for (const auto& kv : submits) {
        std::cout << kv.first << ": " << kv.second << "\n";
    }

    // 查找：[] 会「查无此人反而创建」，只查不改要用 find
    if (submits.find("zhao") == submits.end()) {
        std::cout << "zhao 没有提交\n";
    }
    std::cout << "at 查询: " << submits.at("li") << "\n";   // 不存在则抛异常
    return 0;
}

输出（注意按键有序）：

li: 1
wang: 1
zhang: 2
zhao 没有提交
at 查询: 1

把 std::map 换成 std::unordered_map（头文件 <unordered_map>），遍历顺序变乱、单次操作更快。选型：需要按序输出/范围查询 → map；纯点查 → unordered_map。

步骤 4：algorithm——算法与容器分离

STL 的精髓：算法不直接操作容器，而是操作迭代器（容器的「泛化指针」，Java 的 Iterator 只能 next，C++ 迭代器还能 +n、比较）：

#include <algorithm>
#include <iostream>
#include <numeric>      // accumulate
#include <string>
#include <vector>

struct Submission {
    std::string user;
    int cost;           // 耗时 ms
};

int main() {
    std::vector<Submission> subs = {
        {"zhang", 120}, {"li", 45}, {"wang", 200}, {"li", 88}
    };

    // 排序：按耗时升序。第三个参数是「比较函数」，lambda 现学现卖（第 8 课细讲）
    std::sort(subs.begin(), subs.end(),
              [](const Submission& a, const Submission& b) {
                  return a.cost < b.cost;
              });
    for (const auto& s : subs)
        std::cout << s.user << "-" << s.cost << "\n";

    // 查找第一个超时的提交（谓词 = 返回 bool 的判定函数）
    auto it = std::find_if(subs.begin(), subs.end(),
                           [](const Submission& s) { return s.cost > 100; });
    if (it != subs.end())
        std::cout << "首个超时: " << it->user << "\n";

    // 统计：li 提交了几次
    int n = std::count_if(subs.begin(), subs.end(),
                          [](const Submission& s) { return s.user == "li"; });
    std::cout << "li 提交 " << n << " 次\n";

    // 求和：平均耗时
    int total = std::accumulate(subs.begin(), subs.end(), 0,
                                [](int acc, const Submission& s) { return acc + s.cost; });
    std::cout << "平均 " << total / static_cast<int>(subs.size()) << "ms\n";
    return 0;
}

sort(begin, end, cmp) 三段式是 STL 的通用签名，lower_bound/max_element/remove_if 全长一个样——学会一个就学会一片。Java 的 list.sort(comparator)、stream().filter() 是同一思想的接口化表达。

讲清楚要点

1. 迭代器失效是头号雷区：vector 扩容、插入删除后，旧迭代器/指针全部作废（内存可能整体搬家）；map 插入不失效迭代器，但删除会使被删元素的迭代器失效。「遍历中删元素」的标准写法：it = v.erase(it);。
2. operator[] 与 at 的分工：[] 不检查越界（快，越界是 UB）；at 检查并抛异常（对应 Java 的 IndexOutOfBounds）。性能路径用 [] 且确信边界；不确定就用 at 或先 find。
3. map 的 [] 有副作用：查询不存在的 key 会插入默认值，既改了容器又可能塞进垃圾数据。只读查询用 find + 迭代器，或 C++20 的 contains（if (m.contains("li"))，最直观）。
4. 算法接收的是区间 [first, last)：左闭右开，end() 指向「最后一个元素的下一个」。这是 STL 一切接口的约定，左闭右开让「空区间」和「长度计算」都自然。
5. 性能习惯：能 reserve 先 reserve（vector/string 预留容量，判题输出缓冲就是这么攒的）；能 emplace_back 就不 push_back；容器存大对象时存 unique_ptr 或直接存值（vector 搬移值靠移动语义，通常无需指针）。

你可能会懵的地方

• std::vector<std::vector<int>> 算二维数组吗？ 算，且比 C 风格 int** 安全得多。注意 C++11 起两个 > 之间不用再写空格（> > 是 C++03 的历史包袱）。

• 为什么 map 用红黑树而不是哈希表？ 红黑树保证 O(log n) 最坏性能且天然有序，哈希表平均 O(1) 但最坏 O(n) 且无序。标准库把选择权给你：两个都要。Java 的 TreeMap/HashMap 分家同理。

• 容器里放引用可以吗？ 不行。STL 容器要求元素可赋值可移动，引用不满足。想放「别名」用指针（裸指针观察 + 外部持有对象）或 std::reference_wrapper，初学阶段直接存值或 unique_ptr 最省心。

• size() 返回的什么类型？ size_t（无符号 64 位）。所以 v.size() - 1 在空容器上是天文数字而不是 -1！循环判空先写 if (v.empty())，这是无符号陷阱的标准防雷动作。

• begin()/end() 和 Java 的 iterator() 有什么不同？ C++ 迭代器是「泛化指针」：支持 ++it、*it、随机访问容器还支持 it + 5；算法与容器解耦靠的正是这套统一接口。Java Iterator 只有 hasNext/next，功能弱得多，所以 Java 用集合自身方法补足。

错法对照

错法	问题	正解
遍历时 v.erase(it) 后 ++it	迭代器已失效，UB	it = v.erase(it);（erase 返回下一个有效迭代器）
m[k] 只想查询	不存在则插入默认值，污染数据	m.find(k) 判断，或 C++20 m.contains(k)
for (int i = 0; i <= v.size(); ++i)	越界 + 无符号回绕	i < v.size()，且先判 empty
对 unordered_map 依赖遍历顺序	顺序不定，每次可能不同	要顺序用 map，或先收集 key 再 sort
存字符串比较用 == 判 C 字符串	比较的是指针不是内容	std::string 用 == 没问题；char* 要 strcmp

卡点急救

1. 遍历中删除元素崩溃：改用「erase 返回值」写法 for (auto it = v.begin(); it != v.end(); ) { if (cond) it = v.erase(it); else ++it; }，或先 remove_if 再 erase（erase-remove 惯用法）。
2. map 查询「越查越多」：[] 的副作用。查询一律 find/at/contains。
3. 排序比较器写了 <=：违反「严格弱序」，STL 排序直接 UB（越界崩溃）。比较器必须满足「相等时返回 false」，一律写 <。

面试常问

• vector 的扩容机制？ 容量不足时按约 1.5~2 倍（实现相关）分配新内存，把旧元素移动/复制过去，释放旧内存——因此旧迭代器全部失效。均摊到每次 push_back 是 O(1)。预知规模先 reserve 一次到位。

• map 与 unordered_map 的底层实现与选型？ map 是红黑树：有序、最坏 O(log n)、迭代器稳定；unordered_map 是哈希表：平均 O(1)、无序、rehash 时迭代器失效。需要有序遍历/前驱后继选 map，纯点查、重吞吐选 unordered_map。

• vector 与 list 的区别，什么时候选 list？ vector 连续内存：随机访问 O(1)、尾部增删 O(1)、缓存友好；list 双向链表：任意位置增删 O(1)（拿到迭代器后）、无随机访问、每节点额外指针开销。绝大多数场景 vector 更快（缓存局部性碾压），list 只在「频繁中间插删且持有迭代器」时才值得考虑。

自测三问

1. std::vector 对应 Java 的哪个类？它中段插入的复杂度是多少？
2. 为什么查询 map 的 key 推荐用 find 而不是 []？
3. 什么操作会导致 vector 的迭代器失效？

小结一句话

STL = 容器装数据、算法算区间、迭代器牵线搭桥；默认 vector、按键查 map/unordered_map、能用算法不手写循环——这套组合拳的打法和 Java 集合框架同构，差异只在 C++ 更贴内存。

延伸

• cppreference：容器库
• cppreference：算法库
• 下一课：模板基础——STL 背后的「代码生成器」。