《STL源码剖析》——侯捷

一流程序员读源码。庖丁解牛，目无全牛。

书籍概览

侯捷经典巨著，中文世界唯一一本深入剖析 STL 底层实现的著作。以 SGI STL 2.91.57 版本为分析对象，从空间配置器到迭代器、容器、算法、仿函数、配接器，逐一拆解 STL 六大组件的源码实现与设计思想。

核心价值：不是教你怎么用 STL，而是教你 STL 为什么这么设计、底层如何实现。读完这本书，你对 STL 的理解将从”会用”跃升至”明理”，甚至达到”能扩展”的第三境界。

阅读门槛：不适合 STL 初学者，更不适合 C++ 初学者。需要有扎实的 C++ 模板基础和 STL 使用经验。

STL 六大组件

组件	作用	本书章节
空间配置器（Allocator）	内存的分配与管理	第2章
迭代器（Iterators）	连接容器与算法的桥梁，traits 编程技法	第3章
容器（Containers）	序列式 + 关联式，各种数据结构实现	第4-5章
算法（Algorithms）	排序、查找、数值、集合运算等	第6章
仿函数（Functors）	函数对象，算法的策略参数	第7章
配接器（Adapters）	容器/迭代器/仿函数的包装转换	第8章

第1章 STL概论与版本简介

STL 的历史脉络

HP 版本：STL 鼻祖，Alexander Stepanov 与 Meng Lee 在 HP 实验室完成的最初实现，所有 STL 版本的祖本
P.J. Plauger 版本：Dinkumware 出品，VC++ 自带的 STL 实现，代码可读性较差
Rogue Wave 版本：Borland C++ Builder 采用
STLport 版本：跨平台移植版，源自 SGI STL，支持多编译器
SGI STL 版本：本书分析对象，出自 Stepanov 本人之手，设计最巧妙、思想最深刻，开源免费

SGI STL 文件结构

三类文件：

标准头文件（无扩展名）：<vector>、<list>、<algorithm> 等，用户直接 include
HP 规范头文件（.h 扩展名）：C++ Standard 定案前的旧规范
内部私用文件（stl_*.h）：真正的实现代码，如 stl_vector.h、stl_alloc.h

关键 C++ 语法知识点

本章专门铺垫了阅读源码所需的高级 C++ 语法：

模板偏特化（partial specialization）：为某些模板参数提供特殊实现
成员模板（member templates）：类的成员函数本身也是模板
静态常量整数成员 in-class 初始化：static const int N = 100;
临时对象的产生与运用：int()、vector<int>() 这种显式构造临时对象
前闭后开区间表示法 [)：STL 迭代器的核心约定
operator() 重载：让类对象可以像函数一样被调用（仿函数的基础）
increment/decrement/dereference 操作符：迭代器实现的关键

第2章空间配置器（Allocator）

STL 一切容器的内存根基。放在最前面讲，是因为理解 allocator 是领悟 STL 工作原理的先决条件。

2.1 标准接口

STL allocator 的标准接口规范：allocate()、deallocate()、construct()、destroy()。

2.2 SGI 双层空间配置器

SGI 设计了两级配置器，核心思想：大内存直接 malloc，小内存用内存池+自由链表管理，避免碎片化。

第一级配置器 __malloc_alloc_template：

处理 >128 字节的大内存申请
直接封装 malloc/free
内置 malloc_alloc_oom_handler 机制：内存不足时调用用户设定的处理函数，反复尝试释放内存后再分配

第二级配置器 __default_alloc_template：

处理 ≤128 字节的小内存申请
维护 16 条 free-lists（8/16/24/…/128 字节各一条）
每次申请上调至 8 的倍数，从对应链表取块
链表空时从内存池（memory pool）批量分配 20 个节点填充
内存池也空了就向系统堆申请一大块（通常 40 个节点量 + 额外附加量）

2.3 内存基本处理工具

三个底层函数，负责在已分配的”原始内存”上构造对象：

函数	作用	优化策略
`uninitialized_copy`	在 [result, result+n) 上复制构造 [first, last) 的元素	POD 类型直接 memcpy，非 POD 逐元素 construct
`uninitialized_fill`	在 [first, last) 上填充值为 x 的对象	POD 类型直接 fill，非 POD 逐元素 construct
`uninitialized_fill_n`	在 [first, first+n) 上填充 n 个值为 x 的对象	POD 类型直接 fill_n，非 POD 逐元素 construct

