泛型算法

直觉：为什么 100 种容器不能有 100 种算法？

你已经学了六种容器——每种都有自己的一套操作接口。如果要在 vector 里找一个值，你会写一个循环；要在 list 里找同样的值，再写一个循环——除了容器名字变了，代码几乎一模一样。难道每学一种新容器，就要把排序、查找、计数这些"工序"重写一遍？

想象工厂流水线有一套标准加工工序：分拣（find）、计数（count）、排序（sort）、填充（fill）——这些工序不关心物料是装在长条槽（vector）里、挂在链条上（list）、还是放在分段托盘（deque）里。它们只需要一根统一的输送带（迭代器）把物料一个接一个送到加工位。输送带只需回答三个问题：这是哪件物料？下一件在哪？送到哪一站结束？

这套"标准工序"就是 C++ 的 100 多个标准算法——你只要学会它们一次，就能作用在所有提供输送带的容器上。没有这套算法库会怎样？ 你会一遍遍写循环——查找、排序、去重——或者更糟，自己手写一个又慢又容易出错的排序，而不用标准库里早已调优好的版本。这一章教你用标准算法代替手写循环，从此「这个操作该选哪个算法」你心里有数。

算法不认识容器——只认迭代器

C++ 标准库提供大量 泛型算法（generic algorithm）——它们被设计成与容器类型解耦。算法不是容器的成员函数，也不直接拥有容器——它们依靠 迭代器范围（iterator range） 与迭代器能力工作。并非每个算法适用于每个容器，例如 sort 需要随机访问，list 必须使用成员 sort。

上图展示了泛型算法的核心设计：三层解耦。算法层只认 begin() 和 end() 两个迭代器——至于这两个迭代器背后是 vector、list 还是 deque——算法毫不知情。这就像工厂的加工工序只认输送带上的物料——物料是从长条槽滑过来的、从链条挂架递来的、还是从分段托盘转接的——工序不关心。

算法在头文件中，不在容器里

#include <algorithm>   // find, sort, count, copy, fill, replace, ...
#include <numeric>     // accumulate, inner_product, partial_sum, ...

大部分算法定义在 <algorithm> 中，数值相关的算法（如 accumulate）在 <numeric> 中。注意——算法是独立函数，不是容器方法——你不需要 v.sort()，而是 std::sort(v.begin(), v.end())。

第一个例子：用 find 代替手写循环

#include <vector>
#include <algorithm>
#include <iostream>
 
int main() {
    std::vector<int> v = {3, 7, 1, 9, 2, 7, 4, 8};
 
    // 手写循环——逻辑可泛化，但这里仍要自行维护边界与步进
    auto it_manual = v.begin();
    while (it_manual != v.end() && *it_manual != 7)
        ++it_manual;
 
    // 泛型算法——1 行，对任何容器都有效
    auto it_algo = std::find(v.begin(), v.end(), 7);
 
    // 两者结果相同
    std::cout << (it_manual == it_algo) << '\n';  // 1（true）
}

find 接受三个参数：前两个定义搜索范围 [begin, end)，第三个是要找的值。它从 begin 开始逐个比对，找到就返回指向该元素的迭代器，找不到就返回 end。

官方 Chapter 10 的完整算法契约

泛型并不意味着“任何算法都能接任何迭代器”。每个算法声明最低能力，调用者提供满足能力的范围、操作和输出位置；算法通常只重排或改写元素，不会替容器插入或删除元素。

迭代器类别与算法参数模式

迭代器类别（iterator categories） 从能力上分为五类：输入迭代器可读且通常只保证单遍；输出迭代器可写且通常只保证单遍；前向迭代器可多遍向前；双向迭代器还能递减；随机访问迭代器支持常数时间跳转、距离与下标。forward_list 只有前向能力，list 是双向能力，vector、deque、array 与 string 提供随机访问。

常见算法参数模式可以据此阅读：

• alg(first, last, otherArgs)：一个输入范围，结果通过返回值或原范围表达。
• alg(first, last, dest, otherArgs)：一个输入范围加一个输出起点；dest 必须有效或是插入迭代器。
• alg(first1, last1, first2, otherArgs)：第二个范围只给起点，调用者必须保证它足够长。
• alg(first1, last1, first2, last2, otherArgs)：两个范围边界都明确；某些重载在较新标准才提供，使用时要核对项目语言版本。

算法把违反能力要求变成编译错误：std::sort(list.begin(), list.end()) 失败，因为双向迭代器没有随机跳转；这不是容器名字被特殊禁止，而是能力契约不满足。

插入、流与反向迭代器

