侯捷 STL 学习笔记（一）：从六部件合作理解泛型编程

侯捷 C++ 六门课程总目录

会写 vector<int>，不等于知道该选哪一种容器；能调用 count_if，也不等于知道它为什么能处理多种容器。侯捷这门课程从使用入口走向源码，关注的正是这段距离：数据怎样存放，算法怎样访问它，改变一个条件以后，哪些部分还能复用。

来源档案：讲者为侯捷；标题页原课名《C++标准库：体系结构与内核分析》，画面带 Boolan 博览标识。本次选用 B 站账号 DetachmentSy 于 2025 年上传的《侯捷 - STL标准库和泛型编程》（BV1kBh5zrEYh，当前 46 个分 P）。本文覆盖 P1《认识headers、版本、重要资源》、P2《STL体系结构基础介绍》。原始录制年份及原课完整性未核实，上传年份不能当作录制年份。核对日期：2026-09-12。本次回放入口。链接失效后，可用“侯捷 C++标准库体系结构与内核分析 Boolan”检索。

本系列为 AI 辅助初加工的学习笔记。本文先完整读取两集音轨转录，再核对关键课件与代码；现代补充和原创实验与课堂演示分别说明，不发布逐字稿。

本门阅读路线与先修

本文是本门课程的导论。先准备 C++ 基本语法、指针、类以及模板的使用经验；暂时不会写复杂模板也能读这一篇。读完应能解释：为什么算法接收一对迭代器；为什么二元比较不能直接成为 count_if 的条件；为什么 auto 和 auto& 会产生不同结果。

文章	问题	覆盖分 P
一、从六部件合作理解泛型编程（本文）	数据、访问协议和操作怎样搭配	P1–2

P1 把目标分成会使用、认识内部结构、良好使用、扩充四层。最值得保留的是其中的因果关系：心里有容器的内存布局和扩展方式，才能判断它是否适合自己的工作负载。扩充标准库组件不是学习的必达终点，先把已有部件用好已经很有价值。

不是六个名词，而是一个统计任务

P2 先画出部件关系，再给出一个很短的程序。课堂数组保存 27、210、12、47、109、83 六个整数，随后构造 vector<int, allocator<int>>，并统计满足条件的元素数。

可以沿着这个任务理解每个角色。

容器负责保存元素和维护自己的结构。需要动态存储时，分配器在背后提供存储服务；课堂显式写出 allocator<int>，只是为了让这个通常被默认参数隐藏的角色露出来。这里的 int 是元素类型，不意味着分配器每次只能取得一个整数的空间。

统计动作放在独立算法 count_if 中。算法不接收整个 vector，而是接收 vi.begin()、vi.end() 和一个判断条件。迭代器把“怎样访问元素”提供给算法，让算法不必知道容器内部是连续数组、链表还是其他结构。

这与把所有业务操作都放进容器成员函数的组织方式不同。不过，容器仍然是类，仍有成员操作，泛型编程也没有否定封装。真正分开的，是依赖具体布局的管理工作与可通过访问协议复用的算法。

部件	在这个例子里做什么
容器 container	`vector` 保存六个整数
分配器 allocator	为容器所需动态存储提供服务
迭代器 iterator	指定要遍历的范围，支持访问和前进
算法 algorithm	`count_if` 统计谓词为真的元素
函数对象 function object	`less<int>` 表达两个整数的“小于”关系
适配器 adapter	固定一个参数，再把判断结果取反

这套六部件分类是理解经典 STL 的课程框架，不是整个现代 C++ 标准库的穷尽分类。P1 也区分标准库与 STL；课堂随口给出的占比不应当作统计数字。

条件是怎样一步步变出来的

先提出“小于 40 的元素有几个”。凭眼睛能找到 27 和 12，答案是 2。算法则需要一个可以针对当前元素返回真假的谓词。

课堂从 less<int> 出发，它回答的是“第一个整数是否小于第二个整数”。问题在于：count_if 每次只把一个元素交给条件，而比较需要两个参数。于是用 bind2nd 把第二个参数固定为 40，把 less(x, y) 变成 less(x, 40)。

为了演示继续组合，课程在外面加上 not1，否定刚才的一元谓词。对本例整数而言，条件便从“小于 40”变成“大于等于 40”，结果应为 4。下面仅是历史课堂的结构片段：

less<int>()
  → bind2nd(less<int>(), 40)
  → not1(bind2nd(less<int>(), 40))
  → count_if(vi.begin(), vi.end(), 上述谓词)

不要把这些旧名字直接复制进现代代码。bind2nd 已从 C++17 标准移除，旧式否定器 not1 也在后续清理中退出标准；可分别查阅 C++17 变更记录与废弃设施清理提案。今天可以直接用 lambda 表达条件；需要复用否定操作时，也有 std::not_fn。

要保留下来的是接口适配的推导：一个操作的语义正确，但参数形式与使用位置不匹配，就把差异集中到一个小对象里。这与站内接口隔离与适配器笔记的思想相通，只是这里适配的是可调用对象的参数，而非外部系统接口。

半开区间把“停止”变成协议的一部分

P2 后半段专门解释 [first, last)：包含开始位置，不包含结束位置。end() 表示越过最后一个元素的位置，不能解引用。它不是“最后一个元素的另一种叫法”。

