Skip to main content

Chapter 25: Algorithm Design Principles

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

STL algorithm 将“对一段元素执行何种操作”与“元素如何存储在容器中”彻底解耦。排查或设计任何算法调用,本质上只需锁定五个核心约束:半开区间范围、内存与容器边界、iterator 能力、predicate/projection 注入规则,以及复杂度与修改边界。

全章共用代码样本(下文各节持续拆解)

贯穿材料核心代码

本章以任务调度数据 jobs 作为贯穿材料,在同一段代码里集中展示查询、按字段排序和过滤变换:

#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
);

这段样本依次覆盖了四类核心交互:std::find_if 消费半开区间,std::ranges::sort 按 &Job::priority 原地重排,std::views::filter 延迟筛选输入,std::ranges::transform 借由 std::back_inserter(ready_ids) 将 &Job::id 写入目标容器。

25.1 iterator range 与 half-open contract​

STL algorithm 将输入抽象为半开区间 [first, last):first 指向首个有效元素(可解引用),last 是停止边界(只参与比较和距离计算,不可解引用)。空区间满足 first == last,单元素区间满足 first != last 且 ++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;
}

算法收到的是两个 iterator 而非容器或长度字段,因此 std::find_if(jobs.begin(), jobs.end(), pred) 可直接复用于 std::vector、std::list、原生数组区间及自定义 range。子区间表达同样一致:检查前三个任务传入 [jobs.begin(), jobs.begin() + 3),处理第二个元素到结尾传入 [jobs.begin() + 1, jobs.end())。

关键事实

算法主循环围绕 first != last(边界检查)、*first(访问当前元素)和 ++first(推进位置)展开;last 同时承担输入边界与未命中返回值角色,调用方可用 it == last 判空,且严禁解引用 last 或未命中返回的 iterator。

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

STL algorithm 只通过 iterator 读写或重排元素值,容器继续独占存储结构、容量增长、元素生命周期和迭代器失效规则。

在贯穿材料中,std::ranges::sort(jobs, std::greater<>{}, &Job::priority) 只负责在 [begin, end) 内比较并交换元素,std::vector 仍持有原连续内存块及元素生命周期控制权。当算法需要产生新输出时,则完全取决于调用方传入何种输出 iterator:

插入适配器写入:std::back_inserter(ids) 将每次赋值转换为 ids.push_back(value),容量扩张、新元素构造以及扩容引发的旧 iterator 失效与异常传播均归属于容器边界。

std::vector<int> ids;

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

预分配区间覆写:传入普通起始位置 ids.begin() 时,算法直接连续写入 jobs.size() 次,目标区间是否足够完全由调用方保证。

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

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

值重排与结构提交分离:std::remove_if 仅在区间内前移保留元素并返回新逻辑尾端 new_last,容器实际长度缩短与尾部元素析构仍须由成员函数 erase 提交。

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

jobs.erase(new_last, jobs.end());
写入或修改模式算法职责容器与调用方职责关键边界风险
原地重排(std::ranges::sort)比较并交换或移动元素位置保持存储与元素生命周期依赖元素可移动或可交换
插入写入(std::back_inserter)逐元素赋值到输出 iterator自动 push_back、扩容与构造扩容触发旧 iterator 失效
覆写写入(ids.begin())从起点连续覆盖写 N 次预先保证目标区间长度足够空间不足导致越界写入
逻辑删除(std::remove_if)前移保留元素并返回 new_last调用 erase 缩容并析构尾部漏调 erase 导致残留无效元素

边界与误区

注意

普通输出 iterator 本身不携带终点信息,调用写入算法前必须先确认输出规模与可写容量,或改用插入适配器;对于 std::remove_if 等重排算法,算法结束后 jobs.size() 不变,[new_last, jobs.end()) 只是待清理的尾部区间,必须交由容器成员函数 erase 收尾。

25.3 iterator category、predicate 与 projection​

STL algorithm 的泛型能力由三类约束协同定义:iterator category 限定算法可用的位置操作,predicate 或 operation 注入业务判断与变换规则,C++20 projection 则先从元素提取投影值再交给比较器或谓词。

算法通过最小 iterator 能力约束可接入的容器,而非直接绑定具体容器类型:

算法形态典型操作最小 iterator 能力工程含义
线性查询find_if、count_ifinput / forward只沿单方向顺序扫描
双端重排reversebidirectional需从左右两端向中间推进
随机访问排序sort、heap algorithmrandom access需下标式跳转与交换(如 std::list 不适用 std::sort)
输出生成copy、transformoutput iterator要求目标位置可写

predicate 注入判断条件:predicate 是返回布尔值的可调用对象。贯穿材料中的 first_ready 用 lambda 检查 job.ready;若业务条件改为“优先级至少 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 将字段提取抽成独立参数。贯穿材料中 std::ranges::sort(jobs, std::greater<>{}, &Job::priority) 先用 &Job::priority 投影出 int,再交给 std::greater<>{} 比较,比在 comparator 内部手写 lhs.priority > rhs.priority 更直观。同一机制也可直接用于 std::ranges::copy_if:

std::vector<Job> urgent;

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

传统算法常把字段提取混写在 lambda 或 comparator 内部,而 ranges algorithm 将 projection 独立出来,编译报错和代码意图都更易定位。

排查顺序

阅读任意 C++20 std::ranges 算法调用可按四步拆解:① 确认输入 range 及其 iterator 能力;② 确认是否存在输出 iterator 与目标容量;③ 确认 projection 提取了什么字段或值;④ 确认 predicate 或 comparator 对投影结果执行何种判断。