插入迭代器有三种：back_inserter 调用 push_back，front_inserter 调用 push_front，inserter(c, pos) 在指定位置反复调用 insert 并维护插入位置。输出顺序很重要：front_inserter 连续写入会反转元素顺序。

std::list<int> values;
std::copy(src.begin(), src.end(), std::back_inserter(values));
 
std::vector<int> middle = {1, 4};
std::copy(src.begin(), src.end(), std::inserter(middle, middle.begin() + 1));

istream_iterator<T> 把格式化输入适配为输入迭代器，ostream_iterator<T> 把赋值适配为输出；反向迭代器让 rbegin() 到 rend() 以相反方向遍历，但 reverse_iterator::base() 指向的是反向迭代器所指元素的后一个正向位置：

std::istream_iterator<int> in(std::cin), eof;
std::vector<int> numbers(in, eof);
std::copy(numbers.rbegin(), numbers.rend(),
          std::ostream_iterator<int>(std::cout, " "));

lambda、bind 与参数重排

lambda 最适合短小的局部操作；已有函数的参数顺序不符合算法谓词时，std::bind 可以绑定固定实参并重排占位参数：

#include <functional>
using std::placeholders::_1;
 
bool at_least(const std::string &word, std::size_t size) {
    return word.size() >= size;
}
 
auto firstLong = std::find_if(words.begin(), words.end(),
                              std::bind(at_least, _1, 6));

bind 默认按值保存绑定实参；要绑定不可拷贝对象或要求被调函数接收普通引用时，使用 std::ref/std::cref 明确包装。现代代码中 lambda 往往更易读，但理解 bind 有助于读懂 C++11 代码和参数重排。

容器特定算法

容器特定算法（container-specific algorithms） 对链表尤其重要。泛型 remove 只把保留元素移到前面并返回新末尾，不能缩短容器；list::remove 会真正删除节点。list::sort、merge、splice 通过重连节点工作，不要求随机访问，也不复制节点中的值。

std::list<int> a = {3, 1, 2, 2};
std::list<int> b = {6, 4, 5};
a.sort();
a.unique();
b.sort();
a.merge(b); // a: 1 2 3 4 5 6，b 为空

forward_list 提供相应的单链表成员操作以及 splice_after。使用成员版本还是泛型版本，不只是语法选择：前者能改变节点结构和容器大小，后者只能通过迭代器读写现有元素。

Stepper：算法怎么一步步执行？

猜一猜：把下面 Stepper 从第一步逐一切换到最后一步，你看到 find 的执行过程——它每一轮检查哪个元素？找到目标值后立即停止还是继续扫描？

只读算法：只看不改

只读算法（read-only algorithm） 不会修改容器中的元素——它们只是"浏览"一遍。

find——找到第一个匹配元素

#include <vector>
#include <algorithm>
#include <string>
 
int main() {
    std::vector<std::string> words = {"apple", "banana", "cherry", "date"};
 
    auto it = std::find(words.begin(), words.end(), "cherry");
    if (it != words.end())
        std::cout << "找到: " << *it << '\n';  // "找到: cherry"
    else
        std::cout << "未找到\n";
}

find 返回一个迭代器——指向第一个匹配元素。未找到则返回 end() 迭代器（尾后位置，不可解引用）。常见错误：不检查 != end() 就直接解引用——如果是 end()，那是未定义行为。

find_if 是其变体——接受一个谓词（返回 bool 的函数）而不是具体值：

// 找到第一个长度 > 5 的单词
auto it = std::find_if(words.begin(), words.end(),
    [](const std::string &s) { return s.size() > 5; });
// it 指向 "banana"

count——统计出现次数

std::vector<int> v = {1, 2, 3, 2, 1, 2, 4};
int n = std::count(v.begin(), v.end(), 2);  // n = 3

count 遍历整个范围，统计等于目标值的元素个数。count_if 统计满足谓词的元素数。accumulate 是累加版本——它定义在 <numeric> 而非 <algorithm>：

#include <numeric>
std::vector<int> v = {1, 2, 3, 4, 5};
int sum = std::accumulate(v.begin(), v.end(), 0);        // sum = 15
int product = std::accumulate(v.begin(), v.end(), 1,
    [](int a, int b) { return a * b; });                  // product = 120

accumulate 的第三个参数是初始值——它是累加的"起点"，同时也决定了返回值的类型。

equal——比较两个序列是否相等

std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {1, 2, 3, 4, 5};
 
bool same = std::equal(a.begin(), a.end(), b.begin());
// same = true

equal 假设第二个序列至少和第一个一样长——它只接受第二个序列的起始迭代器，不会检查长度是否足够。如果第二个序列比第一个短——未定义行为。

写算法：会改容器内容

