算法库概览与分类

从厨师技能说起

一位优秀的大厨不仅懂得选食材（容器），还掌握各种技法：切、剁、炒、蒸、烤、炸……在STL（标准模板库）中，算法就是这些技法。它们可以“处理”容器里的数据，完成排序、查找、复制、变换等任务。算法不关心容器是如何存储数据的，只通过迭代器打交道，因此通用性极强。

举个例子，就像你整理书包时，可能会用到：

• 查找：在乱糟糟的书包里找数学书（find）
• 统计：数一数有多少支笔（count）
• 排序：把试卷按分数从低到高排好（sort）
• 复制：把作业本上的答案抄到新本子上（copy）
• 替换：把试卷上写错的“0”改成“10”（replace）

STL算法主要分布在两个头文件中：

• <algorithm>：包含最常用的算法，如查找、排序、替换、分区等。
• <numeric>：包含数值算法，如累加、内积、部分和等。

本章将介绍最常用、竞赛中最可能用到的算法，并强调时间复杂度和适用场景。学完这部分，你就像拿到了一个万能工具箱，以后遇到各种数据处理问题，都能轻松找到对应的“工具”。

算法分类

1. 非修改式算法（Non-modifying）

这些算法只读取元素，不改变容器的内容。就像你在图书馆看书时，只是翻看内容，不会在书上乱画一样。

生活中的例子：

• find：你想从一摞试卷中找出自己的那张（学号=35），就从第一张开始一张张翻看，直到找到为止。这就像你排队时找朋友，一个个看过去。
• count：老师想知道班里有多少人考了100分，于是从头到尾数一遍。如果你记性差，数完一遍可能还要再数一遍确认。
• search：在作文里找“比赛”这个词第一次出现在哪一页。但注意，如果文章很长，这个方法会比较慢（O(n*m)），就像你用手工一页页翻找，而更聪明的方法（KMP算法）可以更快。
• adjacent_find：检查一串数字中是否有连续两个相同的数，比如你的学号[3,5,5,2]中，5和5相邻重复了。这就像检查作业本上有没有连着两题都写错了同样的答案。

示例：find和count最常用。比如你有一个存放零花钱的列表 money = [20, 10, 5, 10, 50]，想知道有没有10元钱，用find；想知道10元出现了几次，用count。

2. 修改式算法（Modifying）

这些算法会修改容器中的元素内容。就像你在画画时，不仅看画，还会用橡皮擦擦掉或重新涂色。

生活中的例子：

• copy：你写了一篇作文，老师要求你把草稿誊写到正式作文本上。你用笔把内容原封不动地抄过去（copy），当然也可以只抄一部分。
• fill：开学了，你拿出一个空的铅笔盒，把每一格都放上一支铅笔（全部设为“铅笔”）。或者你做一个全0的数组来存储考试成绩，用fill一次性归零。
• transform：体育课老师让每个人做两次仰卧起坐，于是你把自己做的个数乘以2。这就是对每个元素做变换（操作是“乘以2”）。
• replace：你在一张错题集里，把所有“×”号改成“√”号，表示已经订正过的题目。
• remove：你有一堆零食，想扔掉所有过期的。你先把没过期的挑出来放在前面（remove），然后扔掉后面剩下的空位置（erase）。注意：remove并不会真的扔掉东西，它只是把要保留的挪到前面，后面的位置还留着旧东西，你需要手动清理（erase）才能腾出空间。
• reverse：把一摞试卷的顺序倒过来，最上面变成最下面。就像你在玩扑克牌时把整副牌反过来。
• rotate：你按学号排队，现在想从第5个同学开始重新排队，让第5个变成第1个。这就像循环移位。

注意：remove并不真正删除元素，它把要保留的元素挪到前面，返回新的end迭代器，需要调用容器的erase才能释放空间（“remove-erase惯用法”）。很多新手会忘记erase，结果容器大小没变，后面的“垃圾”元素还在，只是逻辑上移到了后面。

3. 排序及相关算法

这是信息学竞赛中使用频率最高的算法。就像你每次考试后都要把成绩单按分数排序，以便知道谁考得最好。

生活中的例子：

