Chapter 8: Generic Algorithm Design

STL 算法的核心问题是：一段算法代码如何在不了解容器内部结构的前提下，稳定处理 vector、list、数组、流迭代器和用户自定义 range。答案来自一组很小的接口契约：调用方给出半开区间，iterator 暴露当前位置能力，算法只使用它声明过的操作，用户通过函数对象注入比较、筛选或变换逻辑。

本章用一个贯穿材料展开：mini_find_if 只扫描 [first, last)，只执行 first != last、++first、*first 和 pred(*first)。这段代码足够短，却包含了 generic algorithm design 的主要结构：算法模板接收位置对象，位置对象连接容器内部结构，谓词把用户业务判断接入算法骨架。

本章会把算法设计拆成五个判断动作：先确认输入区间是否成立，再确认 iterator 能力是否满足算法需要，再通过 traits 或 tag dispatch 选择实现路径，再检查谓词或比较器的语义约束，最后把复杂度承诺和失效边界合并成工程判断。读完后，读者应能从一个 STL 算法签名推回它依赖的容器能力、用户责任和实现形状。

标准库资料把 std::find 描述为在 [first, last) 中返回第一个满足条件的位置，并给出 InputIt、谓词和线性复杂度要求；std::sort 明确要求随机访问迭代器和比较器；std::lower_bound 明确要求分区区间，并说明非随机访问迭代器会产生线性级 iterator 递增成本。本章使用 cppreference 的 std::find 条目、std::sort 条目、std::lower_bound 条目和 iterator tag 条目作为语义核对来源，正文只提炼可用于源码阅读和工程判断的部分。

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

算法独立于容器的前提是输入被压缩成一对位置，而这对位置满足同一个 range 契约。半开区间 [first, last) 表示从 first 开始，持续递增后可以到达 last；last 是终止哨位，通常不可解引用。这个约定让空区间、单元素区间和普通区间使用同一种循环结构：只要 first == last，循环就结束。

贯穿材料 mini_find_if 展示了最小算法输入契约。它没有读取容器大小，没有调用 container.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;
}

这段代码对 iterator 提出四个操作要求。first != last 用来判断扫描是否结束；++first 用来移动到下一个位置；*first 用来取得当前位置元素；pred(*first) 用来执行用户定义的命中判断。只要某个类型提供这四类行为，并且这些行为的语义符合输入迭代器要求，算法就能工作。

这个接口条件把容器责任和算法责任切开。容器负责产生合法 iterator，iterator 负责把位置移动和解引用翻译成底层结构访问，算法负责按照区间顺序执行循环，调用方负责保证 first 到 last 之间的区间有效。常见实现里，vector 的 iterator 可能接近指针，list 的 iterator 通常保存节点指针，数组可以通过原生指针参与算法；算法代码看到的都是位置操作。

半开区间还有一个工程收益：返回值可以复用输入边界。mini_find_if 找到元素时返回当前位置，未找到时返回 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';
}

这个调用只把 numbers.begin() 和 numbers.end() 暴露给算法。算法不持有 numbers，也不负责延长容器生命周期。只要 numbers 在算法执行期间保持可访问，iterator 指向的元素序列就能被顺序扫描。

算法签名中的 value type 通常来自 iterator，而非来自容器类型。标准库实现会通过 std::iterator_traits<InputIt>::value_type、reference、difference_type 这类类型信息理解 iterator 能产生什么值、两个位置之间的距离如何表示、解引用结果是否可写。这里的关键判断是：算法依赖的是 iterator 暴露的能力集合，容器只是 iterator 的来源之一。

失败边界也来自这个契约。first 和 last 来自不同容器时，递增 first 无法以合法方式到达 last；last 已经失效时，比较和终止判断都失去语义；调用期间修改容器导致 iterator 失效时，算法继续使用旧 iterator 会进入未定义行为范围。算法通常不会动态检查这些问题，因为检查会要求它重新知道容器结构，从而破坏容器无关设计。

因此，阅读一个 STL 算法签名时，第一步是把输入拆成三层：区间是否由同一序列提供，iterator 是否能完成算法用到的基本操作，元素访问是否满足算法对读写和比较的要求。这三层成立后，算法才谈得上泛化到不同容器。

8.2 iterator + algorithm 的解耦路径

iterator 和 algorithm 的解耦路径可以理解为一次翻译：算法写的是位置操作，iterator 把位置操作翻译成具体容器访问。mini_find_if 的循环表达的是“沿着序列向后扫描”，至于向后一步是数组地址加一、链表节点跳到 next、还是流迭代器读取下一个输入单元，由 iterator 类型决定。

