STL 算法

读完能做什么

• 能看懂 算法名(起点, 终点) 这种调用形式，说出它要处理的是哪一段数据。
• 能用“输入范围、返回值、是否修改数据”三个入口读懂一个没见过的算法。
• 能预测只排序一段区间时，哪些位置会变、哪些位置保持原样。
• 能按任务（查找、排序、去重、第 k 小）说出该用哪个算法，并找到本章对应的页面。

为什么需要它

同样一件事——把一组数排好序——数据可能放在普通数组里，也可能放在 vector、deque 里。如果为每种数据各写一份排序代码，同一份逻辑就要重复好几遍。

STL 的做法是：让算法只认位置，不认数据存在哪里。你只要说清“从哪个位置到哪个位置”，算法就能处理。于是同一句 sort(...) 既能排数组，也能排 vector：

sort(a, a + n);              // 普通数组：起点 a，终点 a + n
sort(v.begin(), v.end());    // vector：起点 begin()，终点 end()

这两行片段（省略了头文件和 main）形状几乎一样，只是“起点、终点”换了个写法。本页就把这种调用形式讲清楚，并告诉你本章已经讲过哪些算法、分别解决什么问题。

它是什么

一句话：STL 算法是一批函数模板，它们不关心数据存在哪里，只按“从哪个位置到哪个位置”处理一段数据。

函数模板。 “模板”指同一份代码可以给不同类型使用，编译时按你实际传入的类型生成对应的函数。sort 是函数模板，所以它能排 int、double、string，你不必为每种类型各写一份。

迭代器是算法和容器之间的桥梁。 迭代器是“指向容器中某个位置的游标”：v.begin() 停在第一个元素上，v.end() 停在最后一个元素后面的位置（尾后位置，那里没有元素）。算法只拿到两个位置，就能从头走到尾处理这段数据——它不需要知道数据存在数组还是链表里。

区间 [first, last)。 两个位置组成一个左闭右开区间：包含 first 指向的元素，不包含 last 指向的元素。所以 [v.begin(), v.end()) 正好是整个 vector，[v.begin() + 1, v.begin() + 3) 只含下标 1、2 两个位置。这套约定在容器、迭代器与区间里详细讲过，本页所有算法都遵守它。

普通数组也能用。 数组名可以当成指向首元素的指针，指针在算法眼里就是一种迭代器：a 是起点，a + n 是终点。所以数组不需要任何包装就能交给算法。

graph LR
    data["数据 4 3 1 2"] --> first["起点 first"]
    data --> last["终点 last"]
    first --> algo["算法"]
    last --> algo
    algo --> out["处理后的区间"]

最小可运行示例

用 sort 把 [4, 3, 1, 2] 从小到大排好：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {4, 3, 1, 2};

    sort(v.begin(), v.end());            // 处理整个区间 [begin, end)

    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

1 2 3 4 

逐行看：

• sort(v.begin(), v.end()) 里两个参数就是区间的起点和终点：v.begin() 指向 4，v.end() 是 2 后面那个尾后位置，所以这段区间覆盖全部 4 个元素。
• sort 直接修改 v 里的元素顺序，它不返回新的容器，也不需要你把结果接住。
• 排完之后按顺序打印，得到 1 2 3 4。
• 算法都在 <algorithm> 里声明，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

一步步看变化

还是这组数据 [4, 3, 1, 2]，这次先只排中间两个位置，再排全体。局部排序用区间 [v.begin() + 1, v.begin() + 3)，即下标 1、2：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {4, 3, 1, 2};

    sort(v.begin() + 1, v.begin() + 3);  // 只处理下标 1、2 这两个位置
    cout << "局部排序后：";
    for (int x : v) cout << x << ' ';
    cout << '\n';

    sort(v.begin(), v.end());            // 再处理全体
    cout << "全体排序后：";
    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

局部排序后：4 1 3 2 
全体排序后：1 2 3 4 

v.begin() + 1 指向下标 1 的 3，v.begin() + 3 指向下标 3 的 2。因为区间是左闭右开的，终点取不到，所以真正参与排序的只有下标 1 和 2 上的 3、1。它们排成 1、3 之后，下标 0 的 4 和下标 3 的 2 一动没动，得到 4 1 3 2。

这也解释了为什么“终点写在哪里”特别重要：把终点从 v.begin() + 3 改成 v.begin() + 4（也就是 v.end()），参与排序的位置就多了一个，结果会完全不同。

逐项扩展核心操作

同一个算法，不同的数据来源

sort 不关心数据放在哪里，所以数组和 deque 可以用同一句调用：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[4] = {4, 3, 1, 2};
    deque<int> d = {4, 3, 1, 2};

    sort(a, a + 4);                      // 普通数组：起点 a，终点 a + 4
    sort(d.begin(), d.end());            // 容器：起点 begin()，终点 end()

    cout << "数组：";
    for (int i = 0; i < 4; i++) cout << a[i] << ' ';
    cout << '\n';
    cout << "deque：";
    for (int x : d) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

数组：1 2 3 4 
deque：1 2 3 4 

同一份 sort 代码为什么能处理两种数据？因为算法只要求迭代器支持它需要的操作，不要求数据存放在哪里。sort 需要随机访问迭代器（能随意跳、能相减），数组指针、vector、deque 的迭代器都满足；list 的迭代器只能 ++ / --，不满足，所以 sort(l.begin(), l.end()) 编译不过，要改用成员函数 l.sort()（见 list 链表）。

读懂一个算法的三个入口

遇到一个没见过的算法，先问三个问题：

1. 输入范围是什么？ 从哪个位置到哪个位置？对数据有没有额外要求（比如必须已经有序）？
2. 返回值是什么？ 什么都不返回、返回一个位置、返回 true/false，还是返回一个个数？
3. 会不会修改数据？ 只是读一遍，还是会把元素重新排列？