边界与误区

注意

算法实现可能按值复制 predicate、projection 和 operation 并在循环中反复调用。若可调用对象持有可变状态或隐式副作用,状态复制语义会直接污染观察结果;工程上应保持算法可调用对象轻量、可复制且无隐藏副作用,以适配调试、重试与并行算法。

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

STL algorithm 的复杂度承诺按输入规模 N = last - first(或线性距离)与具体操作次数表达,阅读规范的 Effects 与 Complexity 时需先分清计数量是比较次数、predicate 调用次数、赋值次数、交换次数还是移动次数。

以 mini_find_if 为例:命中首元素只需 1 次 pred 调用,全未命中则调用 N 次并返回 last。这种线性复杂度由半开区间扫描结构决定,不随容器类型改变;std::vector 与 std::list 虽同为线性扫描,实际耗时仍受内存局部性与 iterator 推进成本影响。

工程上需将复杂度与修改层级放在一起核对,下面三行调用虽同为 jobs 上的算法,修改边界截然不同:

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
);
代表算法主要复杂度计数量是否改输入元素或顺序是否写输出是否改容器长度
std::find_if / std::ranges::find_ifpred 调用次数(至多 N)否(只读,返回位置)否否
std::ranges::sort比较次数与交换或移动成本是(区间内原地重排)否否
std::ranges::transformop 调用与输出赋值次数否(读取输入)是(写目标 iterator)视输出适配器而定
std::remove_ifpred 调用与元素移动次数是(前移保留元素)否(返回 new_last)否(需配合 erase)

标准库只承诺调用次数的数量级,用户可调用对象内部的单次开销由调用者承担:

  • 重型 predicate:find_if 的真实耗时往往由单次条件计算而非循环推进主导。
  • 访问外部资源的 comparator:sort 在 O(N log N) 量级的比较中会成倍放大外部访问延迟。
  • 产生临时分配的 projection:若每次投影都构造临时字符串,排序过程中的反复比较将触发大量额外堆分配。

排查顺序

评估算法开销与异常风险时依次确认:① 识别规模 N 下的计数操作及可调用对象内部开销;② 界定算法属于只读、原地重排还是外部写入;③ 确认容器长度与生命周期是否另由成员函数提交;④ 当 predicate、projection、comparator、assignment、swap、move 或容器插入抛出异常时,回到对应修改层级与容器规则评估局部写入恢复及 iterator 失效范围。

25.5 STL 算法分类​

面对具体需求时,先按问题所属算法族缩小候选范围,再核对族内共有的 iterator 能力与前提不变量,比在函数列表里逐个试错更高效。

算法族核心问题代表算法关键前提与检查点
查询类区间里有什么find_if、count_if、all_of、any_of、none_of、equal、mismatch只读输入、支持短路或线性扫描、返回位置或布尔值
修改类如何写到新状态copy、move、transform、fill、generate、remove_if、replace、reverse、rotate输出可写性与重叠区间、赋值/移动成本、remove_if 需成员函数提交缩容
排序与有序区间如何利用顺序sort、stable_sort、partial_sort、nth_element、binary_search、lower_bound、upper_bound、equal_range、is_sorted、is_sorted_until比较器严格弱序、排序类需 random access、稳定性需求、二分查找须先满足有序或分区条件
集合类合并或比较双有序序列set_union、set_intersection、set_difference、set_symmetric_difference、includes双输入必须有序且比较器语义一致(双指针推进)、输出需足够空间或插入 iterator
堆算法连续区间维护优先级make_heap、push_heap、pop_heap、sort_heaprandom access iterator 与堆不变量(push_heap 前须先尾插,pop_heap 将堆顶换至尾部再恢复余部堆序)
数值归约序列累计、差分或扫描accumulate、reduce、inner_product、partial_sum、inclusive_scan、exclusive_scan、adjacent_difference初始值类型、运算结合性(并行执行尤为关键)、副作用、整数溢出与浮点精度误差

回到贯穿材料 jobs:查找首个可运行任务属于查询类,按优先级排序属于排序类,提取 id 写入 ready_ids 属于修改/变换类,若改为只取优先级 Top-K 任务,则转向堆算法或 partial_sort。

核心判断

选型先定目标族,再沿“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());

本章知识点总结​

  • 半开区间

    [first, last) 由可解引用的起点与只作比较的哨兵边界组成,last 同时承担循环终点与未命中返回值角色。

  • 算法与容器分工

    算法仅通过 iterator 读写或重排元素值,存储分配、容量增长、元素生命周期及迭代器失效由容器管理。

  • 输出边界与逻辑尾端

    普通输出 iterator 须由调用方预留足够空间,back_inserter 将写入转为容器插入;remove_if 只返回 new_last,缩容析构须由 erase 提交。

  • 能力与规则注入

    iterator category 限定算法可用的位置操作,predicate、operation 与 C++20 projection 将业务规则与字段提取从循环中剥离。

  • 可调用对象约束

    算法可能按值复制可调用对象并高频调用,应保持轻量、无隐藏副作用,避免在 comparator 或 projection 中产生隐式分配。

  • 复杂度与修改边界

    评估算法调用需同时核对规模 N 下的计数操作、单次可调用开销、修改层级(只读/重排/输出)及异常传播路径。

  • 按族选型

    先锁定查询、修改、排序、集合、堆或数值归约族,再依次校验有序/堆不变量、比较器一致性与稳定性要求。