写算法（write algorithm） 会改变元素的值——因此你需要确保目标有足够的"位置"来接收结果。

fill——从头到尾写入同一值

fill(begin, end, val) 把区间内的每个元素都设成 val。fill_n(dest, n, val) 从 dest 开始写入 n 个 val：

std::vector<int> v = {1, 2, 3, 4, 5};
std::fill(v.begin(), v.begin() + 3, 0);  // v: {0, 0, 0, 4, 5}
 
std::vector<int> v2;
std::fill_n(std::back_inserter(v2), 5, 42);  // v2: {42, 42, 42, 42, 42}

第二段使用了 插入迭代器（insert iterator）——它把“往迭代器写入”转换为容器插入，解决目标范围尚未创建元素的问题。

copy——整段搬运

copy(src_begin, src_end, dst) 把源区间的元素一个个复制到目标：

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(5);                       // 必须预分配足够空间！
std::copy(src.begin(), src.end(), dst.begin()); // dst: {1, 2, 3, 4, 5}

最常见的错误：dst 没有预分配空间——copy 只是写入到已有位置，不会自动扩容。如果你不确定目标有多大，用 back_inserter：

std::vector<int> dst;  // 空！
std::copy(src.begin(), src.end(), std::back_inserter(dst));  // 正确：自动 push_back

replace——条件替换

std::vector<int> v = {1, 2, 3, 2, 4, 2, 5};
std::replace(v.begin(), v.end(), 2, 99);  // 所有 2 → 99
// v: {1, 99, 3, 99, 4, 99, 5}

replace_copy 是"复制并替换"的版本——源不变，改版写入目标：

std::vector<int> src = {1, 2, 3, 2, 4};
std::vector<int> dst;
std::replace_copy(src.begin(), src.end(),
    std::back_inserter(dst), 2, 99);
// src: {1, 2, 3, 2, 4}  不变
// dst: {1, 99, 3, 99, 4}

transform——逐元素变形

transform 是对每个元素调用函数对象、把结果写入目标的通用武器：

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(src.size());  // 预分配
 
// 每个元素 ×2
std::transform(src.begin(), src.end(), dst.begin(),
    [](int x) { return x * 2; });
// dst: {2, 4, 6, 8, 10}
 
// 原地平方——src 和 dst 可以是同一个容器
std::transform(src.begin(), src.end(), src.begin(),
    [](int x) { return x * x; });
// src: {1, 4, 9, 16, 25}

transform 接受三个必需参数：源范围 [begin, end) + 目标起始位置 + 一个可调用对象（函数、函数指针、函数对象、lambda）。transform 的强大在于——你自己决定"怎么变"，它负责把"变"施加到每个元素。

排序定制：sort、unique、stable_sort

sort——随机访问范围排序

sort(begin, end) 对区间进行升序排序——默认用 < 比较。要求迭代器是 随机访问迭代器（RandomAccess Iterator）——这意味着 vector/deque/array/string 可用，list 不可用（要用 list::sort）。标准规定复杂度和排序结果，不规定必须使用快排或 introsort；具体实现可自由选择满足要求的算法。

std::vector<int> v = {5, 2, 8, 1, 9, 3, 6, 4, 7};
std::sort(v.begin(), v.end());
// v: {1, 2, 3, 4, 5, 6, 7, 8, 9}

下面 Stepper 用快速排序的一次可能执行路径解释“比较、分区、递归”如何产生有序结果。它是教学模型，不是对某个标准库 std::sort 内部步骤或 pivot 选择的承诺：

自定义排序规则

sort 默认按升序排。要降序怎么办？传入第三个参数——一个比较函数：

std::vector<int> v = {5, 2, 8, 1, 9};
 
// 降序排序
std::sort(v.begin(), v.end(),
    [](int a, int b) { return a > b; });
// v: {9, 8, 5, 2, 1}

这个比较函数被称为 谓词（predicate）——sort 在比较两个元素时会调用它。返回 true 表示 a 应该排在 b 前面。

更实际的例子——对结构体按某个字段排序：

struct Student {
    std::string name;
    int score;
};
 
std::vector<Student> students = {
    {"Alice", 92}, {"Bob", 85}, {"Charlie", 97}
};
 
// 按成绩降序排
std::sort(students.begin(), students.end(),
    [](const Student &a, const Student &b) {
        return a.score > b.score;
    });
// Charlie(97) > Alice(92) > Bob(85)

unique——去重

unique 把重复的相邻元素"挤"到末尾——注意它只处理相邻重复，不会真正删除元素：

