STL 源码剖析 PDF 文档

Question

2000 年下半，我开始为计划中的《泛型思维》一书陆续准备并热身。为了对泛型编程技术以及 STL 实作技术有更深的体会，以便在讲述整个 STL 的架构与应用时更能虎虎生风，我常常深入到 STL 源码去刨根究底。2001/02 的某一天，我突然有所感触：既然花了大把精力看过 STL 源码，写了眉批，做了整理，何不把它再加㆒点功夫，形成一个更完善的面貌后出版？对我个人而言，一份注解详尽的 STL源码，价值不扉；如果我从中获益，一定也有许多人能够从中获益。

这样的念头使我极度兴奋。剖析大架构本是侯捷的拿手，这个主题又可以和《泛型思维》相呼应。于是我便一头栽进去了。

我选择 SGI STL 做为剖析对象。这份实作版本的可读性极佳，运用极广，被选为 GNU C++ 的标准程式库，又开放自由运用。愈是细读 SGI STL 源码，愈令我震惊抽象思考层次的落实、泛型编程的奥妙、及其效率考量的绵密。不仅最为人广泛运用的各种资料结构（data structures）和演算法（algorithms）在 STL中有良好的实现，连记忆体配置与管理也都重重考虑了最佳效能。一切的一切，除了实现软体积木的高度复用性，让各种组件（components）得以灵活搭配运用，更考量了实用㆖的关键议题：效率。

目录

