Chapter 25: Algorithm Design Principles

STL algorithm 的核心目标，是把“对一段元素执行某种操作”从具体容器里抽出来。读完本章后，读者应能看到一个算法调用，立刻定位它处理哪段区间、读取还是写入元素、依赖什么 iterator 能力、由哪个 predicate 或 projection 注入用户规则，以及复杂度承诺按什么数量计算。

本章用一组任务调度数据作为贯穿材料。代码里有任务对象、任务区间、查询、排序和提取字段几个操作。后续每一节都会回到这段代码，用同一组问题拆解算法设计原则。

#include <algorithm>
#include <functional>
#include <iterator>
#include <ranges>
#include <vector>

struct Job {
    int id;
    int priority;
    bool ready;
};

std::vector<Job> jobs = {
    {1, 40, false},
    {2, 90, true},
    {3, 70, true},
    {4, 20, false},
};

auto first_ready = std::find_if(
    jobs.begin(),
    jobs.end(),
    [](const Job& job) { return job.ready; }
);

std::ranges::sort(jobs, std::greater<>{}, &Job::priority);

std::vector<int> ready_ids;
std::ranges::transform(
    jobs | std::views::filter([](const Job& job) { return job.ready; }),
    std::back_inserter(ready_ids),
    &Job::id
);

这段代码把 STL algorithm 的五个问题集中放在一起：std::find_if 消费半开区间，std::ranges::sort 改变元素顺序，std::views::filter 延迟筛选输入，std::ranges::transform 写入输出 iterator，&Job::priority 和 &Job::id 把对象字段接入算法。算法设计原则的阅读顺序就是：先确定区间，再确定所有权边界，再确定 iterator 能力与可调用对象，再确定复杂度和修改边界，最后把算法放入功能族中选择。

25.1 iterator range 与 half-open contract

STL algorithm 的输入边界通常写成 [first, last)。这个符号表示从 first 指向的元素开始，一直推进到 last 代表的边界为止。first 可以解引用，last 是停止位置，只参与比较和距离计算。空区间用 first == last 表示，单元素区间用 first 指向元素、++first == last 表示。

这个约定把算法循环压缩成一个稳定形状。std::find_if 的简化实现可以写成下面这样：

template<class InputIt, class Pred>
InputIt mini_find_if(InputIt first, InputIt last, Pred pred) {
    for (; first != last; ++first) {
        if (pred(*first)) {
            return first;
        }
    }
    return last;
}

这段代码展示了半开区间的三个动作。循环先检查 first != last，然后解引用 *first，最后推进 ++first。找到元素时返回当前位置，扫描到边界时返回 last。调用方收到返回值后，可以用 it == last 判断是否命中；同一个 last 同时承担输入边界和未命中结果的角色。

贯穿材料中的 std::find_if(jobs.begin(), jobs.end(), pred) 把整个 jobs 交给算法。算法收到的是两个 iterator，循环只围绕位置对象推进。这个设计使同一个 find_if 可以处理 std::vector、std::list、原生数组区间以及用户自定义 range，只要传入位置对象满足算法的 iterator 要求。

半开区间还让子区间表达保持一致。若只想检查排好序后的前三个任务，可以传入 [jobs.begin(), jobs.begin() + 3)；若要处理从第二个元素到结尾的范围，可以传入 [jobs.begin() + 1, jobs.end())。区间边界始终用起点和终点表达，算法本身无需知道“长度字段”或“容器对象”。

对源码阅读来说，看到算法循环里的 first != last、++first、*first，应先把这三个操作映射回 iterator contract。first != last 负责边界，*first 负责访问当前元素，++first 负责前进。后续的比较、谓词、赋值、交换和移动，都附着在这个基本循环之上。

25.2 内存边界与容器类型隔离

STL algorithm 把元素位置作为输入输出接口，容器负责存储结构、容量增长、元素生命周期和迭代器失效规则。这个分工决定了算法可以跨容器复用，也决定了调用方必须为写入位置提供合法目标。

