Skip to main content

Chapter 8: Generic Algorithm Design

核心问题与阅读主线

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

STL 泛型算法的核心问题,是如何用一份不感知容器内部布局的模板代码,同时处理 vector、链表、原生数组与流迭代器。工程解法由四条最小契约构成:半开区间划定范围、iterator 抽象位置操作、traits/policy 注入编译期信息,以及 callable 注入业务策略。

全章共用场景样本

贯穿材料贯穿场景

全章以 mini_find_if 为贯穿材料:它仅扫描 [first, last),只执行 first != last、++first、*first 与 pred(*first) 四个动作,集中呈现了算法骨架、位置抽象与可调用插槽的耦合边界。

标准语义与复杂度基线对照 cppreference std::find、std::sort、std::lower_bound 与 iterator tags。

8.1 算法独立于容器的接口条件​

算法脱离容器的前提,是将输入收拢为同一序列的半开区间 [first, last):first 持续递增可到达 last,last 仅作终止哨位、不可解引用。空区间(first == last)与非空区间由此共用同一套循环终止条件。

贯穿材料 mini_find_if 不读取容器大小、不调用 begin(),只依赖一对满足输入契约的 iterator:

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

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

这段实现仅要求 InputIt 满足四项最小操作:

  • first != last:判断是否到达终止哨位。
  • ++first:推进到下一位置。
  • *first:读取当前位置元素。
  • pred(*first):执行用户传入的命中判断。

接口契约将四方职责彻底解耦:

  • 容器:产生合法起止 iterator(vector 接近原生指针,list 保存节点指针,原生数组直接作为指针)。
  • iterator:将位置移动与解引用翻译为底层结构访问。
  • 算法:只按区间顺序驱动循环,不感知容器结构。
  • 调用方:保证 [first, last) 有效,且容器在执行期间保持可访问。

半开区间还让返回值直接复用 last 哨位:命中返回当前位置,未命中返回 last,无需额外状态区分失败路径(std::find、std::find_if 均采用这一接口形状):

std::vector<int> numbers{3, 1, 4, 1, 5};

auto it = mini_find_if(numbers.begin(), numbers.end(), [](int value) {
return value > 3;
});

if (it != numbers.end()) {
std::cout << *it << '\n';
}

算法所需的 value_type、reference 与 difference_type 均通过 std::iterator_traits<InputIt> 从 iterator 提取,而非来自容器本身——容器只是 iterator 的来源之一。

边界与误区

注意

算法无法在运行期校验区间归属与生命周期(否则必须感知容器结构,破坏泛化)。以下三类误用均会直接触发未定义行为:first 与 last 来自不同容器导致递增无法到达终点;last 已失效使终止判断失去语义;遍历期间修改容器引起迭代器失效后算法继续解引用。

8.2 iterator + algorithm 的解耦路径​

iterator 与 algorithm 的解耦本质上是一次翻译:算法只表达“沿位置向后扫描”,具体是数组地址加一、链表节点跳到 next,还是流迭代器读取下一单元,全部由 iterator 类型决定。

同一份 mini_find_if 源码可以同时接收 vector 与 list 的迭代器,编译器在编译期按不同 InputIt 分别实例化:

std::vector<int> vector_values{1, 3, 5, 8};
std::list<int> list_values{1, 3, 5, 8};

auto vector_hit = mini_find_if(
vector_values.begin(),
vector_values.end(),
[](int value) { return value % 2 == 0; }
);

auto list_hit = mini_find_if(
list_values.begin(),
list_values.end(),
[](int value) { return value % 2 == 0; }
);

解耦发生于编译期静态多态:编译器分别为 std::vector<int>::iterator 与 std::list<int>::iterator 生成特化代码并直接展开操作,运行时无需容器基类或虚函数分发。

算法表达iterator 承担的翻译vector 常见形状list 常见形状
first != last判断当前位置是否到达终点比较两个位置地址或包装指针比较两个节点位置
++first移动到下一个元素指针向后推进一个元素大小跳到当前节点的后继
*first取得当前位置元素解引用连续存储位置访问节点内的值
返回 first把命中位置交还调用方返回数组式位置返回节点式位置

阅读算法源码时,可直接按源码表达式反推最低 iterator 能力:

源码关键表达式最低 iterator 能力典型算法或语义要求
++it、*it、it1 != it2InputIterator / ForwardIteratormini_find_if(单趟扫描);std::lower_bound(需多趟前向)
*out = valueOutputIteratorstd::copy 等写入类算法,目标位置必须可写
--itBidirectionalIterator双向遍历与逆序操作
it + n、last - first、it[n]RandomAccessIteratorstd::sort(随机跳转与交换)

核心判断

容器是否拥有某种成员函数并不直接决定泛型算法能否接入;算法签名声明的 iterator category 及其使用的表达式集合才是唯一能力边界。