std::vector<int> v = {1, 2, 2, 3, 3, 3, 4, 5, 5};
auto new_end = std::unique(v.begin(), v.end());
// [v.begin(), new_end) 是 {1, 2, 3, 4, 5}
// [new_end, v.end()) 中的元素仍有效，但值未指定
 
v.erase(new_end, v.end());  // 删除新逻辑末尾之后的元素
// v: {1, 2, 3, 4, 5}

稳定排序（stable_sort） 的关键语义是等价元素保持原序，不能把它和 sort 的全部差异简化为函数名不同：

// 假设有多个 Student score=90——stable_sort 保持他们的原始顺序
std::stable_sort(students.begin(), students.end(),
    [](const Student &a, const Student &b) {
        return a.score > b.score;
    });

lambda 表达式：就地生成一个函数

你已经见过几次了——[](int x) { return x > 0; } 这种写在代码中间的"函数"。这是 lambda 表达式（lambda expression）——C++11 引入的语法糖，让你在需要函数对象的地方当场写一个"匿名函数"。

lambda 的四个组成部分：

• ① 捕获列表 [capture]：告诉 lambda 它如何访问外部变量。[=] 按值捕获（复制一份）、[&] 按引用捕获（共享原变量）、[x, &y] 混合——x 按值、y 按引用
• ② 参数列表 (params)：和普通函数一样的参数——调用者传进来的东西
• ③ 返回类型 -> ret：大多数情况可省略——编译器能从函数体推导
• ④ 函数体 { body }：lambda 的执行逻辑

int threshold = 10;
std::vector<int> v = {5, 15, 8, 20, 3};
 
// [=] 按值捕获 threshold——lambda 内部可以读取它
auto it = std::find_if(v.begin(), v.end(),
    [=](int x) { return x > threshold; });   // *it = 15
 
// [&] 按引用捕获——lambda 内部可以修改外部变量
int count = 0;
std::for_each(v.begin(), v.end(),
    [&](int x) { if (x > threshold) ++count; });
// count = 2

容易踩的坑

小结

• 泛型算法与容器解耦——通过迭代器范围 [begin, end) 接收数据；只要迭代器能力满足算法要求，同一算法就能复用。find/count 等只读算法不改数据，fill/copy/transform 等写算法需要有效目标
• sort 对 RandomAccess 迭代器区间 O(n log n) 排序——接受可选的第三个参数（谓词）自定义排序规则；unique 只压缩重复不删除——配合 erase 完成真正的去重操作
• lambda 是就地定义的匿名函数——[capture](params) -> ret { body }；[=] 按值捕获外部变量（副本）、[&] 按引用捕获（共享）；lambda 作为谓词传入算法——大幅减少独立函数定义
• 写算法不自动扩容——copy/transform 写入时目标容器空间必须足够，否则用 back_inserter 自动 push_back；fill_n 同理——n 个位置必须有效
• 手写循环能被标准算法替换的场景——查找用 find/find_if、计数用 count/count_if、删除元素用 remove_if + erase

#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {3, -1, 2, -3, 5, -2};
    for (auto it = v.begin(); it != v.end(); ++it) {
        if (*it < 0) {
            v.erase(it);    // Bug 1
        }                   // Bug 2
    }
    for (int x : v) std::cout << x << ' ';  // 应该输出 3 2 5
}

#include <vector>
#include <algorithm>
#include <iostream>
int main() {
    std::vector<int> v = {3, -1, 2, -3, 5, -2};
    auto newEnd = std::remove_if(v.begin(), v.end(),
        [](int x) { return x < 0; });
    v.erase(newEnd, v.end());
    for (int x : v) std::cout << x << ' ';  // 3 2 5
}

struct Student {
    std::string name;
    int score;
};
std::vector<Student> top_n(std::vector<Student> students, int n);

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
 
struct Student {
    std::string name;
    int score;
};
 
std::vector<Student> top_n(std::vector<Student> students, int n) {
    // 降序排列——成绩高的在前面
    std::sort(students.begin(), students.end(),
        [](const Student &a, const Student &b) {
            return a.score > b.score;  // 降序：a > b 时 a 排 b 前
        });
 
    // 把 n 限制在合法半开区间 [0, size]
    if (n <= 0)
        return {};
    if (n > static_cast<int>(students.size()))
        n = static_cast<int>(students.size());
 
    return std::vector<Student>(students.begin(), students.begin() + n);
}
 
int main() {
    std::vector<Student> all = {
        {"Alice", 85}, {"Bob", 92}, {"Charlie", 78},
        {"Diana", 95}, {"Eve", 88}
    };
    auto top = top_n(all, 3);
    for (const auto &s : top)
        std::cout << s.name << ": " << s.score << '\n';
    // Diana: 95 / Bob: 92 / Eve: 88
}

名词解释