贯穿材料中的 std::ranges::sort(jobs, std::greater<>{}, &Job::priority) 会重排 jobs 内部的 Job 元素。算法执行比较和交换，std::vector 继续拥有那块连续存储。元素的构造、析构、容量和地址有效性仍由容器规则决定。sort 的职责是把 [begin, end) 内的元素改成满足排序关系的顺序。

std::ranges::transform 的边界更加明显。它从输入 range 读取 Job，对每个元素应用 &Job::id，再把结果写到 ready_ids 的输出 iterator。std::back_inserter(ready_ids) 把一次赋值转换成 ready_ids.push_back(value)，因此容量增长、内存分配和新元素构造都由 ready_ids 完成。

std::vector<int> ids;

std::ranges::transform(
    jobs,
    std::back_inserter(ids),
    &Job::id
);

这段代码里，算法只做“读取一个 Job、生成一个 int、写一次输出”的循环。ids 是否重新分配、旧 iterator 是否失效、分配失败时已经写入多少元素，都属于容器和异常传播边界。算法接口只承诺它会按规则访问输入并写入输出 iterator。

若输出 iterator 采用普通目标位置，调用方需要提前准备目标区间。例如把 jobs 的 id 写进已经分配好大小的 std::vector<int>：

std::vector<int> ids(jobs.size());

std::ranges::transform(
    jobs,
    ids.begin(),
    &Job::id
);

这里的 ids.begin() 是第一个可写位置，算法会连续写入 jobs.size() 次。目标区间大小由调用方保证，算法接口本身只拿到一个起始输出位置。这个例子说明了内存边界的检查顺序：先数清输入会产生多少输出，再确认输出 iterator 背后有可写能力和足够目标空间，最后看写入是否通过容器插入接口完成。

修改型算法与容器成员函数的责任也要分清。以 std::remove_if 为例，它会把保留元素向前移动，并返回新的逻辑尾端；容器的实际长度仍由调用方用成员函数调整。

auto new_last = std::remove_if(
    jobs.begin(),
    jobs.end(),
    [](const Job& job) { return job.priority < 50; }
);

jobs.erase(new_last, jobs.end());

remove_if 管理的是区间内元素值的重排，erase 管理的是容器长度、元素析构和存储状态。读 STL algorithm 源码时，应把“值移动”和“容器结构改变”分成两个层级。算法通常操作 iterator 可见的值，容器成员函数操作节点、容量、长度和生命周期。

下面的图把这一层责任关系压缩到一个路径中。它的边界是普通 STL algorithm 调用，未展开容器内部 allocator 细节。

图中的关键点是责任方向。调用方选择区间，算法执行循环，可调用对象提供比较、筛选或变换规则，容器保持存储所有权。这个分工让 STL algorithm 可以保持泛型，也让调用方需要在调用前完成区间、输出、失效和生命周期检查。

25.3 iterator category、predicate 与 projection

算法的泛型能力来自三类约束：iterator category 决定算法可使用的位置操作，predicate 或 operation 决定用户注入的判断或变换逻辑，projection 在 C++20 ranges algorithm 中负责先从元素提取参与比较或判断的视图值。

iterator category 是算法读取 iterator 能力的入口。std::find_if 只需要读取、比较边界和向前推进，因此输入 iterator 足够；std::reverse 需要从两端向中间推进，因此要求 bidirectional iterator；std::sort 需要随机跳转和交换，因此要求 random access iterator。这个分层让算法把“能处理什么容器”绑定到位置能力上。

算法形态	典型操作	最小 iterator 能力	工程含义
线性查询	`find_if`、`count_if`	input / forward	只沿一个方向扫描
双端重排	`reverse`	bidirectional	需要从左右两端推进
随机访问排序	`sort`、heap algorithm	random access	需要下标式跳转和局部交换
输出生成	`copy`、`transform`	output iterator	需要目标位置可写

