C++ STL 算法：实用指南与示例

不用自己写的循环

上一篇中你看到，每个容器都会提供迭代器，也就是带有 begin() 和 end() 的轻量游标。标准算法之所以存在，全靠这层抽象。每次想要查找、计数或转换数据时，不必再写一个原始的 for 循环，而是调用 <algorithm> 中一个有名字的函数，把一个区间交给它。

区间就是两个迭代器：从哪里开始，以及停止位置的下一个位置。因为所有算法都使用同一套迭代器语言，同一个 find 可以用于 vector、string 或普通数组。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42};

    // Is 16 in the range [begin, end)?
    auto it = find(v.begin(), v.end(), 16);

    if (it != v.end())
        cout << "found " << *it << " at index " << (it - v.begin()) << "\n";
    else
        cout << "not found\n";
    return 0;
}

要牢记的模式：查找类算法用返回 end() 迭代器来表示“没找到”。在解引用结果之前，一定要先和 end() 比较，解引用 end() 属于未定义行为。

用谓词计数和判断

许多算法都接受一个谓词，即一个对每个元素返回 bool 的函数（通常是 lambda）。count_if 统计匹配的个数；all_of、any_of 和 none_of 回答关于整个区间的是非问题。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {42, 88, 17, 95, 63, 71};

    int passed = count_if(scores.begin(), scores.end(),
                          [](int s) { return s >= 60; });

    bool allPositive = all_of(scores.begin(), scores.end(),
                              [](int s) { return s > 0; });

    bool anyPerfect = any_of(scores.begin(), scores.end(),
                             [](int s) { return s == 100; });

    cout << passed << " passed\n";          // 4 passed
    cout << "all positive? " << allPositive << "\n";  // 1
    cout << "any perfect? " << anyPerfect << "\n";    // 0
    return 0;
}

std::count（没有 _if）是更简单的版本，它统计的是某个确切的值，而不是某个条件。一旦你的判断是“符合某条规则的任何元素”，而不是“这个特定的值”，就该用带谓词的版本。

转换和归约区间

两个主力算法覆盖了大部分数据处理：std::transform 把每个元素通过一个函数进行映射，std::accumulate（来自 <numeric>，而不是 <algorithm>）把一个区间归约成单个值。

transform 通过一个输出迭代器写入结果。一个常见又危险的错误是让输出指向一个空的 vector：算法假定空间已经存在，于是越过末尾写入。要么先设置好目标容器的大小，要么使用 back_inserter，让每个结果都通过 push_back 添加进去。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> squares;   // empty - no room yet

    // back_inserter grows `squares` as results arrive
    transform(nums.begin(), nums.end(), back_inserter(squares),
              [](int n) { return n * n; });

    for (int s : squares) cout << s << " ";  // 1 4 9 16
    cout << "\n";
    return 0;
}

accumulate 从一个初始值开始，从左到右合并各个元素。初始值的类型很重要：传入 0（一个 int），求和就会以 int 进行，根据元素的数据类型，可能发生溢出或截断。

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {9.99, 4.50, 19.95};

    // Start with 0.0 (double) so the running total stays a double.
    double total = accumulate(prices.begin(), prices.end(), 0.0);

    cout << "total: " << total << "\n";  // total: 34.44
    return 0;
}

如果你写成 accumulate(prices.begin(), prices.end(), 0)，用 int 作初始值，每次加法都会以 int 进行，小数部分就没了。初始值的类型会悄悄决定结果的类型。

erase-remove 惯用法

下面这个陷阱几乎让所有人都吃惊。std::remove 不会从容器中删除任何东西。算法手里只有迭代器，所以无法改变容器的大小，它们甚至根本不知道容器的存在。remove 实际做的是把所有要保留的元素移到前面，让尾部处于未指定的状态，并返回一个指向新的逻辑末尾的迭代器。

// remove alone leaves the size unchanged - this is the bug:
remove(v.begin(), v.end(), 0);  // returns an iterator you ignored
// v still has its original size; the tail is garbage

要真正删除这些元素，需要把 remove 和容器的 erase 配合使用，这就是它被称为 erase-remove 惯用法的原因：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 0, 7, 0, 1, 0, 9};

    // 1. remove shuffles non-zeros forward, returns new end
    // 2. erase chops off everything from there to the real end
    v.erase(remove(v.begin(), v.end(), 0), v.end());

    for (int n : v) cout << n << " ";  // 3 7 1 9
    cout << "\n";
    return 0;
}

如果条件是谓词而不是确切的值，就用 remove_if。在 C++20 中，可以直接用自由函数 std::erase / std::erase_if 省掉这一套，它们会替你完成两个步骤：erase(v, 0);。

迭代器失效的风险

因为算法返回的是迭代器，这些迭代器同样受上一篇讲过的失效规则约束。保存了一个迭代器之后再修改容器，比如触发重新分配的 push_back，或者一次 erase，都可能让保存的迭代器变成悬空的，而使用它属于未定义行为。

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // may reallocate v's storage
cout << *it;       // BUG: `it` may now point at freed memory

安全的习惯是：拿到算法返回的迭代器后立即使用，不要等到任何可能改变容器大小或引发重新分配的操作之后。如果需要根据结果修改容器，就改为保存一个下标（it - v.begin()），因为下标在重新分配后依然有效。

下一篇：排序

你已经见过查找、计数、转换和归约，但有一个算法重要到值得单独写一篇。std::sort 会原地重新排列一个区间，而一旦数据有序，一整类更快的、只适用于有序数据的算法（binary_search、lower_bound、equal_range）就能派上用场。接下来我们深入讲解排序：如何提供自定义比较器，sort 和 stable_sort 的区别，以及比较函数必须遵守哪些规则才能避免未定义行为。