用本章的算法对照一遍：

输入范围：只处理一段

find 是“找到某个值的位置”，用它看区间怎么起作用。只在后两个位置里找 3：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {8, 3, 5, 3};

    auto it = find(v.begin() + 2, v.end(), 3);          // 只在后两个位置里找
    cout << "从下标 2 开始找 3，命中下标 " << (it - v.begin()) << '\n';

    bool inFront = (find(v.begin(), v.begin() + 2, 5) != v.begin() + 2);
    cout << "前两个位置里有 5 吗：" << inFront << '\n';
    return 0;
}

输出：

从下标 2 开始找 3，命中下标 3
前两个位置里有 5 吗：0

• 第一个 find 的区间是 [begin + 2, end)，只覆盖下标 2、3 上的 5、3，所以命中下标 3 的那个 3，而不是下标 1 的 3。
• 第二个 find 的区间是 [begin, begin + 2)，只覆盖下标 0、1 上的 8、3。里面没有 5，于是它返回区间的终点 begin + 2；把它和终点比较，得到 false，打印 0。
• 没找到时返回的是“你给的终点”，不是“容器的终点”。 判断有没有找到，一定要拿返回值和同一个终点比较。

返回值：位置、真假

find 返回一个位置，这个位置不能直接拿来用：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {8, 3, 5, 3};

    auto it = find(v.begin(), v.end(), 3);   // 输入区间 [begin, end)，要找 3
    if (it != v.end()) {                     // 返回值是位置，先和终点比较
        cout << "找到 3，下标 " << (it - v.begin()) << '\n';
    } else {
        cout << "没找到 3\n";
    }

    cout << "找完之后 v 的内容没变：";
    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

找到 3，下标 1
找完之后 v 的内容没变：8 3 5 3 

• it != v.end() 是必须的一步：find 找不到时返回终点，直接解引用会越界。这属于“解引用之前先确认位置有效”的通用习惯。
• it - v.begin() 把位置换算成下标。这个减法只有随机访问迭代器（vector、deque、数组）支持，list、set 上不能这样算。
• 输出最后一行说明 find 没有修改 v：它只是读了一遍。

和它相反的是 sort：sort 没有返回值，但它会改动数据本身。返回值、是否修改数据，就是这两个算法的区别所在。

按任务找页面

本章已经讲过的算法只有下面这些，遇到对应任务时直接翻那一页：

<algorithm> 头文件里还有几十个别的函数。本页只列本章已经讲过的部分，等你需要时再查手册——不要因为一个函数“名字看着眼熟”就以为已经掌握它的前提条件和返回值。

选择自测：下面四个任务分别该翻哪一页、用哪个算法？先自己回答，再展开核对。

1. 一组数已经按从小到大排好，只要判断 7 在不在里面。
2. 读入一堆整数，要去重后按从小到大输出。
3. 只想知道第 5 小的数是多少，不要求把整组数排好。
4. 数据存在 list 里，想排序。

什么时候选它、哪里容易错

区间是左闭右开的。 [first, last) 不包含 last。所以“处理前 3 个元素”写 [begin, begin + 3)，“处理整个容器”写 [begin, end())。终点写多一格、写少一格，结果就变了。

注意算法的前提条件。 binary_search、lower_bound、upper_bound 都要求区间已经按同一规则有序；sort 要求随机访问迭代器。前提不满足时，要么编译不过，要么结果不可靠：

// 错误示例：二分查找要求区间已经有序，下面这段在乱序数据上调用，结果不可靠
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 2};            // 没有排序

    cout << binary_search(v.begin(), v.end(), 2) << '\n';   // 结果不可靠，不要照着写
    return 0;
}

这段能编译，但打印出来的真假没有意义：二分查找每步都要“砍掉一半”，数据没序就砍错了地方。要先用 sort 排好，再查。

返回值要检查再用。 find、lower_bound、upper_bound 返回的是位置，没找到时返回终点；解引用之前先和终点比较。binary_search 返回的是 bool，不能拿它当下标用。

复杂度差别很大。

算法不调用容器的成员函数。 它只拿到两个位置，然后通过迭代器一步步走。所以算法不知道容器里现在有多少元素、会不会扩容，它只负责“把这段区间处理好”——这也是它能同时服务数组和各种容器的原因。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

vector<int> v = {5, 2, 4, 3, 1};
sort(v.begin() + 1, v.begin() + 4);      // 只处理下标 1、2、3
for (int x : v) cout << x << ' ';

第 2 题：修改代码

下面这段片段现在把 [4,3,1,2] 全体排序。请改成只排后 3 个位置（下标 1、2、3），让输出变成 4 1 2 3：

vector<int> v = {4, 3, 1, 2};
sort(v.begin(), v.end());                // 现在排的是全体
for (int x : v) cout << x << ' ';

验证条件：先说出新的区间起点、终点分别指向哪个位置，以及下标 0 的元素为什么不会动，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {5, 2, 4, 3, 1};

    sort(v.begin() + 1, v.begin() + 4);      // 只处理下标 1、2、3
    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

5 2 3 4 1 

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {4, 3, 1, 2};

    sort(v.begin() + 1, v.end());            // 只排后 3 个位置

    for (int x : v) cout << x << ' ';
    cout << '\n';
    return 0;
}

4 1 2 3 

立即练习

本页是算法入口课，重点是读懂“区间 + 返回值 + 是否修改数据”这套调用形式，所以不安排 OJ 题目：本章每一类算法都有自己的页面，等你学完 sort、查找、去重、nth_element 之后，再到各页的「立即练习」做题更合适。