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——可变字符串