这个约定使空范围自然表示为 first == last。循环先检查是否抵达终点，再取元素，空范围无需另造一个虚假元素。课堂图也特意画出不连续的格子，提醒读者：范围的逻辑顺序不等于内存地址连续。

现代补充还要收紧“泛化指针”的类比。不同迭代器的能力不同：能 ++，不代表能 --；能顺序遍历，不代表能 it + n。算法能复用的前提是迭代器满足其能力要求，不是所有算法都能套到所有容器上。这与迭代器模式的访问协议直接相连：隐藏表示方式，也必须保留能力和失效条件。

用现代 C++ 验证同一条推导

下面是据课堂思路重写的完整 C++20 实验，只依赖标准库。它保留原六个整数，分别检验条件、空范围和 range-for 的值/引用区别；不是历史源码原样复制。

#include <algorithm>
#include <cassert>
#include <vector>

int main() {
    std::vector<int> values{27, 210, 12, 47, 109, 83};
    int limit = 40;
    auto below = [limit](int x) { return x < limit; };
    auto not_below = [below](int x) { return !below(x); };

    assert(std::count_if(values.begin(), values.end(), below) == 2);
    assert(std::count_if(values.begin(), values.end(), not_below) == 4);
    assert(!below(40) && not_below(40));

    std::vector<int> empty;
    assert(empty.begin() == empty.end());
    assert(std::count_if(empty.begin(), empty.end(), below) == 0);

    const auto original = values;
    for (auto element : values) {
        element *= 3;
        assert(element % 3 == 0);
    }
    assert(values == original);

    for (auto& element : values) element *= 3;
    for (std::size_t i = 0; i < values.size(); ++i)
        assert(values[i] == original[i] * 3);
}

此例已用 Apple Clang 21、-std=c++20 -Wall -Wextra -pedantic 编译并执行，全部断言通过。

这里的两个 lambda 分别承担固定阈值和否定条件的工作，仍能看出课堂的两层组合。这个小例子直接写 x >= 40 更简洁，但保留中间对象有助于检查“转换前后的接口是什么”。

代码也对应课堂最后一处变化：for (auto element : values) 取得元素副本；auto& 才让赋值影响容器中的整数。循环变量表示元素的值或引用，不能与遍历用的迭代器混为一谈。课堂紧接着把冗长的 list<string>::iterator 改为 auto 接收 find 的结果，那才是在推导迭代器类型。

此例采用小整数，乘三不会溢出。把元素换成大整数或自定义类型后，应重新检查算术和复制语义；对具有无序情况的浮点比较，也不能无条件把 !(x < limit) 替换成 x >= limit。

选型之前，先说明自己要做哪些操作

P2 并没有给出“最快容器”排名。课堂连续追问：从头还是从尾追加？是否常在中间插入？是否需要先查找再删除？这些问题决定一种结构的优势是否真的用得上。

复杂度帮助比较随规模增长的工作量，却不直接给出某台机器上的耗时。课程强调大规模测试，是为了让增长差异显现；它不意味着低于十万或一百万元素，复杂度概念就不成立。对于小规模，常数、分配成本和局部性可能尤其明显。后续读源码时，应一直把这些操作问题带在身边。

P1 对源码版本的提醒同样值得保留：从较旧实现切入，常能更快看懂核心结构。但标准规定的接口与复杂度、某个版本的组织方式、某次运行的耗时，是三种不同证据。旧实现可以帮助理解，不能替今天的标准作保证。

头文件也是如此。<vector>、<algorithm> 是使用入口，不等于整个标准库都只由头文件实现。标准说元素在头文件中按需声明或定义，并不保证所有实现源码都在其中；C 兼容头的命名空间规则也比“有无 .h”的口头二分更细，见标准库头文件条款。本文示例显式写 std::，避免把课堂便捷写法 using namespace std; 变成公共头文件的默认习惯。

重点回看

以下时间属于本次上传版本，字幕坐标已结合列出的课件核对；播放器不跳转时仍可按 P 与时间手动定位。

分 P 与时间	识别线索	回看重点
P1 · 09:35–15:35	headers、namespace std	区分组件名称、头文件入口与命名空间写法
P1 · 19:14–21:13	Bibliography、STL源码剖析	为什么先用较旧实现理解结构
P2 · 09:30–21:05	六部件关系、count_if	从小于40，到绑定参数，再到否定条件
P2 · 25:33–29:22	“前闭后开”区间、end红叉	为什么结束位置不代表一个可读元素
P2 · 32:07–38:24	range-based for、auto keyword	元素副本、元素引用与迭代器类型三者的区别

思考与实验

把阈值改为 27，再给数组加入 40。先手算两个计数，再运行断言。检验的是“严格小于”和“否定小于”的边界，而不是记住原答案。
把 values 改为 std::list<int>，只保留两个 count_if 断言。它们是否仍成立？随后尝试 values.begin() + 2，解释编译错误来自哪一项能力缺失。
把否定条件直接写成 x >= limit，对本例整数两者等价。扩展实验可用浮点 NaN 检查二者结果，说明比较关系的额外假设为何不能被适配器语法隐藏。

理解这些小实验之后，再回到从变化出发的抽象讨论，可以比较两种复用路径：运行时通过共同接口替换对象，或编译时让不同类型满足同一操作要求。它们保护的变化和付出的成本不同，不能只凭“用了模板”就判定设计更好。