算法概述与分类：STL 的灵魂所在
说实话，STL 里最让我着迷的部分，就是算法。容器是骨架，迭代器是血脉，而算法——才是真正干活的灵魂。我刚开始用 STL 时，总觉得算法就是一堆函数，后来才发现，它背后有一套极其优雅的分类体系。
今天咱们就来聊聊，STL 算法到底怎么分类，它们和容器、迭代器之间又是什么关系。
算法的四大分类
STL 算法大致可以分为四类：只读算法、修改算法、排序算法和数值算法。这四类基本覆盖了日常开发中 90% 以上的场景。
1. 只读算法
这类算法不会修改容器里的元素。它们只是「看看」数据，然后返回一些信息。
常见的包括：find、count、for_each（如果传入的函数不修改元素的话）、equal、mismatch 等等。
核心特点：传入的迭代器通常是 InputIterator 或 ForwardIterator，不需要写权限。
// 只读算法示例
std::vector<int> vec = {1, 2, 3, 4, 5};
// find 不会修改容器
auto it = std::find(vec.begin(), vec.end(), 3);
if (it != vec.end()) {
// 找到了，it 指向 3
}
// count 只是统计
int cnt = std::count(vec.begin(), vec.end(), 3);我个人习惯在调试时大量使用 for_each 配合 lambda 打印数据，方便又安全。
2. 修改算法
这类算法会改变容器里的元素。注意，我说的是「改变元素」，不是「改变容器大小」。
常见的包括：copy、transform、replace、fill、remove（这个有坑，后面说）。
我曾经踩过的坑：std::remove 并不会真正删除元素！它只是把要删除的元素移到末尾，返回新的逻辑结尾。你得配合 erase 才能真的删掉。这就是所谓的 erase-remove 惯用法。
// 修改算法示例
std::vector<int> vec = {1, 2, 3, 4, 5};
// 每个元素加 10
std::transform(vec.begin(), vec.end(), vec.begin(),
[](int x) { return x + 10; });
// 注意：remove 不会缩小容器
auto new_end = std::remove(vec.begin(), vec.end(), 3);
vec.erase(new_end, vec.end()); // 这才是真正的删除3. 排序算法
排序算法家族很庞大。除了最常用的 sort，还有 stable_sort、partial_sort、nth_element 等等。
| 算法 | 时间复杂度 | 特点 |
|---|---|---|
| sort | O(N log N) | 快排+堆排混合，不稳定 |
| stable_sort | O(N log N) | 归并排序，稳定 |
| partial_sort | O(N log M) | 只排前 M 个 |
| nth_element | O(N) | 只找第 N 大的元素，不排序 |
我的经验：如果你只需要前 10 个最小的元素，千万别用 sort 全排。用 partial_sort 或者 nth_element，性能差距很明显。我在做实时数据处理时，这个优化帮了大忙。
4. 数值算法
这类算法定义在 <numeric> 头文件中。常用的有 accumulate、inner_product、partial_sum、adjacent_difference。
// 数值算法示例
std::vector<int> vec = {1, 2, 3, 4, 5};
// 求和
int sum = std::accumulate(vec.begin(), vec.end(), 0);
// 前缀和
std::vector<int> prefix(vec.size());
std::partial_sum(vec.begin(), vec.end(), prefix.begin());
// prefix = {1, 3, 6, 10, 15}说白了，数值算法就是帮你做数学运算的。我写金融相关的代码时，inner_product 经常用来算向量点积。
算法与容器的关系
这里有个关键点：STL 算法不直接操作容器，而是操作迭代器。这意味着，算法和容器是解耦的。
你想想看，std::sort 可以排序 vector，也可以排序 deque，甚至能排序原生数组。为什么？因为它只要求传入随机访问迭代器。
但有些容器天生就不适合某些算法。比如 list 不支持随机访问，你就不能对它用 sort（不过 list 自己有成员函数 sort）。
核心原则：算法通过迭代器与容器交互。迭代器的能力决定了哪些算法可用。
算法与迭代器的配合
迭代器是算法的「眼睛」和「手」。算法通过迭代器读取数据、写入数据、移动位置。
不同的算法对迭代器有不同的要求：
- InputIterator：只读，单向移动。比如
find、count。 - OutputIterator：只写，单向移动。比如
copy的目标迭代器。 - ForwardIterator：可读写，单向移动。比如
replace。 - BidirectionalIterator：可读写，双向移动。比如
reverse。 - RandomAccessIterator：可读写，随机访问。比如
sort、binary_search。
嗯，这里要注意：如果你传了一个能力不足的迭代器给算法，编译期就会报错。这是 STL 设计的高明之处——错误尽量在编译期暴露。
// 迭代器能力决定算法可用性
std::list<int> lst = {3, 1, 4, 1, 5};
// 编译错误！list 的迭代器不是随机访问迭代器
// std::sort(lst.begin(), lst.end());
// 正确做法：用 list 自己的成员函数
lst.sort();避坑指南：我曾经在项目里用 std::sort 排序 list，编译报错后我还纳闷了半天。后来才意识到，list 的迭代器是双向的，不是随机的。记住：算法对迭代器的要求，就是容器对算法的限制。
知识体系总览
下面这张图，把算法分类、迭代器要求、容器适配关系都串起来了。我建议你多看几遍，理解了这个结构，STL 算法就算入门了。
总结一下：算法分类帮你快速定位功能，迭代器要求决定了使用边界，容器特性影响了实际性能。这三者配合好了，STL 用起来就顺手了。
我个人觉得，理解算法分类最好的方式就是多写、多试。遇到一个需求，先想「这是只读还是修改？」，再想「需要排序吗？」，最后看「容器支持什么迭代器？」。按这个思路走，基本不会出错。