• sort：期末考试后，老师把全班成绩从低到高排序。如果两个同学分数相同，sort可能把他们原来的前后顺序打乱（不稳定），而stable_sort会保持他们在原名单中的先后顺序（稳定）。
• partial_sort：你只想知道班上成绩最好的前5名是谁，不需要把所有人的成绩都排好。就像我们常说的“排名前5”，用partial_sort最快。
• nth_element：你想知道中位数（第n小的数）是多少，但不需要完全排序。比如全班50人，第25名的分数是多少？nth_element只保证第25名在正确位置，左边都小于等于它，右边大于它，但左右内部可能没排序。这比先全部排序快很多。
• binary_search：你有一本按拼音排好的字典，想查“机器”这个词是否存在。你不用从头翻到尾，而是每次翻到中间，比较拼音，缩小范围，很快就能找到。这就是二分查找，前提是字典必须已经排好序。
• lower_bound和upper_bound：在成绩单中，你想知道所有得90分的同学有哪些。先找到第一个≥90的位置（lower_bound），再找到第一个>90的位置（upper_bound），这两个位置之间的区域就是所有90分。这就像在有序名单中划出所有90分的区间。
• merge：你有两个按学号排好的班级名单，想合并成一个总的名单（仍然按学号有序）。就像把两堆排好的扑克牌合在一起，每次取最小的那张。
• inplace_merge：你有一份名单，前半部分按语文成绩排好，后半部分也按语文成绩排好，现在想把整个名单合并成一个有序的。就像你把两段排好的队伍直接合并，不需要额外场地。

重点解释：

• sort是快速排序+插入排序混合，不稳定；stable_sort是归并排序，稳定但需要O(n)额外空间。
• nth_element是选择算法（introselect），平均O(n)，常用于求中位数或第k小。
• lower_bound和upper_bound配合可以确定值value在有序数组中的范围（equal_range）。在竞赛中，这两个函数非常实用，比如求“小于等于x的元素个数”或“大于x的元素个数”。

4. 集合算法（Set Algorithms）

用于有序容器（如set、排序后的vector），需要区间已有序。

• set_union(b1,e1,b2,e2,out)：并集。
• set_intersection(b1,e1,b2,e2,out)：交集。
• set_difference(b1,e1,b2,e2,out)：差集（在第一个中有不在第二个中的）。
• set_symmetric_difference(b1,e1,b2,e2,out)：对称差。

时间复杂度：O(n1+n2)。

生活中的例子：

• 并集：把两个班的兴趣小组名单合并，重复的人只算一次，得到总名单。
• 交集：找出同时参加了数学和英语兴趣小组的同学。
• 差集：找出只参加了数学但没有参加英语的同学。
• 对称差：找出只参加了其中一个兴趣小组的同学（不包含两个都参加的）。

注意：这些算法要求输入区间已经排好序。如果容器没有排序，你需要先用sort排好。另外，如果使用std::set容器，它本身就有对应的成员函数（比如set_union可以用std::set的insert结合遍历实现），但算法版本更通用。

5. 数值算法（Numeric）

定义在<numeric>中。

• accumulate(begin,end,init)：累加，init为初始值。
• inner_product(b1,e1,b2,init)：内积（对应元素相乘再累加）。
• partial_sum(begin,end,out)：部分和序列。
• adjacent_difference(begin,end,out)：相邻差序列。

生活中的例子：

• accumulate：计算你一周的零花钱总和。比如周一5元、周二10元、周三0元……累加得到总金额。
• inner_product：计算你买了两种商品的总花费：商品A买了3个单价5元，商品B买了2个单价8元，内积就是3×5 + 2×8 = 31元。这就像两个向量对应位置相乘再相加。
• partial_sum：你每天做作业，第一天做了2页，第二天做了4页，第三天做了6页，部分和就是每天累计做的页数：2, 6, 12。
• adjacent_difference：你记录了每天跑步的距离，想知道每天比前一天多跑了多少（相邻差）。比如第一天5km，第二天7km，第三天6km，相邻差就是：5（第一天距离），2（7-5），-1（6-7）。

新手容易犯的错误