同一个算法体可以处理 vector 和 list，原因是它只使用 input iterator 级别的操作。下面两段调用进入同一个模板实例化模式，但 iterator 类型不同，编译器会为不同 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; }
);

这里的解耦点在模板实例化。源码层面只有一份 mini_find_if；编译期看到 std::vector<int>::iterator 和 std::list<int>::iterator 后，分别实例化出对应版本。运行时不需要通过容器基类、虚函数或统一容器接口访问元素。STL 的泛型算法主要依靠静态多态：类型在编译期决定，操作在生成后的代码中直接展开。

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

这个表说明算法和容器之间的接口面非常窄。算法不关心“下一个元素如何找到”，只关心 ++first 后迭代器进入下一个有效位置。容器内部可以完全不同，但它们通过 iterator 提供同样的外部位置语义。

解耦也带来一个直接限制：算法只能使用 iterator category 允许的操作。mini_find_if 使用顺序递增和解引用，所以 input iterator 足够；二分查找需要反复前进一段距离，所以至少需要 forward iterator 才能可靠多次遍历；排序需要高效随机跳转和交换元素，所以 std::sort 要求 random access iterator。容器是否拥有某种成员函数并不直接决定算法能否使用，算法签名里的 iterator 要求才是边界。

源码阅读时可以按操作反推 iterator 能力。看到 ++it 和 *it，通常是 input 或 forward 级别；看到 --it，需要 bidirectional；看到 it + n、last - first、it[n]，需要 random access；看到算法写入 *out = value，输出位置还必须满足可写语义。这个反推方法比死记算法分类更稳定，因为它直接对应源码里的表达式。

C++20 的 ranges 把一对 iterator 的接口进一步包装成 range 对象和 sentinel，但底层原则保持一致。std::ranges::find(range, value) 可以由 range 取出起点和终点；算法仍然通过 iterator、sentinel、谓词和投影完成工作。本章聚焦传统 STL 算法形态，因为源码阅读中仍会频繁遇到 first, last 这一基础接口。

8.3 traits、tag dispatch 与 policy based design

traits 的作用是把类型携带的信息转成算法能读取的编译期信息。iterator 本身是一种值对象，但算法还需要知道它的类别、差值类型、解引用结果类型和引用类型。std::iterator_traits<It> 提供统一入口，让原生指针和自定义 iterator 都能以同一套名字暴露这些信息。

mini_find_if 不需要显式 traits，因为它只依赖 !=、++、* 和谓词调用。稍复杂的算法会需要 difference_type 记录距离，或需要 iterator_category 选择更合适的实现路径。std::lower_bound 这类算法就会计算区间长度，再通过 std::advance 移动到中点。对随机访问 iterator 来说，移动到中点可以用常数级跳转；对链表 iterator 来说，移动 n 步就要做 n 次递增。

下面的 mini_distance 展示 tag dispatch 的典型形状。它先从 iterator_traits 取出 iterator_category，再把空 tag 对象传给内部实现函数。不同 overload 在编译期被选择，运行时没有额外分支成本。

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

这段简化代码属于教学实现，准确表达了常见源码形状。std::vector<int>::iterator 通常会走随机访问路径，std::list<int>::iterator 通常会走输入或双向迭代器兼容的线性路径。源码里常见的 __iterator_category、__advance、__distance 这类辅助层，本质上就是把 iterator 能力转成实现选择。

iterator tag 的继承关系也服务于这种分发。std::random_access_iterator_tag 派生自 std::bidirectional_iterator_tag，再向上连接到 forward 和 input 体系。这个设计允许一个更强的 iterator 满足较弱算法的要求。强能力可以走更快路径，弱能力走保守路径。

policy based design 在算法中解决的是“可变策略放在哪里”的问题。算法固定骨架，例如遍历、分区、交换、归并；策略参数决定比较方式、执行方式或投影方式。传统 STL 中最常见的策略是比较器和谓词，C++17 又给部分算法增加 execution policy，C++20 ranges 算法还常见 projection。策略进入算法后，算法主体调用策略对象，而非把业务判断写死。

#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 提供排序骨架，LowerScoreFirst 提供顺序策略。算法不理解 User 的业务含义，只要求比较器能在任意需要比较的两个元素之间返回稳定的先后关系。策略对象越小、越容易内联，编译器越容易把算法骨架和业务判断合并成直接代码。

从源码阅读角度看，traits、tag dispatch 和 policy based design 可以用同一个问题串起来：算法缺少哪类信息，信息从哪个模板参数进入，进入后在编译期选 overload、选分支，还是在算法循环里被重复调用。这个问题串能把大量模板噪声压缩成可读路径。

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