核心思想：对 POD（Plain Old Data）类型走最快路径（memcpy/fill），对非 POD 类型走安全路径（逐个构造/析构）。这是 STL 性能优化的经典模式——type_traits + 编译期分发。

第3章迭代器（Iterators）与 Traits 编程技法

迭代器是 STL 的核心设计：让算法独立于容器，用统一的接口操作不同的数据结构。

3.1 迭代器设计思维

迭代器是一种”智能指针”，封装了对容器元素的访问和移动。算法不直接操作容器，只操作迭代器，实现了算法与容器的解耦。

3.2 Traits 编程技法——STL 源代码门钥

iterator_traits 是萃取迭代器”相应型别”的统一接口。迭代器需要定义 5 种型别：

相应型别	含义
`value_type`	迭代器指向的元素类型
`difference_type`	两个迭代器之间的距离类型
`reference_type`	元素的引用类型
`pointer_type`	元素的指针类型
`iterator_category`	迭代器的分类（移动能力等级）

iterator_category 的 5 个等级（继承关系从弱到强）：

input_iterator_tag：只读，单向移动
output_iterator_tag：只写，单向移动
forward_iterator_tag：读写，单向移动
bidirectional_iterator_tag：读写，双向移动
random_access_iterator_tag：读写，随机访问（支持 +n、-n、[] 运算）

3.3 编译期分发（Compile-time Dispatching）

以 advance() 和 distance() 为例：

advance(it, n)：随机访问迭代器可以直接 it += n（O(1)），双向迭代器必须循环 n 次（O(n)）
distance(first, last)：随机访问迭代器可以直接 last - first（O(1)），输入迭代器必须循环计数（O(n)）

实现方式：函数重载 + iterator_category 作为参数类型，编译器在编译期选择正确的版本。没有运行时开销。

3.4 `std::iterator` 保证

所有 STL 迭代器都继承自 std::iterator<category, T, distance, pointer, reference>，自动定义 5 种型别，避免遗漏。

3.5 `__type_traits`

SGI 的扩展，比 iterator_traits 更进一步——萃取类型本身的特性：

has_trivial_default_constructor：是否有平凡默认构造函数
has_trivial_copy_constructor：是否有平凡拷贝构造函数
has_trivial_assignment_operator：是否有平凡赋值运算符
has_trivial_destructor：是否有平凡析构函数
is_POD_type：是否是 POD 类型

用途：uninitialized_copy/fill 等底层函数根据这些特性选择最优路径。POD 类型直接 memcpy，非 POD 必须调用构造/析构函数。

这是模板元编程的雏形：在编译期根据类型特性做决策，运行时零开销。

第4章序列式容器（Sequence Containers）

4.1 容器分类

序列式容器：元素有序排列，位置由插入时机和位置决定
- vector、list、deque、heap（隐式）、priority_queue、stack、queue、slist

4.2 Vector

底层结构：连续线性空间，三个指针 start、finish、end_of_storage

核心机制——两倍扩容：

容量满时，重新分配两倍大小的新空间
把旧元素全部拷贝/移动到新空间（构造 + 析构）
释放旧空间
所有迭代器、指针、引用全部失效

时间复杂度：

push_back 均摊 O(1)（因为扩容是均摊的）
尾部 pop_back O(1)
中间 insert/erase O(n)（元素移动）
随机访问 O(1)

4.3 List

底层结构：双向循环链表，一个哨兵节点 node

特点：

插入/删除 O(1)（只要拿到迭代器）
不连续空间，迭代器不会因插入失效（除了指向被删元素的）
不支持随机访问，没有 operator[]
自带 sort() 成员函数（比 std::sort 高效，因为链表用 merge sort 更合适）

关键操作：splice（拼接）、merge（归并）、reverse（反转）、sort（排序）— 都是 O(n) 但常数因子不同。

4.4 Deque（双端队列）

底层结构：分段连续空间 + 中控器（map，即指针数组）

设计精妙之处：

对外呈现”连续空间”的假象（随机访问迭代器），实际由多段固定大小的缓冲区组成
每段缓冲区大小固定（通常 512 字节或元素大小的倍数）
中控器 map 是一个 T** 数组，每个元素指向一段缓冲区
头尾都可以 O(1) 插入删除（只要当前缓冲区还有空间）
两端扩容时只需要分配新的缓冲区，不需要移动所有元素