庖丁解牛（侯捷自序） i
目录 v
前言 xvii
本书定位 xvii
合适的读者 xviii
最佳阅读方式 xviii
我所选择的剖析对象 xix
各章主题 xx
编译工具 xx
中英术语的运用风格 xxi
英文术语採用原则 xxii
版面字形风格 xxiii
源码形式与下载 xxiv
线㆖服务 xxvi
推荐读物 xxvi
第 1 章 STL 概论与版本简介 001
1.1 STL 概论 001
1.1.1 STL 的历史 003
1.1.2 STL 与 C++ 标准程式库 003
1.2 STL 六大组件 — 功能与运用 004
1.3 GNU 源码开放精神 007
1.4 HP STL 实作版本 009
1.5 P.J. Plauger STL 实作版本 010
1.6 Rouge Wave STL 实作版本 011
1.7 STLport 实作版本 012
1.8 SGI STL 实作版本 总览 013
1.8.1 GNU C++ header 档案分佈 014
1.8.2 SGI STL 档案分佈与简介 016
STL 标准表头档（无副档名） 017
C++ 标准规格定案前，HP 规范的 STL 表头档（副档名 .h） 017
SGI STL 内部档案（SGI STL 真正实作于此） 018
1.8.3 SGI STL 的组态设定（configuration） 019
1.9 可能令你困惑的 C++ 语法 026
1.9.1 stl_config.h ㆗的各种组态 027
组态 3：static template member 027
组态 5：class template partial specialization 028
组态 6：function template partial order 028
组态 7：explicit function template arguments 029
组态 8：member templates 029
组态 10：default template argument depend on
previous template parameters 030
组态 11：non-type template parameters 031
组态：bound friend template function 032
组态：class template explicit specialization 034
1.9.2 暂时物件的产生与运用 036
1.9.3 静态常数整数成员在 class 内部直接初始化 037
in-class static const integral data member initialization
Partial Specialzation（偏特化）的意义 086
1.9.4 increment/decrement/dereference 运算子 037
1.9.5 前闭后开 区间表示法 [ ) 039
1.9.6 function call 运算子（operator()） 040
第 2 章 空间配置器（allocator） 043
2.1 空间配置器的标准介面 043
2.1.1 设计一个阳春的空间配置器，JJ::allocator 044
2.2 具备次配置力（sub-allocation）的 SGI 空间配置器 047
2.2.1 SGI 标准的空间配置器，std::allocator 047
2.2.2 SGI 特殊的空间配置器，std::alloc 049
2.2.3 建构和解构基本工具：construct() 和 destroy() 051
2.2.4 空间的配置与释放，std::alloc 053
2.2.5 第一级配置器 __malloc_alloc_template 剖析 056
2.2.6 第二级配置器 __default_alloc_template 剖析 059
2.2.7 空间配置函式 allocate() 062
2.2.8 空间释放函式 deallocate() 064
2.2.9 重新充填 free-lists 065
2.2.10 记忆池（memory pool） 066
2.3 记忆体基本处理工具 070
2.3.1 uninitialized_copy 070
2.3.2 uninitialized_fill 071
2.3.3 uninitialized_fill_n 071
第 3 章 迭代器（iterators）概念与 traits 编程技法 079
3.1 迭代器设计思维 — STL 关键所在 079
3.2 迭代器是㆒种 smart pointer 080
3.3 迭代器相应型别（associated types） 084
3.4 Traits 编程技法 — STL 源码门钥 085
3.4.1 迭代器相应型别之㆒ value_type 090
3.4.2 迭代器相应型别之㆓ difference_type 090
3.4.3 迭代器相应型别之㆔ pointer_type 091
3.4.4 迭代器相应型别之㆕ reference_type 091
3.4.5 迭代器相应型别之五 iterator_category 092
3.5 std::iterator class 的保证 099
3.6 iterator 相关源码整理重列 101
3.7 SGI STL 的私房菜：__type_traits 103
第 4 章 序列式容器（sequence containers） 113
4.1 容器概观与分类 113
4.1.1 序列式容器（sequence containers） 114
4.2 vector 115
4.2.1 vector 概述 115
4.2.2 vector 定义式摘要 115
4.2.3 vector 的迭代器 117
4.2.4 vector 的资料结构 118
4.2.5 vector 的建构与记忆体管理：constructor, push_back 119
4.2.6 vector 的元素操作：pop_back, erase, clear, insert 123
4.3 list 128
4.3.1 list 概述 128
4.3.2 list 的节点（node） 129
4.3.3 list 的迭代器 129
4.3.4 list 的资料结构 131
4.3.5 list 的建构与记忆体管理：constructor, push_back, insert 132
4.3.6 list 的元素操作：push_front, push_back, erase, pop_front, 136
pop_back, clear, remove, unique, splice, merge, reverse, sort目 录
The Annotated STL Sources
4.4 deque 143
4.4.1 deque 概述 143
4.4.2 deque 的㆗控器 144
4.4.3 deque 的迭代器 146
4.4.4 deque 的资料结构 150
4.4.5 deque 的建构与记忆体管理 ：ctor, push_back, push_front 152
4.4.6 deque 的元素操作：pop_back, pop_front, clear, erase, insert 161
4.5 stack 167
4.5.1 stack 概述 167
4.5.2 stack 定义式完整列表 167
4.5.3 stack 没有迭代器 168
4.5.4 以 list 做为 stack 的底层容器 168
4.6 queue 169
4.6.1 queue 概述 169
4.6.2 queue 定义式完整列表 170
4.6.3 queue 没有迭代器 171
4.6.4 以 list 做为 queue 的底层容器 171
4.7 heap（隐性表述，implicit representation） 172
4.7.1 heap 概述 172
4.7.2 heap 演算法 174
push_heap 174
pop_heap 176
sort_heap 178
make_heap 180
4.7.3 heap 没有迭代器 181
4.7.4 heap 测试实例 181
4.8 priority-queue 183STL 源码剖析
The Annotated STL Sources
4.8.1 priority-queue 概述 183
4.8.2 priority-queue 定义式完整列表 183
4.8.3 priority-queue 没有迭代器 185
4.8.4 priority-queue 测试实例 185
4.9 slist 186
4.9.1 slist 概述 186
4.9.2 slist 的节点 186
4.9.3 slist 的迭代器 188
4.9.4 slist 的资料结构 190
4.9.5 slist 的元素操作 191
第 5 章 关联式容器（associated containers） 197
5.1 树的导览 199
5.1.1 ㆓元搜寻树（binary search tree） 200
5.1.2 平衡㆓元搜寻树（balanced binary search tree） 203
5.1.3 AVL tree（Adelson-Velskii-Landis tree） 203
5.1.4 单旋转（Single Rotation） 205
5.1.5 双旋转（Double Rotation） 206
5.2 RB-tree（红黑树） 208
5.2.1 安插节点 209
5.2.2 ㆒个由㆖而㆘的程序 212
5.2.3 RB-tree 的节点设计 213
5.2.4 RB-tree 的迭代器 214
5.2.5 RB-tree 的资料结构 218
5.2.6 RB-tree 的建构与记忆体管理 221
5.2.7 RB-tree 的元素操作 223
元素安插动作 insert_equal 223
元素安插动作 insert_unique 224目 录
The Annotated STL Sources
真正的安插执行程序 __insert 224
调整 RB-tree（旋转及改变颜色） 225
元素的搜寻 find 229
5.3 set 233
5.4 map 237
5.5 multiset 245
5.6 multimap 246
5.7 hashtable 247
5.7.1 hashtable 概述 247
5.7.2 hashtable 的桶子（buckets）与节点（nodes） 253
5.7.3 hashtable 的迭代器 254
5.7.4 hashtable 的资料结构 256
5.7.5 hashtable 的建构与记忆体管理 258
安插动作（insert）与表格重整（resize） 259
判知元素的落脚处（bkt_num） 262
複制（copy_from）和整体删除（clear） 263
5.7.6 hashtable 运用实例（find, count） 264
5.7.7 hash functions 268
5.8 hash_set 270
5.9 hash_map 275
5.10 hash_multiset 279
5.11 hash_multimap 282
第 6 章 演算法（algorithms） 285
6.1 演算法概观 285
6.1.1 演算法分析与複杂度表示 O( ) 286
6.1.2 STL 演算法总览 288
6.1.3 mutating algorithms — 会改变操作对象之值 291STL 源码剖析
The Annotated STL Sources
6.1.4 nonmutating algorithms — 不改变操作对象之值 292
6.1.5 STL 演算法的㆒般型式 292
6.2 演算法的泛化过程 294
6.3 数值演算法 <stl_numeric.h> 298
6.3.1 运用实例 298
6.3.2 accumulate 299
6.3.3 adjacent_difference 300
6.3.4 inner_product 301
6.3.5 partial_sum 303
6.3.6 power 304
6.3.7 itoa 305
6.4 基本演算法 <stl_algobase.h> 305
6.4.1 运用实例 305
6.4.2 equal 307
fill 308
fill_n 308
iter_swap 309
lexicographical_compare 310
max, min 312
mismatch 313
swap 314
6.4.3 copy，强化效率无所不用其极 314
6.4.4 copy_backward 326
6.5 Set 相关演算法（应用于已序区间） 328
6.5.1 set_union 331
6.5.2 set_intersection 333
6.5.3 set_difference 334
6.5.4 set_symmetric_difference 336
6.6 heap 演算法：make_heap, pop_heap, push_heap, sort_heap 338
6.7 其他演算法 338目 录
The Annotated STL Sources
6.7.1 单纯的资料处理 338
adjacent_find 343
count 344
count_if 344
find 345
find_if 345
find_end 345
find_first_of 348
for_each 348
generate 349
generate_n 349
includes （应用于已序区间） 349
max_element 352
merge （应用于已序区间） 352
min_element 354
partition 354
remove 357
remove_copy 357
remove_if 357
remove_copy_if 358
replace 359
replace_copy 359
replace_if 359
replace_copy_if 360
reverse 360
reverse_copy 361
rotate 361
rotate_copy 365
search 365
search_n 366
swap_ranges 369
transform 369
unique 370
unique_copy 371
6.7.2 lower_bound （应用于已序区间） 375
6.7.3 upper_bound （应用于已序区间） 377
6.7.4 binary_search （应用于已序区间） 379
6.7.5 next_permutation 380
6.7.6 prev_permutation 382
6.7.7 random_shuffle 383STL 源码剖析
The Annotated STL Sources
6.7.8 partial_sort / partial_sort_copy 386
6.7.9 sort 389
6.7.10 equal_range（应用于已序区间） 400
6.7.11 inplace_merge（应用于已序区间） 403
6.7.12 nth_element 409
6.7.13 merge sort 411
第 7 章 仿函式（functor，另名 函式物件 function objects） 413
7.1 仿函式（functor）概观 413
7.2 可配接 （adaptable） 的关键 415
7.1.1 unary_function 416
7.1.2 binary_function 417
7.3 算术类（Arithmetic）仿函式 418
plus, minus, multiplies, divides, modulus, negate,
identity_element
7.4 相对关係类（Relational）仿函式 420
equal_to, not_equal_to, greater, greater_equal, less, less_equal
7.5 逻辑运算类（Logical）仿函式 422
logical_and, logical_or, logical_not
7.6 证同（identity）、选择（select）、投射（project） 423
identity, select1st, select2nd, project1st, project2nd
第 8 章 配接器（adapter） 425
8.1 配接器之概观与分类 425
8.1.1 应用于容器，container adapters 425
8.1.2 应用于迭代器，iterator adapters 425
运用实例 427
8.1.3 应用于仿函式，functor adapters 428
运用实例 429目 录
The Annotated STL Sources
8.2 container adapters 434
8.2.1 stack 434
8.2.1 queue 434
8.3 iterator adapters 435
8.3.1 insert iterators 435
8.3.2 reverse iterators 437
8.3.3 stream iterators (istream_iterator, ostream_iterator) 442
8.4 function adapters 448
8.4.1 对传回值进行逻辑否定：not1, not2 450
8.4.2 对参数进行繫结（绑定）：bind1st, bind2nd 451
8.4.3 用于函式合成：compose1, compose2（未纳入标准） 453
8.4.4 用于函式指标：ptr_fun 454
8.4.5 用于成员函式指标：mem_fun, mem_fun_ref 456
附录 A 参考资料与推荐读物（Bibliography） 461
附录 B 侯捷网站简介 471
附录 C STLport 的移植经验（by 孟岩） 473
索引 481

下载地址：https://www.wenjiangs.com/wp-content/uploads/2022/11/WK2sj90hW4KTgBhH.zip