predicate 是返回可用于布尔判断结果的可调用对象。std::find_if 的 predicate 接收当前元素，返回当前元素是否命中条件。贯穿材料中的 lambda 是一个 predicate：

auto first_ready = std::find_if(
    jobs.begin(),
    jobs.end(),
    [](const Job& job) { return job.ready; }
);

这里的算法循环提供 Job，lambda 决定业务条件。算法本身没有“任务是否可运行”的知识。若要换成“优先级至少 80”，只需要替换 predicate，算法循环形状保持不变。

auto first_high_priority = std::find_if(
    jobs.begin(),
    jobs.end(),
    [](const Job& job) { return job.priority >= 80; }
);

projection 是 C++20 ranges algorithm 的一个入口，它把元素先映射成某个字段或计算结果，再交给比较器或 predicate。贯穿材料中的排序调用如下：

std::ranges::sort(jobs, std::greater<>{}, &Job::priority);

这个调用的可读含义是：对 jobs 排序，比较方式是从大到小，被比较的键来自 Job::priority。算法看到完整 Job 对象，projection 先提取 priority，比较器再比较两个 int。这样写比在 comparator 内部手写 lhs.priority > rhs.priority 更容易暴露“排序键”这个事实。

同一个 projection 思路也可用于筛选和复制。下面代码把高优先级任务复制到另一个容器，predicate 接收的是 projection 后的 priority：

std::vector<Job> urgent;

std::ranges::copy_if(
    jobs,
    std::back_inserter(urgent),
    [](int priority) { return priority >= 80; },
    &Job::priority
);

阅读 ranges algorithm 调用时，可以按四步拆解：输入 range 是谁，输出 iterator 是否存在，projection 产生什么值，predicate 或 comparator 对 projection 后的值做什么判断。传统 algorithm 通常把 projection 写入 lambda 或 comparator 内部；ranges algorithm 把 projection 作为独立参数，错误信息和代码意图更容易定位。

源码层面，predicate、projection 和 operation 都属于可调用对象。算法实现可能复制这些对象，并在循环中反复调用。若可调用对象带有状态，状态复制语义会影响结果观察方式。工程中把算法可调用对象写成轻量、可复制、无隐藏副作用的对象，能降低并行算法、调试和重试路径的复杂度。

25.4 复杂度承诺与修改边界

STL algorithm 的复杂度承诺通常按区间长度和用户可调用对象调用次数表达。读取这类承诺时，先把输入规模写成 N = last - first 或线性距离，再看规范承诺的是比较次数、predicate 次数、赋值次数、交换次数、移动次数，还是某种组合。

mini_find_if 的循环最多检查每个元素一次，因此最多调用 pred N 次。若第一个元素命中，只调用一次；若没有命中，调用 N 次并返回 last。这个复杂度来自半开区间线性扫描，与容器类型关系很小。std::list 和 std::vector 都是线性扫描，只是内存局部性和 iterator 推进成本不同。

修改边界要和复杂度一起读。std::ranges::sort 会改变元素顺序，复杂度通常围绕比较次数和元素交换或移动成本讨论；std::find_if 只读取元素并返回位置；std::ranges::transform 读取输入并写入输出；std::remove_if 在输入区间内部移动保留元素并返回逻辑尾端。算法名字、参数形式和规范中的 Effects / Complexity 共同说明了这些边界。

下面这段代码包含三个不同修改层级：

auto ready = std::ranges::find_if(
    jobs,
    [](const Job& job) { return job.ready; }
);

std::ranges::sort(jobs, std::greater<>{}, &Job::priority);

std::ranges::transform(
    jobs,
    std::back_inserter(ready_ids),
    &Job::id
);

find_if 的结果是一个位置，不改元素值；sort 会在原区间内部重排元素；transform 会向另一个输出位置写入结果。三者都接收 range 或 iterator，但修改边界完全不同。工程判断时，应把“是否读取”“是否改输入元素”“是否改顺序”“是否写输出”“是否改变容器结构”逐项确认。