迭代器设计复杂：需要维护当前缓冲区位置、缓冲区首尾指针、中控器指针，支持跨缓冲区跳跃。

时间复杂度：

头尾 push/pop 均摊 O(1)
中间 insert/erase O(n)（但比 vector 好，因为只需要移动一端的元素）
随机访问 O(1)（但常数因子比 vector 大）

4.5 Stack 和 Queue

都是容器配接器（container adapter），底层默认用 deque 实现。

没有迭代器：不提供遍历功能，符合栈和队列的语义
Stack：LIFO，只有 push/pop/top
Queue：FIFO，只有 push/pop/front/back

也可以用 list 作为底层容器（模板参数指定）。

4.6 Heap（堆）

不是容器，是一组算法，底层用 vector + 完全二叉树的隐式表示（数组模拟树）。

四种算法：

push_heap：把最后一个元素向上调整（percolate up）
pop_heap：把根元素放到最后，把最后元素向下调整（percolate down）
sort_heap：反复 pop_heap，得到有序数组
make_heap：从乱序数组构建堆（从最后一个非叶节点开始向下调整）

默认是大顶堆（max-heap）。

4.7 Priority Queue

配接器，底层 = vector + heap 算法。默认大顶堆。

没有迭代器，只能访问顶部元素。

4.8 Slist（单向链表）

SGI 扩展，不在 C++ 标准中。单向链表，比 list 省空间（少一个指针），但功能受限。

特殊设计：insert_after / erase_after — 因为单向链表无法快速找到前一个节点，所以操作的是”当前节点的下一个”。

第5章关联式容器（Associative Containers）

5.1 树的导览

铺垫数据结构知识：二叉搜索树 → AVL 树 → 红黑树。

红黑树的 5 条规则：

每个节点非红即黑
根节点是黑色
红色节点的子节点必须是黑色（不能有连续红节点）
从根到 NULL 的每条路径上黑节点数目相同
NULL 节点视为黑色

红黑树的优势：插入/删除/查找都是 O(log n)，且通过旋转和变色维持平衡，最坏情况也不会退化。

5.2 RB-tree（红黑树）

SGI 所有标准关联式容器（set、map、multiset、multimap）的底层都是红黑树。

关键设计：

节点结构：color、parent、left、right、value
迭代器：中序遍历（in-order），所以关联式容器天然有序
insert_unique：不允许键值重复
insert_equal：允许键值重复

5.3 Set / Map / Multiset / Multimap

容器	键值关系	底层	可否重复
set	键 = 值	RB-tree	不可
map	键值对（pair）	RB-tree	键不可重复
multiset	键 = 值	RB-tree	可重复
multimap	键值对（pair）	RB-tree	键可重复

共同特点：

元素自动按 key 排序（中序遍历红黑树）
查找 O(log n)
插入删除 O(log n) + 平衡调整
map 的 operator[] 语义：key 不存在则插入默认值

5.4 Hashtable（哈希表）

SGI 扩展，不在 C++98 标准中（C++11 引入 unordered 系列）。

冲突处理：开链法（separate chaining），每个桶（bucket）挂一个链表。

关键参数：

bucket 数量：总是质数（优化哈希分布）
负载因子（load factor）：元素数 / bucket 数 > 1 时触发 resize，bucket 数翻倍到下一个质数
hash function：对整数类型直接取模，对字符串等有专门的哈希函数

5.5 hash_set / hash_map / hash_multiset / hash_multimap

底层用 hashtable 实现的关联式容器。

与 RB-tree 版本的对比：

查找平均 O(1)，最坏 O(n)（全冲突）
元素无序（不排序）
需要好的 hash 函数

第6章算法（Algorithms）

6.1 算法分类

质变算法（mutating）：会改变元素值/顺序

copy、fill、swap、sort、reverse、rotate、remove、replace、transform…

非质变算法（non-mutating）：不改变元素

find、count、search、for_each、equal、mismatch、min、max…

6.2 算法的泛化过程

从”针对特定数据结构的函数”进化到”针对迭代器的通用算法”——这就是泛型编程的本质。

6.3 数值算法 `<stl_numeric.h>`

