Lesson 0008 · STL 算法与关联容器

C++ 进阶 — 第 1 课

上节课（0007C 拷贝控制）：自己写析构、拷贝构造、赋值运算符，手动管一块堆内存。
这节课：手写冒泡排序、手写去重、手写查找 —— 这些标准库已经帮你写好了，一行代码搞定。学会用 STL，写代码量减半。
三句话速览
  1. sort 一行排序，比自己写的快得多。
  2. set 自动去重，还帮你排好序。
  3. map 是键值对，统计次数最好用。

1. sort — 排序，一行搞定

#include <algorithm>  // sort 在这里

vector<int> v = {5, 3, 8, 1, 2};
sort(v.begin(), v.end());     // 升序：1 2 3 5 8

sort(v.begin(), v.end(), greater<int>());  // 降序：8 5 3 2 1

复杂度 O(n log n)，比你手写的冒泡 O(n²) 快得多。

数组也能排序

int arr[] = {5, 3, 8, 1, 2};
sort(arr, arr + 5);          // arr 现在 = {1, 2, 3, 5, 8}

2. find — 查找元素

vector<int> v = {5, 3, 8, 1, 2};
auto it = find(v.begin(), v.end(), 8);

if (it != v.end())
    cout << "找到了，下标: " << (it - v.begin()) << endl;
else
    cout << "没找到" << endl;
iterator（迭代器）：find 返回的不是下标，是“指向元素的位置”。it - v.begin() 才换算成下标。auto 让编译器自动推断类型，不用手写 vector<int>::iterator。

3. set — 自动去重 + 排序

#include <set>

set<int> s;
s.insert(3); s.insert(1); s.insert(4); s.insert(1); s.insert(5);

for (int x : s) cout << x << " ";  // 1 3 4 5（自动去重+排序！）
操作代码说明
插入s.insert(x)重复的自动忽略
删除s.erase(x)不存在就什么也不做
查找s.count(x)存在返 1，不存在返 0

去重一行版

vector<int> v = {3, 1, 4, 1, 5, 4};
set<int> s(v.begin(), v.end());         // 丢进 set，自动去重排序
for (int x : s) cout << x << " ";     // 1 3 4 5

你之前写了 15 行嵌套循环的去重，现在两行搞定。

4. map — 键值对，查字典

#include <map>

map<string, int> score;          // 名字 → 分数
score["Alice"] = 95;
score["Bob"]   = 87;
score["Alice"] = 96;            // 更新

cout << score["Alice"];         // 96
cout << score["Charlie"];       // 0（不存在的 key 自动创建为 0）

// 安全查找
if (score.count("Bob")) cout << "Bob 存在";

遍历 map

for (auto& p : score) {
    cout << p.first << ": " << p.second << endl;
}
// Alice: 96
// Bob: 87

p.first 是 key，p.second 是 value。

5. pair — 捆绑两个值

pair<int, int> p = {3, 7};
cout << p.first;    // 3
cout << p.second;   // 7

常跟 vector 配合：vector<pair<int, int>> v; 存一堆坐标或边。

6. 速查总表

场景用啥头文件
排序sort(begin, end)<algorithm>
查找find(begin, end, val)<algorithm>
反转reverse(begin, end)<algorithm>
最值max(a, b) / min(a, b)<algorithm>
去重排序set<T><set>
键值映射map<K, V><map>
配对pair<A, B><utility>
交换swap(a, b)<utility>
一句话分工：vector、set、map 是容器（存东西的）；sort、find、reverse 是算法（处理东西的）。两者靠迭代器对接。

7. 坑点清单

8. 小测

Q1. set<int> s = {3, 1, 3, 2}; s 里有几个元素？
Q2. sort 和手写冒泡排序区别是什么？
Q3. map 中访问不存在的 key 会发生什么？

9. 动手练习

题目 1：用 sort 重写排序
读入 n 和 n 个数，用 sort 从小到大输出。
然后再试试从大到小。
题目 2：统计词频
读入 n 个单词（string），用 map 统计每个单词出现了几次，按字典序输出。
示例：apple banana apple cat banana apple → apple: 3 banana: 2 cat: 1
提示：map 自动按 key 字典序排列，直接遍历即可。
卡住时的自查顺序
  1. 头文件带了吗？<algorithm>、<set>、<map> 各管一摊。
  2. 报错说找不到 begin 或类型不对：先检查容器名写没写错、是不是空的。
  3. find 的结果没判 != v.end() 就解引用，是最常见的崩溃来源。
  4. 结果不对：先把容器的 size() 和内容打印一遍，确认数据到底进去没有。

本课小结

下一课预告
0009 结构体与面向对象入门 —— 现在一个人的名字、分数、身高分三个 vector 存着，排序时很容易对不上号。下一课把这些相关的数据捆成一个整体，就是 struct；再加上成员函数，就成了 class。

← 上一课：拷贝控制 · 课程总览 · STL 速查

← 上一课：拷贝控制 下一课：结构体与面向对象入门 →