复杂度承诺还包含用户代码成本。若 predicate 很重，find_if 的主要成本可能来自 predicate；若 comparator 访问外部资源，sort 的成本会被比较器放大；若 projection 计算临时字符串，排序比较会反复触发额外分配。标准库能承诺调用次数数量级，用户可调用对象内部成本由调用者控制。

异常边界也应放在修改边界之后检查。算法调用 predicate、projection、comparator、assignment、swap 或 move 时，这些操作可能抛出异常。已经完成的写入或重排是否可恢复，取决于具体算法、元素类型、容器操作和异常发生位置。本章只建立阅读顺序：先看算法是否写入或重排，再看写入依赖哪些用户操作，最后看容器成员函数是否参与长度和生命周期提交。

这个顺序可以沉淀成一个可复用 checklist：确定输入规模，定位算法会调用哪些用户对象，读取复杂度中的计数对象，确认是否写输入或输出，确认容器结构是否由成员函数改变，最后把异常路径和 iterator 失效放回容器规则中判断。

25.5 STL 算法分类

算法分类的价值在于缩小选择范围。看到一个问题时，先判断目标是查询、修改、排序、集合、堆还是数值归约，再在该族内部选择具体算法。这样读源码和查接口时，会围绕同一组设计问题展开，而非在函数名列表里逐个试用。

查询类算法回答“区间里有什么”。find_if 返回第一个满足条件的位置，count_if 返回满足条件的数量，all_of、any_of、none_of 返回布尔判断，equal 和 mismatch 比较两个区间。它们的共同设计点是读取输入、短路或线性遍历、返回位置或布尔结果。

修改类算法回答“如何把元素写到新状态”。copy、move、transform 面向输出区间，fill 和 generate 产生新值，remove_if、replace、reverse、rotate 改变值或顺序。它们的共同检查点是目标可写性、重叠区间、元素赋值或移动成本，以及容器长度是否需要由成员函数提交。

排序及有序区间算法回答“如何利用顺序”。sort、stable_sort、partial_sort、nth_element 改变或选择顺序；binary_search、lower_bound、upper_bound、equal_range 在有序前提下查找；is_sorted 和 is_sorted_until 检查前提。它们的共同检查点是比较器关系、随机访问能力、稳定性需求和输入是否已满足有序或分区条件。

集合算法回答“两个有序区间如何合并或比较”。set_union、set_intersection、set_difference、set_symmetric_difference 和 includes 都以有序输入为前提。它们通常用双指针同步推进，输出一个新序列或布尔结果。调用前应确认两边使用同一比较器语义，输出区间有足够空间或使用插入 iterator。

堆算法回答“如何在连续区间中维护优先级访问”。make_heap 把普通区间调整成堆，push_heap 假设新元素已经追加到尾部并上浮，pop_heap 把堆顶交换到尾部并在剩余区间恢复堆序，sort_heap 反复弹出堆顶形成排序区间。它们的共同前提是 random access iterator 和堆不变量。

数值算法回答“如何对序列做累计、差分或归约”。accumulate、reduce、inner_product、partial_sum、inclusive_scan、exclusive_scan、adjacent_difference 都围绕值的组合展开。它们的核心检查点是初始值类型、运算结合性、副作用、溢出和浮点误差。并行相关算法还会把执行顺序和可结合性问题推到调用方。

贯穿材料可以落入多个算法族。查找第一个可运行任务属于查询，按优先级排序属于排序，从任务中提取 id 属于修改或变换，按优先级取 Top-K 可以转向堆或局部排序。选择算法时，先用“目标族”缩小范围，再用 iterator 能力、写入边界、稳定性、复杂度和容器结构选具体函数。

最小自检任务

阅读下面代码，判断三个算法调用分别处理哪段区间、是否修改输入元素、需要什么关键 iterator 或输出能力，并说明 remove_if 之后为什么还需要 erase。

