第十四章 STL 算法：标准库的"瑞士军刀"

本章目标：熟练使用 <algorithm> 里的核心算法，理解"算法 + 迭代器 + lambda"的组合拳。这是从"会写循环"到"会写现代 C++"的跨越。

14.1 为什么要学算法？

// 烂代码：手写循环找最大值
int m = v[0];
for (auto& x : v) if (x > m) m = x;

// 好代码：一句话
auto m = *std::max_element(v.begin(), v.end());

手写循环容易错（边界、空容器、索引混乱），标准库算法久经考验、意图一目了然。原则：**能调用算法就不写循环**。

14.2 查询类算法

std::find(v.begin(), v.end(), x);        // 找 x，返回迭代器
std::count(v.begin(), v.end(), x);       // x 出现几次
std::count_if(v.begin(), v.end(), pred); // 满足条件的个数
std::max_element(v.begin(), v.end());    // 最大元素迭代器
std::min_element(v.begin(), v.end());    // 最小
std::minmax_element(...);                // 一起找
std::all_of(v, pred);                    // 全都满足？
std::any_of(v, pred);                    // 有满足的吗？
std::none_of(v, pred);                   // 全都不满足？
std::binary_search(v, x);                // 有序容器二分查找 O(log n)

找满足条件的第一个：

auto it = std::find_if(v.begin(), v.end(),
                       [](int x){ return x > 100; });
if (it != v.end()) { /* 找到了 *it */ }

14.3 修改类算法

std::sort(v.begin(), v.end());                 // 升序
std::sort(v.begin(), v.end(), std::greater<>()); // 降序
std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

std::reverse(v.begin(), v.end());              // 反转
std::rotate(v.begin(), v.begin()+2, v.end());  // 旋转
std::fill(v.begin(), v.end(), 0);              // 全部填 0
std::replace(v.begin(), v.end(), old, new);    // 替换
std::remove_if(v.begin(), v.end(), pred);      // 移除满足的
// ⚠ remove_if 后要 erase！经典组合：
v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());

std::unique(v.begin(), v.end());               // 相邻去重（先 sort！）
std::copy(a.begin(), a.end(), b.begin());      // 复制

三个最常用组合拳（背下来）：

1. 排序：sort
2. 去重：sort + unique + erase
3. 删除：erase + remove_if

14.4 变换与生成

std::transform(a.begin(), a.end(), b.begin(),
               [](int x){ return x * 2; });      // a → b
// 就地：b 换成 a
std::transform(a.begin(), a.end(), a.begin(), f);

std::accumulate(v.begin(), v.end(), 0);            // 求和
std::accumulate(v.begin(), v.end(), 1, [](int a,int b){ return a*b; });

// C++23 有更现代的 fold_left（ranges 版，新版 libc++ 才有）：
// std::ranges::fold_left(v, 0, std::plus<>{});

// 生成序列
std::vector<int> v2(10);
std::iota(v2.begin(), v2.end(), 0);   // 0,1,2,...,9

14.5 排序 + 比较：给自定义类型排序

给结构体按成员排序：

struct Student { std::string name; int score; };

std::vector<Student> stu{...};
std::sort(stu.begin(), stu.end(),
          [](const Student& a, const Student& b) {
              return a.score > b.score;   // 按分数降序
          });

lambda 就是"自定义排序规则"的口子，一切排序都靠它。（也可以用三路比较运算符让类型自带排序，见 12.3。）

14.6 ranges 版（C++20，正式推荐）

所有上面这些都有 ranges 版本，少写 begin/end：

std::ranges::sort(v);
std::ranges::sort(v, std::greater<>{});        // 降序
std::ranges::sort(v, {}, &Student::score);     // 按成员直接排！

std::ranges::find(v, x);
std::ranges::count_if(v, pred);
std::ranges::max_element(v);
// fold_left 是 C++23，libc++ 更新后可用，现在用 accumulate 代替

第三个参数投影（projection）是大杀器：

std::ranges::sort(v, {}, &Student::score);
// 意思是：按 score 成员的值排序，不用写 lambda！

std::ranges::max_element(students, {}, &Student::score);
// 分数最高的学生

新代码统一用 std::ranges:: 版本，顺手还能接视图管道。

14.7 算法实战套路汇总

需求 → 代码：

找最大/最小 → max_element / min_element
统计 → count_if
排序 → sort + 自定义 lambda
去重 → sort + unique + erase
删除 → erase + remove_if
变换 → transform / views::transform
汇总 → accumulate / fold_left
判断 → all_of / any_of
二分查找（大数据）→ binary_search（先排序）

14.8 性能意识（一句话原则）

排序 O(n log n)，二分查找 O(log n)——大数据先排序再查
频繁增删用对容器（vector 头插慢，deque/list 快）
拷贝大对象：传引用、用移动、用视图
永远先写对，再优化；用 profiling 说话，别猜

本章小结

核心算法：find/count/sort/reverse/transform/accumulate/fill
组合拳：sort+unique+erase 去重、erase+remove_if 删除
自定义排序全靠 lambda（或投影 &Student::score）
新代码用 std::ranges:: 版本，少写 begin/end
原则：能调算法就不写循环

练习题

统计一段文本中每个单词的出现次数（map + 算法）。
给 Student 列表按分数降序排序，并列打印前三名。
用 erase+remove_if 删掉 vector 里所有负数。
用 transform 把 string 变成全大写。
用 any_of 判断一组分数里有没有不及格的。