关键事实

C++20 std::ranges::find(range, value) 将一对位置进一步封装为 range 与 sentinel,但底层仍通过 iterator、sentinel、谓词与投影完成工作,与传统 [first, last) 契约完全一致。

8.3 traits、tag dispatch 与 policy based design​

std::iterator_traits<It> 为原生指针和自定义 iterator 提供统一的编译期类型萃取入口,集中暴露 iterator_category、difference_type、value_type 与 reference。

mini_find_if 无需显式 traits;而 std::lower_bound 等算法需用 difference_type 记录区间长度,并按 iterator_category 借助 std::advance 移动到中点——随机访问 iterator 走常数级跳转,链表 iterator 只能做 n 次递增。

mini_distance 展示了 tag dispatch 的典型编译期分发结构:

#include <iterator>

template<class InputIt>
typename std::iterator_traits<InputIt>::difference_type
mini_distance_impl(InputIt first, InputIt last, std::input_iterator_tag) {
typename std::iterator_traits<InputIt>::difference_type count = 0;
for (; first != last; ++first) {
++count;
}
return count;
}

template<class RandomIt>
typename std::iterator_traits<RandomIt>::difference_type
mini_distance_impl(RandomIt first, RandomIt last, std::random_access_iterator_tag) {
return last - first;
}

template<class It>
typename std::iterator_traits<It>::difference_type
mini_distance(It first, It last) {
using Category = typename std::iterator_traits<It>::iterator_category;
return mini_distance_impl(first, last, Category{});
}

标准库源码里的 __iterator_category、__advance、__distance 辅助层均遵循这一模式。配合 tag 继承关系(std::random_access_iterator_tag 派生自 std::bidirectional_iterator_tag,再向上连至 forward 与 input 体系),std::vector<int>::iterator 命中常数级路径,而 std::list<int>::iterator 自动向上匹配到 std::input_iterator_tag 线性路径,零运行时分支开销。

与 traits/tag dispatch 互补,policy based design 将可变策略从固定算法骨架中抽离:

机制注入信息绑定时机与机制在算法中的作用
std::iterator_traitsvalue_type、difference_type、iterator_category编译期模板特化萃取统一读取指针与迭代器元信息
tag dispatch继承体系化的空 tag 类型编译期重载决议为强/弱能力迭代器分派快/慢路径
谓词 / 比较器命中判定或元素先后关系模板策略参数把业务判断接入遍历、分区与排序骨架
execution policy / projectionC++17 并行策略 / C++20 成员投影模板策略参数扩展调度方式或解耦比较键提取

下面用 LowerScoreFirst 将排序策略注入 std::sort:

#include <algorithm>
#include <string>
#include <vector>

struct User {
std::string name;
int score;
};

struct LowerScoreFirst {
bool operator()(const User& left, const User& right) const {
return left.score < right.score;
}
};

void order_users(std::vector<User>& users) {
std::sort(users.begin(), users.end(), LowerScoreFirst{});
}

std::sort 只提供排序骨架并要求比较器给出稳定先后关系;无状态且短小的策略对象可被编译器直接内联进排序核心路径。

排查顺序

阅读泛型算法源码时先追问三件事:算法缺哪类信息(迭代器能力还是业务策略)、信息从哪个模板参数进入、最终在编译期选择 overload 还是在循环体内被逐元素调用。

8.4 函数对象、谓词与用户可插入行为​

算法固定遍历与重排骨架,用户通过函数对象(callable)控制“何时命中”“谁排在前”“如何映射”。三类核心插槽的接口分工与约束如下:

可调用对象典型职责常见算法语义约束
谓词(Predicate)返回可转 bool 的条件判断find_if、分区类算法接收 const 兼容的 value_type,读取算法中应无副作用
比较器(Comparator)二元顺序判定 comp(a, b)sort、lower_bound必须满足严格弱序,同一对元素结果前后一致
变换函数(Op)将输入元素映射为输出值transform只负责单点变换,异常与副作用归调用方承担

在 mini_find_if 中,lambda 作为 UnaryPredicate 接收 const UserRecord&,仅执行只读条件判定:

struct UserRecord {
int id;
bool active;
int score;
};

std::vector<UserRecord> records{
{1, false, 80},
{2, true, 65},
{3, true, 90}
};

auto first_active = mini_find_if(records.begin(), records.end(), [](const UserRecord& record) {
return record.active;
});

std::sort 对比较器的要求更严:算法会以任意顺序多次比较同一对或非相邻元素,比较器必须构建严格弱序,算法才能保证重排收敛与复杂度承诺:

#include <algorithm>

struct HigherScoreFirst {
bool operator()(const UserRecord& left, const UserRecord& right) const {
return left.score > right.score;
}
};

void rank_records(std::vector<UserRecord>& records) {
std::sort(records.begin(), records.end(), HigherScoreFirst{});
}

