C++ 常用 STL 算法

在日常处理容器数据时，像 “统计某个值出现了几次”、“把元素顺序倒过来” 或者 “找出最大和最小的元素”，都是非常高频的操作。在 C++ 中，标准库已经在 <algorithm> 头文件中把这些功能封装成了现成的算法函数，我们直接调用即可，省去了每次手写循环的麻烦。

除了前面单独学过的排序、查找与去重之外，下面这 4 组算法函数在实际开发中的使用频率也非常高，具体作用如下表所示。

std::count() 和 std::count_if()

在 C++ 中，当我们需要统计容器里有多少个元素符合要求时，可以根据需求选择按固定值统计的 std::count() 或按条件统计的 std::count_if()。这两个函数都只负责读取和计数，不会修改原容器中的任何元素。

1. std::count() 按值统计

std::count() 用来统计指定的 [first, last) 区间内，等于目标值 value 的元素一共有多少个。

语法：

auto times = std::count(first, last, value);

说明：

first 和 last 分别表示统计范围的起始与结束边界，value 表示要统计的目标值。该函数直接返回匹配元素的个数：如果目标值一次都没有出现，则返回 0。

2. std::count_if() 按条件统计

如果我们想统计 “大于等于 60 分的及格人数” 或者 “偶数的个数”，也就是按照某个判断条件来计数，就可以使用 std::count_if() 并配合前面学过的 Lambda 表达式。

语法：

auto times = std::count_if(first, last, pred);

说明：

第 3 个参数 pred 是自定义的判断函数或 Lambda 表达式。std::count_if() 会把区间内的每个元素依次传给 pred 检查，并统计 pred 返回 true 的总次数。下面我们通过一个例子同时看看这两个函数的用法。

示例 1：统计元素个数

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores = {100, 55, 80, 100, 45, 90};

    // 1. 统计等于 100 的元素个数
    auto fullCnt = std::count(scores.begin(), scores.end(), 100);
    std::cout << "满分人数：" << fullCnt << '\n';

    // 2. 统计大于等于 60 的元素个数
    auto passCnt = std::count_if(scores.begin(), scores.end(),
        [](int s) {
            return s >= 60;
        });
    std::cout << "及格人数：" << passCnt << '\n';
    return 0;
}

运行结果如下。

满分人数：2
及格人数：4

分析：

在这个例子中，我们第 1 次调用 std::count() 查找等于 100 的分数。因为 scores 里一共有两个 100，所以 fullCnt 的值为 2。

第 2 次调用 std::count_if() 时，Lambda 表达式对每个分数检查 s >= 60。其中 100、80、100、90 共 4 个分数满足条件，因此统计出的 passCnt 为 4。

小伙伴们可以将它和前面学过的 std::find() 对比记忆。std::find() 找到第 1 个匹配项就会立即停下来并返回位置，而 std::count() 和 std::count_if() 会把整个区间检查一遍，算出总个数。

std::reverse() 函数

std::reverse() 函数用来将指定区间内的元素顺序直接倒过来，也就是把原来的第 1 个元素换到最后、最后一个元素换到最前面。

语法：

std::reverse(first, last);

说明：

first 和 last 分别表示反转范围的起始与结束边界。std::reverse() 没有返回值，它会直接修改原容器中的元素顺序。

此外，由于反转时需要从首尾两端同时往中间交换元素，它要求容器的迭代器支持双向移动，像 vector、array、deque、list 和 std::string 都可以使用。

示例 2：反转 vector 元素

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums = {10, 20, 30, 40, 50};

    std::reverse(nums.begin(), nums.end());

    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

50 40 30 20 10

分析：

std::reverse(nums.begin(), nums.end()); 表示将整个 nums 容器的元素顺序原地反转，执行后里面的数据直接变成了 50 40 30 20 10。

在前面学习字符串反转时，我们调用的其实就是同一个函数。如果只想把容器中间的某一段元素倒过来，只需要调整传入的起止位置即可。

std::min_element() 和 std::max_element()

std::min_element() 和 std::max_element() 分别用来在指定区间内查找最小元素和最大元素。

这里有一个初学者特别容易踩坑的细节：它们返回的不是最值本身，而是指向最值所在位置的迭代器。我们拿到返回值之后，必须加上 * 解引用才能读取到具体的数值。

语法：

auto minIt = std::min_element(first, last);
auto maxIt = std::max_element(first, last);

说明：

当查找区间不为空时，它们分别返回指向最小元素和最大元素的迭代器。如果区间内存在多个相同的最值，则返回第 1 个最值所在的位置。

如果传入的是空容器，它们会直接返回结束边界 last。因此在不确定容器是否为空时，小伙伴们在解引用前记得先判断 minIt != 容器.end()。

示例 3：查找最小值和最大值

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums = {8, 3, 12, 5, 7};

    auto minIt = std::min_element(nums.begin(), nums.end());
    auto maxIt = std::max_element(nums.begin(), nums.end());

    if (minIt != nums.end() && maxIt != nums.end()) {
        auto minPos = minIt - nums.begin();
        auto maxPos = maxIt - nums.begin();
        std::cout << "最小值：" << *minIt << '\n';
        std::cout << "最小值下标：" << minPos << '\n';
        std::cout << "最大值：" << *maxIt << '\n';
        std::cout << "最大值下标：" << maxPos << '\n';
    }
    return 0;
}

运行结果如下。

最小值：3
最小值下标：1
最大值：12
最大值下标：2

分析：

minIt 指向最小元素 3 所在的位置，maxIt 指向最大元素 12 所在的位置。返回迭代器的好处在于，我们既能通过 *minIt 和 *maxIt 拿到最值本身，又能通过 minIt - nums.begin() 一步算出它的下标。

平时写代码时，下面这种漏掉 * 直接输出返回值的写法是错误的，因为 std::cout 无法直接打印一个迭代器对象。

auto maxIt = std::max_element(nums.begin(), nums.end());
std::cout << maxIt << '\n';    // 编译报错

std::fill() 函数

在实际开发中，我们有时需要把一个已有容器里的全部或某一段元素统一重置为同一个值，比如在新一局游戏开始前把所有玩家的得分清零，或者把某一段标记位全部设为 -1。这时使用 std::fill() 函数就非常方便。

语法：

std::fill(first, last, value);

说明：

std::fill() 会将 [first, last) 区间内的每一个元素都赋值为 value。这里小伙伴们要注意，它只负责修改容器里已经存在的元素，不会自动帮容器扩容。

如果容器还是空的，千万不要写成 std::fill(nums.begin(), nums.begin() + 5, 0) 去填充数据，否则会因为越界直接导致程序崩溃。

示例 4：批量填充区间元素

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores = {85, 90, 78, 92, 88};

    // 1. 只把前 3 个元素重置为 60
    std::fill(scores.begin(), scores.begin() + 3, 60);
    for (int s : scores) {
        std::cout << s << ' ';
    }
    std::cout << '\n';

    // 2. 把整个容器的元素全部清零
    std::fill(scores.begin(), scores.end(), 0);
    for (int s : scores) {
        std::cout << s << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

60 60 60 92 88
0 0 0 0 0

分析：

第 1 次调用 std::fill() 时，我们将区间设为 [scores.begin(), scores.begin() + 3)，只有前 3 个元素被改成 60。第 2 次传入整个容器的范围后，所有元素就都被重置成了 0。

如果在刚创建容器时就希望生成 5 个 0，按照 vector 初始化的写法直接定义 std::vector<int> scores(5, 0); 会更简单。而当容器已经存在、中途需要批量重置元素值时，使用 std::fill() 就非常合适了。