在学习STL算法时，初学者经常会掉入几个常见的坑。记住它们，能让你少走弯路：

1. 忘记包含头文件
   #include <algorithm> 和 #include <numeric> 是必不可少的。很多同学只写了#include <iostream>，然后直接用sort导致编译错误。

2. 对未排序的容器使用二分查找
   binary_search、lower_bound、upper_bound 必须在已经排好序的区间上使用，否则结果错误。就像在乱序的书架上用二分法找书，根本找不到。

3. remove之后忘记erase
remove不会改变容器大小，它只是把要保留的元素挪到前面，返回新逻辑终点。必须紧接着调用erase(newEnd, container.end())才能真正删除。如果不erase，容器内还留有旧值，但逻辑上你可能会把它们当作有效数据，导致奇怪的结果。

4. 对不支持随机访问的容器使用sort
sort、partial_sort等需要随机访问迭代器，因此不能用于std::list。std::list有自己的sort成员函数。同样，std::forward_list也有自己的排序。

5. 混淆nth_element和partial_sort
nth_element只保证第n个元素在正确位置，左边都比它小（但不一定有序），右边都比它大（也不一定有序）。而partial_sort会把前k个元素排好序。如果你需要前k个有序的结果，用partial_sort；如果只需要知道第k大的值，用nth_element更快。

6. merge的输入区间必须有序
   merge要求两个输入区间都是排好序的，否则合并结果混乱。就像把两堆乱牌合并，不可能得到有序的牌堆。

7. 初始值类型影响结果
   accumulate的初始值类型决定了返回类型。例如accumulate(v.begin(), v.end(), 0)返回int，若列表有小数会丢失精度。如果希望得到浮点数，应该用0.0作为初始值。

C++完整演示：各种算法实战

下面是一个完整的C++程序，包含所有主要算法的使用。代码中每一行变量定义都加了中文注释，方便理解。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>  // 用于 ostream_iterator