#include <algorithm>
#include <iterator>
#include <ranges>
#include <vector>

struct Job {
    int id;
    int priority;
    bool ready;
};

std::vector<Job> jobs = {
    {1, 40, false},
    {2, 90, true},
    {3, 70, true},
    {4, 20, false},
};

auto first_ready = std::ranges::find_if(
    jobs,
    [](const Job& job) { return job.ready; }
);

auto new_last = std::remove_if(
    jobs.begin(),
    jobs.end(),
    [](const Job& job) { return job.priority < 50; }
);

std::vector<int> ids;
std::ranges::transform(
    jobs.begin(),
    new_last,
    std::back_inserter(ids),
    &Job::id
);

jobs.erase(new_last, jobs.end());

答案要点

std::ranges::find_if 处理的是整个 jobs range，语义等价于 [jobs.begin(), jobs.end())。它沿区间读取元素并调用 predicate，返回第一个 ready 为真的位置；若没有命中，返回 jobs.end()。它需要输入方向的读取和推进能力，调用本身不改元素值。

std::remove_if 处理的是 [jobs.begin(), jobs.end())。它会把 priority >= 50 的元素向前移动，并返回新的逻辑尾端 new_last。此时 jobs.size() 仍保持原值，[new_last, jobs.end()) 属于等待清理的尾部区间。容器长度、尾部元素析构和最终结构提交由 jobs.erase(new_last, jobs.end()) 完成。

std::ranges::transform 处理的是 [jobs.begin(), new_last)，也就是 remove_if 之后的有效逻辑区间。它读取每个 Job，通过 &Job::id 取出 id，再通过 std::back_inserter(ids) 追加到 ids。输入侧需要可读取和推进，输出侧需要可写；back_inserter 把写入动作转成 ids.push_back，容量增长和新元素构造由 ids 管理。

这段代码的判断顺序是：先把每个算法的 range 边界写出来，再区分读取、重排和输出写入，随后确认输出 iterator 是否由容器插入适配器提供，最后把容器长度改变交给成员函数 erase。这个顺序能复用到后续 copy_if、sort、集合算法和堆算法的调用判断。

本章知识点总结

半开区间：[first, last) 用起点和边界定义算法输入，last 同时可作为未命中返回位置。
循环形状：典型算法先比较边界，再解引用当前位置，最后推进 iterator。
容器分工：算法操作 iterator 可见的元素，容器负责存储、容量、生命周期和失效规则。
输出边界：写入算法需要合法输出 iterator，插入型 iterator 会把写入转成容器插入动作。
逻辑尾端：remove_if 返回保留元素后的新边界，容器缩短由 erase 提交。
能力分层：iterator category 决定算法能使用线性推进、双向推进还是随机跳转。
用户规则：predicate、operation 和 comparator 把业务判断、变换和排序关系注入算法循环。
投影入口：C++20 ranges algorithm 的 projection 可先提取字段，再交给 predicate 或 comparator。
复杂度对象：复杂度要按区间长度、predicate 次数、比较次数、赋值次数、交换次数或移动次数读取。
修改边界：调用前应区分只读、改输入元素、改元素顺序、写输出和改变容器结构。
异常位置：异常可能来自用户可调用对象、赋值、交换、移动或容器插入，分析时要回到修改边界。
分类选择：先判断问题属于查询、修改、排序、集合、堆或数值归约，再选择具体算法。
有序前提：二分和集合算法依赖有序或分区条件，比较器语义需要在输入和算法中保持一致。
判断顺序：阅读算法调用时，按区间、所有权、iterator 能力、可调用对象、复杂度和修改边界依次检查。

25.1 iterator range 与 half-open contract​

25.2 内存边界与容器类型隔离​

25.3 iterator category、predicate 与 projection​

25.4 复杂度承诺与修改边界​

25.5 STL 算法分类​

最小自检任务​

答案要点​

本章知识点总结​