关键事实

STL 大量使用模板参数接收函数对象而非函数指针:每个函数对象或 lambda 拥有独立静态类型,编译器可直接看到 operator() 定义并将其内联到循环或排序热路径中,避免间接调用开销。

边界与误区

注意

用户 callable 属于算法真实执行路径与失败路径的一部分:比较器若依赖随机数、时钟等可变外部状态或在比较中修改元素,会破坏严格弱序前提;callable 抛出异常时,非修改算法通常不改变序列,而修改与排序算法可能已留下部分移动、交换或重排的中间状态。

8.5 algorithm 适配不同 iterator 的设计边界​

STL 算法的泛化边界由三类约束共同划定:

  • 操作约束:iterator 是否提供算法源码实际使用的表达式。
  • 语义约束:输入区间、元素可变性及 callable 是否满足前置条件。
  • 复杂度约束:在当前 iterator 能力下,比较与移动成本是否仍符合预期。
算法最小 iterator 能力语义前提复杂度判断
find / find_ifinput iterator区间有效,元素可读,谓词可调用线性比较或线性谓词调用
lower_boundforward iterator区间对查找条件已分区比较次数对数级,非随机访问时 iterator 递增可达线性级
sortrandom access iterator元素可重排,比较器形成稳定顺序关系比较次数为 $O(N \log N)$ 级别
copyinput iterator + output iterator输出区间可写且容量由调用方保证线性读取和写入

只看“能否编译”会忽略语义前提,只看“大 O 比较次数”则会忽略非随机访问迭代器的移动开销与成员替代路径:

  • std::list 仅提供双向 iterator,编译期即不满足 std::sort;链表应调用成员 sort 通过节点重连完成排序。
  • std::map / std::set 虽满足 std::lower_bound 的 forward iterator 要求且比较次数为对数级,但迭代器移动中点需线性递增;工程上应优先调用利用树结构的成员 lower_bound。

边界与误区

注意

std::copy(first, last, out) 不校验输出位置后的剩余容量,目标空间必须由调用方预先保证;同一容器内区间重叠时需按方向要求选择对应算法(如从后向前复制应使用 backward 版本)。同时算法不持有容器锁或版本号,执行期禁止在回调或并发代码里修改容器导致迭代器失效。

评估一个 STL 算法能否适配目标容器,按以下六步核查:

  1. 区间来源:[first, last) 是否来自同一序列且执行期持续有效。
  2. 操作能力:iterator category 是否覆盖算法源码全部表达式。
  3. 元素权限:解引用结果是否满足算法所需的只读、可写或可移动交换要求。
  4. 语义契约:谓词无副作用、比较器满足严格弱序、输出目标容量与重叠方向正确。
  5. 成本匹配:比较次数与 iterator 移动步数在当前结构上是否可接受。
  6. 成员替代:容器自身是否提供利用底层结构(链表指针、搜索树)的成员算法。

最小自检任务​

动手自检先独立判断

判断下面三处算法调用是否分别适配当前容器与 iterator(包含一处编译期报错),并说明各处判断依据的区间契约、iterator 能力、callable 要求与复杂度边界。

#include <algorithm>
#include <list>
#include <set>
#include <vector>

void check_algorithms() {
std::vector<int> values{1, 4, 2, 8, 5};
std::list<int> nodes{1, 4, 2, 8, 5};
std::set<int> ordered{1, 2, 4, 5, 8};

auto a = std::find_if(values.begin(), values.end(), [](int value) {
return value > 4;
});

std::sort(nodes.begin(), nodes.end());

auto b = std::lower_bound(ordered.begin(), ordered.end(), 4);
}

本章知识点总结​

  • 半开区间契约

    [first, last) 统一空区间与常规循环,last 兼作未命中返回值;区间同源与存活期由调用方保证。

  • 静态多态解耦

    算法仅消费位置表达式,编译器按 iterator 类型实例化特化代码,无需虚函数;源码表达式可直接反推所需 iterator category。

  • traits 与 tag dispatch

    std::iterator_traits 统一暴露元信息,配合 tag 继承体系在编译期把 __advance、__distance 分派至最优路径。

  • 策略与可调用内联

    谓词、比较器、execution policy 与 projection 将可变策略接入固定骨架;函数对象保留静态类型,便于编译器内联 operator()。

  • callable 语义与异常边界

    std::sort 要求严格弱序且无可变状态干扰;callable 抛异常时,修改/排序算法可能已留下部分重排状态。

  • 复杂度与成员替代

    std::lower_bound 在非随机访问 iterator 上仍需线性移动步数,链表 sort 与关联容器 lower_bound 应优先走成员函数。

  • 适配核查顺序

    依次确认区间同源、iterator 能力、读写权限、callable/容量语义、移动成本与容器成员替代路径。