int main() {
    // ========== 原始数据 ==========
    std::vector<int> vec = {5, 3, 9, 1, 7, 3, 6};  // 一个包含多个数字的向量

    // ---- 非修改式算法 ----
    // 查找值为7的第一个位置
    auto it = std::find(vec.begin(), vec.end(), 7);
    if (it != vec.end()) 
        std::cout << "找到了7，索引: " << (it - vec.begin()) << std::endl;

    // 统计值为3的个数
    int cnt = std::count(vec.begin(), vec.end(), 3);
    std::cout << "3出现了 " << cnt << " 次" << std::endl;

    // ---- 修改式算法 ----
    // 复制所有元素到新向量
    std::vector<int> copyVec(vec.size());          // 新向量，大小与vec相同
    std::copy(vec.begin(), vec.end(), copyVec.begin());  // 复制

    // 把值为3的元素替换为99
    std::replace(vec.begin(), vec.end(), 3, 99);
    std::cout << "替换后: ";
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    // remove-erase惯用法：删除所有值为99的元素
    auto newEnd = std::remove(vec.begin(), vec.end(), 99);  // 把不是99的元素挪到前面
    vec.erase(newEnd, vec.end());                            // 真正删除后面的位置
    std::cout << "删除99后: ";
    for (int x : vec) std::cout << x << " ";
    std::cout << std::endl;

    // ---- 排序算法 ----
    std::vector<int> vec2 = {5, 3, 9, 1, 7, 3, 6};  // 新数据，用于排序演示
    std::sort(vec2.begin(), vec2.end());              // 快速排序（不稳定）
    std::cout << "排序后: ";
    for (int x : vec2) std::cout << x << " ";
    std::cout << std::endl;

    // 二分查找：判断6是否在已排序的vec2中
    bool found = std::binary_search(vec2.begin(), vec2.end(), 6);
    std::cout << "binary_search 6: " << (found ? "true" : "false") << std::endl;

    // lower_bound / upper_bound：确定值为5的范围
    auto lb = std::lower_bound(vec2.begin(), vec2.end(), 5);   // 第一个>=5的位置
    auto ub = std::upper_bound(vec2.begin(), vec2.end(), 5);   // 第一个>5的位置
    std::cout << "等于5的范围: [" << (lb - vec2.begin()) << ", " 
              << (ub - vec2.begin()) << ")" << std::endl;

    // nth_element：求第4小的数（索引3），不加排序
    std::vector<int> vec3 = {5, 3, 9, 1, 7, 3, 6};  // 新数据
    std::nth_element(vec3.begin(), vec3.begin() + 3, vec3.end());
    std::cout << "第4小的数是: " << vec3[3] << std::endl;  // 结果是5（排序后1,3,3,5,6,7,9）

    // ---- 集合算法 ----
    std::vector<int> a = {1, 3, 5, 7};  // 已排序的集合A
    std::vector<int> b = {3, 5, 8};     // 已排序的集合B
    std::vector<int> uni;               // 存储并集的结果
    std::set_union(a.begin(), a.end(), b.begin(), b.end(), 
                   std::back_inserter(uni));  // 将并集追加到uni
    std::cout << "并集: ";
    for (int x : uni) std::cout << x << " ";
    std::cout << std::endl;

    // ---- 数值算法 ----
    std::vector<int> vec4 = {2, 4, 6};  // 数值数据
    int sum = std::accumulate(vec4.begin(), vec4.end(), 0);  // 累加，初始值0
    std::cout << "sum = " << sum << std::endl;

    // 部分和
    std::vector<int> ps(vec4.size());                      // 存储部分和
    std::partial_sum(vec4.begin(), vec4.end(), ps.begin()); // 计算：2, 6, 12
    std::cout << "部分和: ";
    for (int x : ps) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

代码详细说明：

• 第10行：std::find返回迭代器，计算索引使用it - vec.begin()（仅对随机访问迭代器有效，如vector、array、string）。
• 第18行：std::ostream_iterator是一个输出迭代器，直接将元素打印到cout，相当于for循环遍历输出。这里用" "作为分隔符。
• 第24行：std::remove不改变容器大小，erase后才是真正删除。这是“remove-erase惯用法”。
• 第31行：std::sort接受随机访问迭代器，vector满足。
• 第39行：std::lower_bound和upper_bound返回迭代器，相减得索引。注意区间是左闭右开，所以等于5的范围是[lb, ub)，包含lb但不包含ub。
• 第44行：std::nth_element只保证第n个元素在正确位置，两边未必有序。这里是找第4小的（下标3），结果可能是5。
• 第52行：std::back_inserter自动调用push_back，这样无需提前预分配大小。
• 第59行：std::accumulate第三个参数是初始值，类型影响结果（若用0.0可得到浮点结果）。

Python中的等价功能

Python内置函数和itertools、bisect、heapq等模块提供了类似功能，但风格更函数式。下面演示Python版本，同样每行变量定义都加了中文注释。

import itertools
import bisect
import heapq

# ========== 原始数据 ==========
vec = [5, 3, 9, 1, 7, 3, 6]  # 一个包含多个数字的列表

# ---- 非修改式 ----
# find: 用list.index或in
try:
    idx = vec.index(7)  # 查找7第一次出现的位置
    print("找到了7，索引:", idx)
except ValueError:
    print("未找到")

# count: 统计个数
cnt = vec.count(3)  # 3出现了几次
print("3出现了", cnt, "次")

# ---- 修改式 ----
# 复制
copy_vec = vec.copy()  # 复制一份

# replace: 列表推导式（把3替换为99）
vec2 = [99 if x == 3 else x for x in vec]  # 条件表达式
print("替换后:", vec2)

# remove所有99：列表推导式过滤
vec2_clean = [x for x in vec2 if x != 99]  # 只保留不等于99的元素
print("删除99后:", vec2_clean)

# ---- 排序 ----
vec3 = [5, 3, 9, 1, 7, 3, 6]  # 新数据
vec3.sort()  # 原地排序，默认升序
print("排序后:", vec3)

# 二分查找（bisect模块，要求列表已排序）
import bisect
idx = bisect.bisect_left(vec3, 6)  # 第一个>=6的位置
found = idx < len(vec3) and vec3[idx] == 6
print("bisect查找6:", found)

# lower_bound / upper_bound
lb = bisect.bisect_left(vec3, 5)   # 第一个>=5的位置
ub = bisect.bisect_right(vec3, 5)  # 第一个>5的位置
print("等于5的范围: [", lb, ",", ub, ")")

# 第k小：使用heapq.nsmallest
vec4 = [5, 3, 9, 1, 7, 3, 6]  # 新数据
kth = heapq.nsmallest(4, vec4)[-1]  # 第4小的数（先取最小的4个，再取最后一个）
print("第4小的数是:", kth)  # 结果是5

# ---- 集合算法 ----
a = [1, 3, 5, 7]  # 已排序或可转为set
b = [3, 5, 8]
uni = sorted(set(a) | set(b))  # 并集：先用set去重，再排序
print("并集:", uni)

# ---- 数值 ----
vec5 = [2, 4, 6]  # 数值数据
print("sum =", sum(vec5))  # 直接求和

# 部分和（itertools.accumulate）
from itertools import accumulate
ps = list(accumulate(vec5))  # 每次累加的结果：[2, 6, 12]
print("部分和:", ps)

说明：

• Python的list.index是线性查找，等价于find。如果元素不存在会抛出异常，所以要用try-except。
• 列表推导式是修改式算法的常用实现，灵活高效。例如[99 if x == 3 else x for x in vec]相当于replace。
• bisect模块提供二分查找，但要求列表已排序。bisect_left和bisect_right分别对应lower_bound和upper_bound。
• heapq.nsmallest(k, iterable)使用堆，时间复杂度O(n log k)，适合取前k小。如果k接近n，不如直接排序。
• set运算直接支持并、交、差，非常简洁。但注意set是无序的，需要排序得到有序结果。
• Python的sum函数直接累加，等同于accumulate的最终结果。如果需要部分和序列，用itertools.accumulate。

总结与注意事项

要点

1. STL算法通过迭代器操作容器，不与具体容器类型耦合。你可以对vector、array、deque甚至普通数组使用同样的算法。
2. 排序、查找、变换是竞赛中最常用的三大类算法。学会它们，能解决大部分数据处理问题。
3. 注意算法的稳定性：sort不稳定，stable_sort稳定；partial_sort和nth_element用途不同，一个取前k个有序，一个只找第k个值。
4. 带_if后缀的算法（如find_if）允许传入谓词（函数或lambda），用于自定义条件。例如查找第一个大于10的数：find_if(v.begin(), v.end(), [](int x){ return x > 10; })。
5. Python的算法散落在内置函数和模块中，需要熟悉itertools、bisect、heapq、collections等。虽然语法不同，但思想相通。

注意事项

• 算法要求迭代器类型：例如sort需要随机访问迭代器，list不能直接使用，但它自身提供了list::sort成员函数（基于归并）。
• 指针也是随机访问迭代器，所以STL算法可以直接用于普通数组：int arr[5] = {3,1,4,1,5}; sort(arr, arr+5);。
• 使用remove后务必调用erase，否则容器大小不变，逻辑上出现空洞。这是C++特有的“remove-erase惯用法”，Python中直接用列表推导式或filter更安全。
• 对于复杂对象，算法默认使用operator<或operator==，可自定义比较器（通常写lambda或仿函数）。例如按学生成绩降序排序：sort(students.begin(), students.end(), [](const Student& a, const Student& b){ return a.score > b.score; });。
• Python中sort默认升序，可指定reverse=True或key函数进行自定义排序。

算法是STL的灵魂。掌握它们后，你可以像搭积木一样组合算法和容器，高效解决问题。如果想进一步了解，推荐继续学习：

• 迭代器类型：为什么有些算法只能用于vector而不是list？这关系到迭代器分类（输入、输出、前向、双向、随机访问）。
• 容器选择：不同容器适合不同的算法，比如set内部已排序，可以快速二分查找；unordered_set适合快速查找但不支持排序。
• 自定义比较器：在sort、lower_bound等算法中如何使用lambda或函数对象，这是竞赛中非常实用的技能。

现在，你可以打开编译器或Python解释器，亲自运行上面的示例代码，尝试修改参数，看看结果如何变化。动手实践是学习算法的最佳方式！