函数对象是算法留给调用方的行为插槽。谓词是返回布尔语义的可调用对象，常用于筛选、判断和分区；比较器是二元可调用对象，常用于排序和有序搜索；变换函数用于把输入元素映射成输出值。它们的共同点是：算法控制遍历和结构操作，调用方控制“什么时候命中”“谁排在前面”“如何生成新值”。

mini_find_if 的 UnaryPredicate 就是最小行为插槽。算法每次解引用当前位置，把元素交给谓词；谓词返回 true 时，算法返回当前位置。算法不需要知道“偶数”“活跃用户”“价格超过阈值”这些业务条件，只需要谓词的调用结果能转成布尔判断。

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

这个例子里，算法的遍历顺序、返回规则和失败值固定；业务判断由 lambda 注入。lambda 接收 const UserRecord&，表达它只读取元素状态。对 find_if 这类读取算法，稳定做法是让谓词保持无副作用，至少不修改被检查元素。标准库对谓词参数也有类似要求：谓词必须能接受 value type 的可能 const 形式，返回值能转成 bool，并且不修改传入对象。

排序算法对比较器提出更强语义要求。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{});
}

这里 HigherScoreFirst 把“分数更高者靠前”注入排序骨架。排序算法可以任意选择比较顺序，可能多次比较同一对元素，也可能比较非相邻元素。比较器的工程责任是对任意两个可比较元素给出一致结果；算法的工程责任是在这个关系下重排元素，并满足复杂度承诺。

函数对象还有一个性能层面的意义。模板算法接收具体 callable 类型后，编译器通常能看到 operator() 的定义，进而内联到循环或排序核心路径里。相比通过函数指针进行间接调用，函数对象让泛型算法在保留可插入行为的同时获得静态类型信息。这个优势也是 STL 算法大量使用模板参数接收谓词和比较器的原因之一。

用户可插入行为也会改变异常安全和副作用边界。谓词或比较器抛出异常时，非修改算法通常已经扫描过一部分元素但未改变序列；修改算法或排序算法可能已经完成部分移动、交换或重排。标准库会规定算法自身的基本行为，但用户提供的 callable 仍是失败路径的一部分。工程上应把 callable 当成算法执行路径中的真实代码，而非轻量配置项。

阅读算法源码时，遇到 pred(*it)、comp(*middle, value)、op(*first) 这类调用，要立即分清两件事：算法控制调用次数和调用位置，用户对象控制判断结果和潜在异常。这个分离能帮助读者分析复杂度、异常传播和业务逻辑错误来源。

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

STL 算法的泛化能力有清晰边界，边界来自三类约束：操作约束、语义约束和复杂度约束。操作约束回答“iterator 是否提供源码中使用的表达式”；语义约束回答“输入序列是否满足算法前提”；复杂度约束回答“在这种 iterator 上是否仍然符合工程预期”。

mini_find_if 的边界较宽。它只做单向扫描，所以 input iterator 就能满足。它的复杂度是线性扫描，最多对每个元素调用一次谓词。它的语义前提也相对简单：区间有效，谓词可调用，扫描期间元素可读。这个宽边界使它能适配 vector、list、数组和输入流式迭代器。

std::sort 的边界明显更窄。它需要在区间内反复跳转、比较和交换元素，所以要求 random access iterator，并要求元素可交换或可移动赋值，比较器满足排序所需的关系。std::list 提供双向 iterator，无法满足 std::sort 的随机访问要求，所以链表使用自己的成员 sort，通过节点重连完成排序。这个差异来自数据结构可用操作集合的不同。

std::lower_bound 展示了更细的复杂度边界。它的接口要求是 forward iterator，语义前提是输入区间已经按判断条件分区。它能在比较次数上做到对数级，但当 iterator 缺少 random access 能力时，移动到中点需要线性递增。对 std::map、std::set 这类树形容器，成员 lower_bound 可以利用树结构直接搜索，通常比泛型算法路径更适合。

算法	最小 iterator 能力	语义前提	复杂度判断
`find` / `find_if`	input iterator	区间有效，元素可读，谓词可调用	线性比较或线性谓词调用
`lower_bound`	forward iterator	区间对查找条件已分区	比较次数对数级，非随机访问时 iterator 递增可达线性级
`sort`	random access iterator	元素可重排，比较器形成稳定顺序关系	比较次数为 $O(N \log N)$ 级别
`copy`	input iterator + output iterator	输出区间可写且容量由调用方保证	线性读取和写入

