STL 源码剖析

. 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
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
partial specialzation（偏特化）的意义 086
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
以advanced() 为例 093
消除 "单纯传递调用函数" 097
以distance() 为例 098
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
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 183
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
真正的插入执行程序 __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
线性探测（linear probing） 249
二次探测（quadratic probing） 251
分离链（separate chaining） 253
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 - 会改变操作对象之值 291
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
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 383
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.2.1 unary_function 416
7.2.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
8.2 container adapters 434
8.2.1 stack 434
8.2.2 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
borland c++builder 5 474
microsoft visual c++ 6.0 477
索引 481

.　　 第5章 关联式容器（associated containers）
　　 第6章 算法（algorithms）
　　 第7章 仿函数或函数对象（functors, or function objects）
　　 第8章 配接器（adapter）
　　 编译工具
　　 本书主要探索SGI STL 源代码，并提供少量测试程序。如果测试程序只做标准的STL动作，不涉及SGI STL实现细节，那么我会在VC6、CB4、cygnus 2.91 for Windows等编译平台上分别测试它们。
　　 随着对SGI STL 源代码的掌握程度增加，我们可以大胆做些练习，将SGI STL 内部接口打开，或是修改某些STL组件，加上少量输出动作，以观察组件的运作过程。这种情况下，操练的对象既然是 SGI STL，我也就只使用GNU C++ 来编译[4]。
　　 中英术语的运用风格
　　 我曾经发表过一篇《技术引导乎 文化传承乎》的文章，阐述我对专业计算机书籍的中英术语运用态度。文章收录于侯捷网站http://www.jjhou.com/article99-14.htm。以下简单叙述我的想法。
　　 为了学术界和业界的习惯，也为了与全球科技接轨，并且也因为我所撰写的是供专业人士阅读的书籍而非科普读物，我决定适量保留专业领域中被朗朗上口的英文术语。朗朗上口与否，见仁见智，我以个人阅历做为抉择依据。
　　 做为一个并非以英语为母语的族裔，我们对英文的阅读困难并不在单字，而在整句整段的文意。做为一项技术的学习者，我们的困难并不在术语本身（那只是个符号），而在术语背后的技术意义。
　　 熟悉并使用原文术语，至为重要。原因很简单，在科技领域里，你必须与全世界接轨。中文技术书籍的价值不在于“建立本国文化”或“让它成为一本道地的中文书”或“完全扫除英汉字典的需要”。中文技术书籍的重要价值，在于引进技术、引导学习、扫平阅读障碍、增加学习效率。
　　 绝大部份我所采用的英文术语都是名词。但极少数动词或形容词也有必要让读者知道原文（我会时而中英并列，并使用斜体英文），原因是：
　　 l C++ 编译器的错误讯息并未中文化，万一错误讯息中出现以下字眼：unresolved, instantiated, ambiguous, override，而编写程序的你却不熟悉或不懂这些动词或形容词的技术意义，就不妙了。
　　 l 有些动作关系到 library functions，而 library functions的名称并未中文化J，例如 insert, delete, sort。因此视状况而定，我可能会选择使用英文。
　　 l 如果某些术语关系到语言关键词，为了让读者有最直接的感受与联想，我会采用原文，例如static, private, protected, public, friend, inline, extern。
　　 版面像一张破碎的脸？
　　 大量中英夹杂的结果，无法避免造成版面的 “破碎”。但为了实现合宜的表达方式，牺牲版面的 “全中文化”在所难免。我将尽量以版面手法来达到视觉上的顺畅，换言之我将采用不同的字形来代表不同属性的术语。如果把英文术语视为一种符号，这些中英夹杂但带有特殊字形的版面，并不会比市面上琳琅满目的许多应用软件图解使用手册来得突兀（而后者不是普遍为大众所喜爱吗J）。我所采用的版面，都已经过一再试验，获得许多读者的赞同。
　　 英文术语采用原则
　　 就我的观察，人们对于英文词或中文词的采用，隐隐有一个习惯：如果中文词发音简短（或至少不比英文词繁长）并且意义良好，那么就比较有可能被业界用于日常沟通；否则业界多半采用英文词。
　　 例如，polymorphism 音节过多，所以意义良好的中文词 “多态”就比较有机会被采用。例如，虚函数的发音不比 virtual function 繁长，所以使用这个中文词的人也不少。 “多载”或 “重载”的发音比 overloaded 短得多，意义又正确，用的人也不少。
　　 但此并非绝对法则，否则就不会有绝大多数工程师说 data member 而不说 “数据成员”、说 member function 而不说 “成员函数”的情况了。
　　 以下是本书采用原文术语的几个简单原则。请注意，并没有绝对的实践，有时候要看上下文情况。同时，容我再强调一次，这些都是基于我与业界和学界的接触经验而做的选择。
　　 编程基础术语，采用中文。例如：函数、指针、变量、常数。本书的英文术语绝大部份都与 C++/OOP/GP（Generic Programming）相关。
　　 简单而朗朗上口的词，视情况可能直接使用英文：input, output, lvalue, rvalue...
　　 读者有必要认识的英文名词，不译：template, class, object, exception, scope, namespace。
　　 长串、有特定意义、中译名称拗口者，不译：explicit specialization, partial specialization, using declaration, using directive, exception specialization。
　　 操作符名称，不译：copy assignment 操作符，member access 操作符，arrow 操作符，dot 操作符，address of 操作符，dereference 操作符...
　　 业界惯用词，不译：constructor, destructor, data member, member function, reference。
　　 涉及 C++ 关键词者，不译：public, private, protected, friend, static,
　　 意义良好，发音简短，流传颇众的译词，译之：多态（polymorphism），虚函数（virtual function）、泛型（genericity）…
　　 译后可能失掉原味而无法完全彰显原味者，中英并列。
　　 重要的动词、形容词，时而中英并列：模棱两可（ambiguous）, 决议（resolve）,覆盖（override），参数推导（argument deduced），具现化（instantiated）。
　　 STL专用术语：采用中文，如迭代器（iterator）、容器（container）、仿函数（functor）、配接器（adapter）、空间配置器（allocator）。
　　 数据结构专用术语：尽量采用英文，如 vector, list, deque, queue, stack, set, map, heap, binary search tree, RB-tree, AVL-tree, priority queue.
　　 援用英文词，或不厌其烦地中英并列，获得的一项重要福利是：本书得以英文做为索引凭借。
　　 http://www.jjhou.com/terms.txt列有我个人整理的一份英中繁简术语对照表。
　　 版面字型风格
　　 中文
　　 本文：细明 9.5pt
　　 标题：华康粗圆
　　 视觉加强：华康中黑
　　 英文
　　 一般文字，Times New Roman, 9.5pt，例如：class, object, member function, data member, base class, derived class, private, protected, public, reference, template, namespace, function template, class template, local, global
　　 动词或形容词，Times New Roman斜体9.5pt，例如：resolve, ambiguous, override, instantiated
　　 class名称，Lucida Console 8.5pt，例如：stack, list, map
　　 程序代码识别符号，Courier New 8.5pt，例如：int, min(SmallInt*, int)
　　 长串术语，Arial 9pt，例如：member initialization list, name return value, using directive, using declaration, pass by value, pass by reference, function try block, exception declaration, exception specification, stack unwinding, function object, class template specialization, class template partial specialization…
　　 exception types或iterator types或iostream manipulators，Lucida Sans 9pt，例如： bad_alloc, back_inserter, boolalpha
　　 操作符名称及某些特殊动作，Footlight MT Light 9.5pt，例如：copy assignment 操作符，dereference 操作符，address of 操作符，equality 操作符，function call 操作符，constructor, destructor, default constructor, copy constructor, virtual destructor, memberwise assignment, memberwise initialization
　　 程序代码，Courier New 8.5pt，例如：
　　 #include [iostream]
　　 using namespace std;
　　 要在整本书中维护一贯的字形风格而没有任何疏漏，很不容易，许多时候不同类型的术语搭配起来，就形成了不知该用哪种字形的困扰。排版者顾此失彼的可能也不是没有。因此，请注意，各种字形的运用，只是为了让您阅读时有比较好的效果，其本身并不具其它意义。局部的一致性更重于全体的一致性。
　　 源代码形式与下载
　　 SGI STL 虽然是可读性最高的一份STL源代码，但其中并没有对实现程序乃至于实现技巧有什么文字注释，只偶而在文件最前面有一点点总体说明。虽然其符号名称有不错的规划，真要仔细追踪源代码，仍然旷日费时。因此本书不但在正文之中解说其设计原则或实现技术，也直接在源代码中加上许多注释。这些注释皆以蓝色标示。条件式编译（#ifdef）视同源代码处理，函数调用动作以红色表示，嵌套定义亦以红色表示。classes名称、data members名称和member functions名称大多以粗体表示。特别需要提醒的地方（包括template 缺省参数、长度很长的嵌套定义式）则加上灰阶底纹。例如：
　　 template [class T, class Alloc = alloc] // 缺省使用 alloc 为配置器
　　 class vector {
　　 public:
　　 typedef T value_type;
　　 typedef value_type* iterator;
　　 ...
　　 protected:
　　 // vector采用简单的线性连续空间。以两个迭代器start和end分别指向头尾，
　　 // 并以迭代器end_of_storage指向容量尾端。容量可能比(尾-头)还大，
　　 // 多余的空间即备用空间。
　　 iterator start;
　　 iterator finish;
　　 iterator end_of_storage;
　　 void fill_initialize(size_type n, const T& value) {
　　 start = allocate_and_fill(n, value); // 配置空间并设初值
　　 finish = start + n; // 调整水位
　　 end_of_storage = finish; // 调整水位
　　 }
　　...
　　};
　　#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
　　template [class T, class Alloc]
　　inline void swap(vector[T, Alloc]& x, vector[T, Alloc]& y) {
　　 x.swap(y);
　　}
　　#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
　　又如：
　　
　　// 以下配接器用来表示某个 Adaptable Binary Predicate 的逻辑负值
　　template [class Predicate]
　　class binary_negate
　　 : public binary_function[typename Predicate::first_argument_type,
　　 typename Predicate::second_argument_type,
　　 bool] {
　　...
　　};
　　 这些作法可能在某些地方有少许例外（或遗漏），唯一不变的原则就是尽量设法让读者一眼抓住源代码重点。花花绿绿的颜色乍见之下或许不习惯，多看几眼你就会喜欢它J。这些经过注释的SGI STL源代码以 Microsoft Word 97文件格式，连同SGI STL源代码，置于侯捷网站供自由下载[5]。噢，是的，STL涵盖面积广大，源代码浩繁，考虑到书籍的篇幅，本书仅能就具代表性者加以剖析，如果你感兴趣的某些细节未涵盖于书中，可自行上网查阅这些经过整理的源代码文件。
　　 在线服务
　　 侯捷网站（网址见于封底）是我的个人网站。我的所有作品，包括本书，都在此网站上提供服务，包括：
　　 勘误和补充
　　 技术讨论
　　 程序代码下载
　　 电子文件下载
　　 附录B 对侯捷网站有一些导引介绍。
　　 推荐读物
　　 详见附录A。这些精选读物可为你建立扎实的泛型（Genericity）思维理论基础与扎实的STL实务应用能力。
　　--------------------------------------------------------------------------------
　　[1] 请参考Learning Standard C++ as a New Language, by Bjarne Stroustrup, C/C++ Users Journal 1999/05。中译文http://www.jjhou.com/programmer-4-learning-standard-cpp.htm
　　[2] The C++ Standard Template Library, by P.J.Plauger, Alexander Al. Stepanov, Meng Lee, David R. Musser, Prentice Hall 2001/03，与本书定位相近，但在表现方式上大有不同。
　　[3] 关于cygnus、GNU 源代码开放精神、以及自由软件基金会（FSF），请见1.3 节介绍。
　　[4] SGI STL 事实上是个高度可携产品，不限使用于GNU C++。从它对各种编译器的环境组态设定（1.8.3节）便可略知一二。网络上有一个 STLport 组织，不遗余力地将SGI STL 移植到各种编译平台上。请参阅本书附录C。
　　[5] 下载这些文件并不会引发版权问题。详见 1.3 节关于自由软件基金会（FSF）、源代码开放（open source）精神以及各种授权声明。
　　