算法	作用
`accumulate`	累加（可指定初值和操作）
`adjacent_difference`	相邻差分
`inner_product`	内积（点积）
`partial_sum`	部分和（前缀和）
`power`	快速幂（SGI 扩展，用二分法幂运算）
`itoa`	生成连续递增序列（SGI 扩展）

6.4 基本算法 `<stl_algobase.h>`

equal、fill、fill_n、iter_swap、lexicographical_compare、max/min、mismatch、swap。

重点：copy 算法的极致优化：

输入输出都是随机访问迭代器 → 按块复制
输入是 const char*/wchar_t* → 直接 memmove
输出是 char*/wchar_t* → 直接 memmove
POD 类型 → memmove
非 POD 类型 → 逐元素赋值

层层特化、层层优化，无所不用其极，这就是工业级库的水准。

6.5 Set 相关算法

set_union、set_intersection、set_difference、set_symmetric_difference

前提：两个输入区间都必须已排序。时间复杂度 O(m+n)。

6.6 其他重要算法

算法	说明	时间复杂度
`sort`	混合排序（ introsort = quicksort + heapsort + insertion sort ）	O(n log n)
`stable_sort`	归并排序，稳定	O(n log n)
`partial_sort`	部分排序（堆排序思想）	O(n log k)，k 是前 k 个
`nth_element`	第 n 小元素（快速选择思想）	平均 O(n)
`binary_search`	二分查找	O(log n)
`lower_bound` / `upper_bound`	第一个 ≥ / > target 的位置	O(log n)
`equal_range`	等于 target 的区间	O(log n)
`merge`	归并两个有序区间	O(m+n)
`inplace_merge`	原地归并	O(n) ~ O(n log n)
`reverse`	反转区间	O(n)
`rotate`	旋转区间	O(n)，三种实现策略
`next_permutation` / `prev_permutation`	下一个/上一个排列	O(n)
`random_shuffle`	随机打乱	O(n)
`for_each`	对每个元素执行操作	O(n)
`find` / `find_if`	线性查找	O(n)
`count` / `count_if`	计数	O(n)
`search`	子串查找	O(m*n)

sort 的设计：SGI 的 sort 是 Introsort（内省排序）：

默认用快速排序（递归深度不大时）
递归深度超过 log₂n 阈值时，切换到堆排序（避免最坏情况 O(n²)）
子区间长度 < 阈值（通常 16）时，停止排序，最后用插入排序收尾（小数组插入排序更快）

这是多种算法结合、扬长避短的典范。

第7章仿函数（Functors）

仿函数就是重载了 operator() 的类对象，可以像函数一样被调用。比函数指针更灵活，可以保存状态，可以被配接。

7.1 可配接的关键

仿函数要能被 STL 配接器（bind2nd、not1 等）操作，必须定义自己的型别：

unary_function<Arg, Result>：一元仿函数的基类，定义 argument_type 和 result_type
binary_function<Arg1, Arg2, Result>：二元仿函数的基类，定义 first_argument_type、second_argument_type、result_type

这是 traits 编程思想的延伸——通过继承获得统一的型别定义。

7.2 算术类仿函数

plus、minus、multiplies、divides、modulus、negate

7.3 关系运算类仿函数

equal_to、not_equal_to、greater、less、greater_equal、less_equal

less<T> 是最常用的，几乎所有关联式容器和排序算法默认都用 it。

7.4 逻辑运算类仿函数

logical_and、logical_or、logical_not

7.5 证同、选择、投射

identity：返回自身（set 中 key=value 时用）
select1st / select2nd：取 pair 的第一个/第二个元素（map 中取 key/value 时用）
project1st / project2nd：忽略第二个/第一个参数，返回第一个/第二个

这些看似简单的”工具仿函数”，是 STL 组件灵活组合的关键。

第8章配接器（Adapters）

配接器是一种设计模式：把一个接口转换成另一个接口，让原本不兼容的类可以合作。

8.1 分类

容器配接器（container adapters）：stack、queue，把 deque 等容器包装成特定语义
迭代器配接器（iterator adapters）：insert iterators、reverse iterators、stream iterators
仿函数配接器（functor adapters）：bind2nd、not1、compose1 等

8.2 迭代器配接器

Insert Iterators（插入迭代器）：