这个表可以转成源码阅读检查顺序。先看算法签名里的 iterator 名称和约束，再看函数体实际使用了哪些 iterator 表达式，然后看文档或标准语义给出的前置条件，最后把复杂度承诺放回当前容器结构里解释。只看“能否编译”会遗漏语义前提；只看“大 O”会遗漏 iterator 移动成本和成员函数替代路径。

适配边界还包括写入和覆盖关系。std::copy(first, last, out) 把输入区间写到输出位置，算法无法知道输出位置后面是否有足够空间。调用方必须提供可写输出 iterator，并保证写入目标能容纳元素。对同一容器内的重叠区间，具体算法会有方向要求；例如需要从后向前复制时，应选择对应的 backward 版本。这个责任划分是算法泛化的代价：算法获得通用接口，调用方承担区间合法性。

另一个边界是 iterator 失效。算法执行期间只持有 iterator，不持有容器锁或结构版本。若用户在谓词、比较器或并发代码中修改同一容器，并导致原有 iterator 失效，算法的后续操作就失去依据。稳定的工程判断是：把算法调用视为一个使用区间的连续操作，在调用完成前保持区间结构条件成立。

因此，判断一个 STL 算法能否适配某个容器时，应按这个顺序给出结论：区间来源是否同一序列；iterator category 是否覆盖算法源码操作；元素引用是否满足读写或交换要求；谓词、比较器或输出位置是否满足语义条件；复杂度承诺在当前数据结构上是否符合需求；容器成员函数是否能利用内部结构提供更合适路径。

最小自检任务

阅读下面问题代码片段，判断三处调用分别是否适合当前容器和 iterator。代码中包含一处编译期不适配调用。要求说明每个判断依赖的区间契约、iterator 能力、谓词或比较器要求，以及复杂度边界。

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

答案要点

std::find_if(values.begin(), values.end(), predicate) 适合当前 vector。输入是同一容器产生的半开区间，vector iterator 满足顺序扫描需要，谓词接收 int 并返回布尔语义。算法最多线性检查元素，返回第一个大于 4 的位置或 values.end()。

std::sort(nodes.begin(), nodes.end()) 不适合这段代码中的 list iterator。std::sort 要求 random access iterator，而 std::list<int>::iterator 提供双向移动能力。正确判断是使用 nodes.sort() 这类成员算法，让链表利用节点重连完成排序。

std::lower_bound(ordered.begin(), ordered.end(), 4) 在语义上可以处理有序区间，但工程上通常应优先选择 ordered.lower_bound(4)。泛型 lower_bound 对 forward iterator 可以工作，比较次数是对数级，但树形容器 iterator 递增到中点会带来线性移动成本；成员函数能利用树结构查找。

本题的判断顺序是：先看区间是否有效，再看算法要求的 iterator category，再看谓词或比较器是否稳定，最后把复杂度放回容器结构中解释。这个顺序比记忆单个算法名称更可靠。

本章知识点总结

半开区间：STL 算法通常用 [first, last) 表达输入范围，last 表示终止哨位，未命中时也常作为返回值。
位置契约：算法接收的是 iterator 位置对象，调用方负责提供同一序列中的有效起点和终点。
容器解耦：算法通过 !=、++、* 等 iterator 操作访问元素，容器内部结构由 iterator 翻译。
静态多态：模板算法在编译期根据 iterator 和 callable 类型实例化，通常无需容器基类或虚函数分发。
能力反推：源码中出现 --it、it + n、last - first 等表达式时，可以反推出算法需要的 iterator category。
traits 入口：std::iterator_traits 把 iterator 的类别、差值类型和值类型统一暴露给算法实现。
tag dispatch：算法可以用 iterator tag 在编译期选择线性路径或随机访问优化路径。
策略参数：谓词、比较器、execution policy 和 projection 都是把可变行为接入固定算法骨架的方式。
谓词责任：谓词应能接受算法传入的元素引用并返回布尔语义，读取型算法中的谓词应保持元素状态稳定。
比较器责任：排序比较器需要提供稳定的先后关系，算法会按照自己的实现顺序多次调用比较器。
复杂度边界：同一算法在不同 iterator 上可能保持相同比较次数，却产生不同的 iterator 移动成本。
成员替代：树形容器和链表常提供成员算法或成员查找函数，用内部结构补足泛型算法看不到的信息。
写入责任：输出类算法只通过 output iterator 写入，目标空间和重叠方向由调用方按算法要求保证。
判断顺序：分析算法适配性时，依次检查区间、iterator category、元素读写、用户 callable、复杂度和容器成员替代路径。

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

8.2 iterator + algorithm 的解耦路径​

8.3 traits、tag dispatch 与 policy based design​

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

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

最小自检任务​

答案要点​

本章知识点总结​