.　　[1] 庄子养生主：“彼节间有间，而刀刃者无厚；以无厚入有间，恢恢乎其于游刃必有余地矣。”侯捷不让，以此自况。
　　 身为C++标准库最重要的组成部分，STL（标准模板库）不仅是一个可复用组件库，而且是一个包罗算法与数据结构的软件框架（framework）。“框架”这个词，本身就有庞大、稳定、完整而可扩展的涵义。软件框架，则是用一行行精细准确的源码，构造一个庞大、稳定、完整而可扩展的软件架构，稍有软件开发经验的人都知道，要做到这些，谈何容易！ STL在1994年走入C++标准，使得原本即将推出的C++标准延迟4年问世而无怨无悔，并为之对内容做巨幅改进，而今STL不仅为千千万万C++程序员所日常运用，而且获得极高的学术赞誉，成为了一个典范，一种境界。作为一个软件框架，STL所取得的成功，实在可以用“辉煌”来形容，其所内涵的软件思想和技术经验，更是无比的深厚与精致。
　　 学习编程的人都知道，阅读剖析名家代码乃是提高水平的捷径。源码之前，了无秘密，大师们的缜密思维，经验结晶，技术思路，独到风格，都原原本本地体现在源码之中。在你仔细推敲之中，迷惑不解之时，恍然大悟之际，你的经验、思维、视野、知识乃至技术品味都会获得快速的成长。特别是面对STL这样优秀而普遍的作品，无论你是为了满足作为程序员第二天性的求知欲，还是在日常工作中解决实际问题，总会有一天，你会打开一个叫做[vector]或者[algorithm]的头文件，想把STL背后的秘密看个究竟。英文里有一个常用短语，叫做“under the hood”，钻进魔术师的帐篷，屏住呼吸，瞪大眼睛，把那些奇妙的魔法看个通透，让自己的理解和技艺获得巨幅的提升，这种诱惑，任何一个程序员都无法抵挡！
　　 不过，想要研读STL源码，绝对没有那么简单。STL是精致的软件框架，是为优化效率而无所不用其极的艺术品，是数据结构与算法大师经年累月的智慧结晶，是泛型思想的光辉诗篇，是C++高级技术的精彩亮相，这些灿烂的赞誉，体现在数万行源码里，对于一个初涉此道的学习者来说，就是一个感觉：“难！”。无论你是会浅尝辄止地退出这次探险，还是勇敢地向浓雾中前进，当你受困于STL精致的大网之中，为那些迷一般的结构和动作感到茫然无措的时侯，所有人都会冒出一个念头：“如果有这样一本书，既能够提纲挈领，为我理顺思绪，指引方向，同时又能够照顾小节，阐述细微，帮助我更快更好地理解STL源码，那该有多好！”
　　 望着长长的STL著作列表，一个“真正”的C++程序员，多少会有一点遗憾。自从STL问世以来，出版了大量的书籍，帮助读者了解它的思想，学习它的用法，掌握它的技巧。其中佼佼者如Matt Austern的《Generic Programming and STL》，Nicolai Josuttis的《The C++ Standard Library》，Scott Meyers的《Effective STL》，已成C++经典名著。然而，定位在引导学习者进行STL源码分析的著作，可以说是凤毛麟角。毕竟，既要能高屋建瓴，剖析大架构，不为纷繁琐碎之细节而迷乱，又能具体而微，体现细致之处的精妙缜密，不因为宏大体系而失之粗略，无论对于专家高手还是技术作者，都是太难达到的目标。
　　 读了这本《STL源码剖析》之后，我认为，这个遗憾终于被补足了！
　　 本书的作者侯捷先生是蜚声海峡两岸的著名IT技术作家，在C++，Windows系统原理，泛型理论和STL等技术领域有极深的造诣。然而，侯先生最令人称道之处，乃是他剖析大架构的能力。所谓剖析大架构，就是要在洋洋洒洒数以万行计的源码中，精准定位，抽取核心观念，高屋建瓴，纲举目张，将看上去乱麻一般的源码梳理得头绪清晰，条理分明，同时又照顾细节，参透精微，把一个个关键动作阐述得通通透透，这种能力，我以为至少在华人技术作者中，侯先生堪执牛耳。在他的名作《深入浅出MFC》中，侯先生将自己这方面的能力展现得淋漓尽致，而在这本《STL源码剖析》中，我们又看到了一次更加精彩的表现。
　　 我有机会作为大陆最早的几个读者之一，详细拜读了侯先生的这本最新STL专著，感到了一种强烈的技术冲动，说得俗一点，就是觉得很过瘾！具体来说，我以为这本书至少有四大特点，使它成为我所见过的最出色的一本STL源码剖析类著作。
　　 首先，选材精当，立足高远。STL是一个标准，因而有各种实作版本。本书所剖析的SGI STL，可以说是设计最巧妙，思想最深刻，获得赞誉最盛，认同最广的STL实作。当然，这份出自STL之父Alex Stepanov，以及Matt Austern，David Musser等巨匠之手的经典作品，剖析阐述起来自然也需要花费更大的心力。侯先生籍其扎实的理论与技术素养，毅然选择这份作品来剖析，是需要极大勇气与自信的。同样，本书对读者的预期，也是很高的，不但要有扎实的基本功，更要有掌握STL的兴趣与坚韧意志。读这本书，你可以有充分的信心，学到的是超一流大师的思想和经验，所谓名门正派，高屋建瓴。
　　 其次，脉络清晰，组织顺序匠心独具。任何人打算系统阅读STL源码，所必须作出的第一个决定就是，从何处开始？我在初读此书时，一个最疑惑的地方就是候先生居然把allocator放在所有组件之前讲述。要知道，allocator这个东西，对一般的使用者完全透明，根本感觉不到其存在，以至于在名著《The C++ Standard Libaray》中，Nicolai Josuttis将这一部分放在全书最后。既然如此，又何必让这个无名小卒占据头版头条？我一开始还真是不理解。直到后来，我自己有一些扩展STL的实践，才发现，用的时候你固然可以对allocator不闻不问，但一旦要领悟STL的工作原理，或者要自己扩展STL的功能，则对于allocator的掌握几乎是第一先决条件。不了解allocator，则无论剖析也好，扩展也罢，必然处处碰壁。侯先生毫不迟疑，首先帮读者搬开这块绊脚石，理出头绪，实在是匠心独具。紧接着的第三章iterator及traits，直入STL的核心观念与关键技术，剑走中锋，直取要害，高举高打，开诚布公，直接把理解STL的钥匙交道读者手上。此章一过，读者神气完足，就可以大刀阔斧地打通STL的重重关隘。此布局只要稍有变化，读者的学习难度势必猛增。侯先生的此种安排，实在是大家手笔！
　　 此外，本书在技术上迎难而上，详略得当，完整而重点突出。了解SGI STL的读者都知道，这份作品对C++标准中的STL做了大量的扩充，增加了专用的高效allocator，用以操作巨型字符串的rope，单链表slist，以及万众企盼的hash容器等等，再加上STL本身就有很多精微之处，技术上的难点不少。此类书籍的作者，但凡稍有一丝懈怠之心，大可以冠冕堂皇地避重就轻。然而侯先生在此书中对重点难点毫不避讳，无论是标准功能还是非标准功能，只要对读者理解STL架构有益，只要有助于提高读者的技术，增长读者的视野与经验，书中必然不畏繁难，将所有技术细节原原本本和盘托出。另一方面，所谓剖析源码，其目的在于明理，解惑，提高自身水平，并不是要穷经皓首，倒背如流。因此，一旦道理讲清楚，书中就将重复与一般性的内容一笔带过，孰轻孰重，一目了然，详略十分得当，这一点对于提高读者的学习效率，有着巨大的意义。
　　 最后一点，本书通过大量生动范例和插图讲解基本思想，在同类书籍中堪称典范。虽然我把这一点放在最后，但我相信大部分读者站在书店，随手翻过这本书，得到的第一印象便是这一点。STL之所以为大家所津津乐道，除了其思想深刻之外，最大的因素是它实用。它所包装的，是算法与数据结构的基本功能。作为一个程序员，如果你是做数据库编程的，大可以不懂汇编语言，如果你是写驱动程序的，大可以不必通晓人工智能，写编译器的可以不用懂什么计算机图形学，操作系统内核高手的不用精通网站架设，然而，如果你不懂数据结构与算法的基础知识，不具备数据结构与算法的基本技能，那就完全丧失称为一个程序员的资格！市面上讲述算法与数据结构的专著汗牛充栋，俯拾皆是。相比之下，本书倒并不是以此为核心目标的。但是，可曾有哪位读者看到任何一本书象本书一样，将红黑树用一张张清晰生动的图解释得如此浅显易懂？所谓一图胜千言，在教授基本数据结构与算法方面，我想不出还有任何一种方法，能够比幻灯般的图片更生动更令人印象深刻了。读过此书的每一位读者，我想都会为书中那一副副插图所打动，作者细致严谨的作风，时刻为读者考虑的敬业精神，也许是更值得我们尊敬的东西。
　　 我非常荣幸有机会与侯先生和华中科技大学出版社的周筠女士再次合作，参与了这本书的繁简转译工作。在术语转译方面，我们基本上保持了与《Effective C++》相一致的标准。其中有一些术语不完全符合国内的习惯译法，下面是一个简单的对比表：
　　 英文术语
　　 大陆惯用译法
　　 本书译法
　　
　　adapter
　　 适配器
　　 配接器
　　
　　argument
　　 实参（实质参数）
　　 引数
　　
　　by reference
　　 传参考,传地址
　　 传址
　　
　　by value
　　 传值
　　 传值
　　
　　dereference
　　 反引用,解参考
　　 提领
　　
　　evaluate
　　 评估,计算
　　 评估, 核定
　　
　　instance
　　 案例,实例
　　 实体
　　
　　instantiated
　　 实例化
　　 实体化、具现化
　　
　　library
　　 库,函数库
　　 程序库
　　
　　range
　　 范围
　　 区间（使用于STL时）
　　
　　resolve
　　 解析
　　 决议
　　
　　parameter
　　 形参（形式参数）
　　 参数
　　
　　type
　　 类型
　　 型别
　　
　　 侯先生在一片影响颇为广泛的STL技术杂文中，将STL的学习境界划分为三个阶段，会用，明理，能扩展。阅读STL源码是由第一层次直贯第二层次，而渐达于第三层次的一条捷径，当然也是条荆棘之路。如果你是一个勇于征服险峰的程序员，如果你是一个希望了解under the hood之奥秘的程序员，那么当你在攀登STL这座瑰丽高山的时候，这本书会大大地帮助你。我非常热情地向您推荐这本著作。当然，再好的书籍只是工具，能不能成功，关键，在你自己。
　　 孟岩
　　 2002年4月于北京