back_insert_iterator（绑定 push_back）→ back_inserter()
front_insert_iterator（绑定 push_front）→ front_inserter()
insert_iterator（绑定 insert）→ inserter()

把”赋值”操作转化为”插入”操作。算法输出到插入迭代器时，元素自动被插入到容器中。

Reverse Iterators（反向迭代器）：

把 ++ 变成 —，把 — 变成 ++
注意：反向迭代器的”当前元素”是其内部正向迭代器的前一个元素（为了保持前闭后开区间的一致性）
base() 成员函数可以获取对应的正向迭代器

Stream Iterators（流迭代器）：

istream_iterator：把输入流包装成输入迭代器
ostream_iterator：把输出流包装成输出迭代器
可以直接把算法和 I/O 流连起来

8.3 仿函数配接器

配接器	作用
`not1` / `not2`	对返回值取反（一元/二元）
`bind1st` / `bind2nd`	绑定第一个/第二个参数，把二元仿函数变成一元
`compose1` / `compose2`	函数合成（SGI 扩展）
`ptr_fun`	把函数指针包装成可配接的仿函数
`mem_fun` / `mem_fun_ref`	把成员函数指针包装成仿函数

这些配接器是函数式编程思想在 C++ 中的早期体现。C++11 之后被 lambda 和 std::bind 取代，但理解它们的设计对理解泛型编程思想很有帮助。

附录

附录A：参考书籍与推荐读物（泛型思维理论基础 + STL 实务应用）
附录B：侯捷网站导引
附录C：STLport 的移植经验（孟岩）— Borland C++Builder 5 / VC++ 6.0

核心思想总结

1. 泛型编程（Generic Programming）

STL 的灵魂。不是面向对象（OOP），而是泛型编程——用模板让算法和数据结构独立于具体类型，用迭代器让算法独立于具体容器。

“发现算法的共性，抽象出最小依赖，让同一个算法可以操作最大范围的类型。“

2. 分层设计 + 组合优于继承

六大组件各司其职，通过迭代器和仿函数连接。组合的灵活性远大于继承。

3. 零开销抽象（Zero-Cost Abstraction）

STL 的抽象几乎没有运行时开销：

模板 = 编译期生成代码，没有虚函数开销
traits = 编译期型别分发，没有运行时判断
内联函数消除函数调用开销
POD 类型特化直接走 memcpy，比手写循环还快

4. 内存管理哲学

把内存配置和对象构造分开（allocate + construct）
小内存用内存池管理，减少 malloc 开销和碎片
POD 类型走最快路径

5. 约定优于配置

迭代器的 5 种型别、前闭后开区间、迭代器分类等级… 这些是 STL 世界的”契约”，遵守约定的组件可以自由组合。

与其他笔记的关联

《Effective STL》-50条有效使用STL的经验-Scott-Meyers — STL 使用层面的最佳实践
《C++ Coding Standards》-101条编码规范-Herb-Sutter-Andrei-Alexandrescu.md — C++ 编码规范，包含 STL 使用规范
《Modern C++ Design》-现代C++设计-Andrei-Alexandrescu — 更高级的 Policy-Based Design，泛型编程的进阶
《From Mathematics to Generic Programming》-从数学到泛型编程-Stepanov-Rose — STL 之父 Stepanov 的泛型编程思想源头
《Functional Programming in C++》-Ivan-Cukic — 函数式编程，仿函数/配接器思想的延伸与现代化
《高效程序的奥秘》-Hacker-s-Delight-Henry-S-Warren — 位操作级别的优化技巧，与 STL 底层优化精神相通
《A Tour of C++》-第二版-Bjarne-Stroustrup — 现代 C++ 全景，包含 STL 概览
《The C++ Programming Language》-第四版-Bjarne-Stroustrup — C++ 圣经，STL 是其标准库核心

阅读建议

第一遍：通读第1-3章，理解 STL 整体架构和 traits 技法
第二遍：选最感兴趣的 2-3 个容器（推荐 vector、list、deque），对着源码一步步读
第三遍：读算法章，重点关注 sort、copy、rotate 这几个”算法设计教科书”级别的实现
实践：尝试自己实现一个简单的 STL 容器或算法，比如写一个 vector 或者自己的 allocator

侯捷说：STL 学习有三重境界——会用、明理、能扩展。这本书带你从第一重直贯第二重，渐达第三重。

知识库

探索

STL源码剖析