STL源码剖析

庖丁解牛（侯捷自序）

目录

前言

本书定位

合适的读者

最佳阅读方式

我所选择的剖析对象

各章主题

编译工具

中英术语的运用风格

英文术语采用原则

版面字形风格

源码形式与下载

在线服务

推荐读物

第1章 STL 概论与版本简介

1.1 STL 概论

1.1.1 STL的历史

1.1.2 STL与C++ 标准程序库

1.2 STL 六大组件 - 功能与运用

1.3 GNU源码开放精神

1.4 HP STL实现版本

1.5 P.J. Plauger STL实现版本

1.6 Rouge Wave STL实现版本

1.7 STLport 实现版本

1.8 SGI STL实现版本 总览

1.8.1 GNU C++ header 文件分布

1.8.2 SGI STL 文件分布与简介

STL 标准头文件（无扩展名）

C++ 标准规格定案前，HP规范的STL头文件（扩展名 .h）

SGI STL 内部文件（SGI STL真正实现于此）

1.8.3 SGI STL 的组态设定（configuration）

1.9可能令你困惑的C++ 语法

1.9.1 stl_config.h 中的各种组态

组态3：static template member

组态5：class template partial specialization

组态6：function template partial order

组态7：explicit function template arguments

组态8：member templates

组态10：default template argument depend on previous template parameters

组态11：non-type template parameters

组态：bound friend template function

组态：class template explicit specialization

1.9.2 临时对象的产生与运用

1.9.3 静态常数整数成员在class 内部直接初始化

in-class static const integral data member initialization

1.9.4 increment/decrement/dereference 运算子

1.9.5 "前闭后开"区间表示法 [ )

1.9.6 function call运算子（operator()）

第2章 空间配置器（allocator）

2.1 空间配置器的标准接口

2.1.1 设计一个简单的空间配置器，JJ::allocator

2.2 具备次配置力（sub-allocation）的SGI 空间配置器

2.2.1 SGI 标准的空间配置器，std::allocator

2.2.2 SGI 特殊的空间配置器，std::alloc

2.2.3 构造和析构基本工具：construct() 和 destroy()

2.2.4 空间的配置与释放，std::alloc

2.2.5 第一级配置器 __malloc_alloc_template 剖析

2.2.6 第二级配置器 __default_alloc_template剖析

2.2.7 空间配置函数allocate()

2.2.8 空间释放函数deallocate()

2.2.9 重新充填free-lists

2.2.10 内存池（memory pool）

2.3 内存基本处理工具

2.3.1 uninitialized_copy

2.3.2 uninitialized_fill

2.3.3 uninitialized_fill_n

第3章 迭代器（iterators）概念与 traits 编程技法 079

3.1 迭代器设计思维 - STL关键所在

3.2 迭代器是一种 smart pointer

3.3 迭代器相应型别（associated types）

3.4 Traits 编程技法 - STL源码门钥

Partial Specialzation（偏特化）的意义

3.4.1 迭代器相应型别之一value_type

3.4.2 迭代器相应型别之二difference_type

3.4.3 迭代器相应型别之三pointer_type

3.4.4 迭代器相应型别之四reference_type

3.4.5 迭代器相应型别之五iterator_category

以advanced() 为例

消除 "单纯传递调用函数"

以distance() 为例

3.5 std::iterator class 的保证

3.6 iterator相关源码完整重列

3.7 SGI STL的私房菜：__type_traits

第4章 序列式容器（sequence containers）

4.1 容器概观与分类

4.1.1 序列式容器（sequence containers）

4.2 vector

4.2.1 vector 概述

4.2.2 vector 定义摘要

4.2.3 vector 的迭代器

4.2.4 vector 的数据结构

4.2.5 vector 的构造与内存管理：constructor, push_back

4.2.6 vector 的元素操作：pop_back, erase, clear, insert

4.3 list

4.3.1 list 概述

4.3.2 list 的节点（node）

4.3.3 list 的迭代器

4.3.4 list 的数据结构

4.3.5 list 的构造与内存管理：constructor, push_back, insert

4.3.6 list 的元素操作：push_front, push_back, erase, pop_front,

pop_back, clear, remove, unique, splice, merge, reverse, sort

4.4 deque

4.4.1 deque 概述

4.4.2 deque 的中控器

4.4.3 deque 的迭代器

4.4.4 deque 的数据结构

4.4.5 deque 的构造与内存管理 ：ctor, push_back, push_front

4.4.6 deque 的元素操作：pop_back, pop_front, clear, erase, insert

4.5 stack

4.5.1 stack 概述

4.5.2 stack 定义式完整列表

4.5.3 stack 没有迭代器

4.5.4 以list 做为stack 的底层容器

4.6 queue

4.6.1 queue 概述

4.6.2 queue 定义式完整列表

4.6.3 queue 没有迭代器

4.6.4 以list 做为queue 的底层容器

4.7 heap（隐式表述，implicit representation）

4.7.1 heap 概述

4.7.2 heap 算法

push_heap

pop_heap

sort_heap

make_heap

4.7.3 heap 没有迭代器

4.7.4 heap 测试实例

4.8 priority-queue

4.8.1 priority-queue 概述

4.8.2 priority-queue 定义式完整列表

4.8.3 priority-queue 没有迭代器

4.8.4 priority-queue 测试实例

4.9 slist

4.9.1 slist 概述

4.9.2 slist 的节点

4.9.3 slist 的迭代器

4.9.4 slist 的数据结构

4.9.5 slist 的元素操作

第5章 关联式容器（associated containers）

5.1 树的导览

5.1.1 二元搜寻树（binary search tree）

5.1.2 平衡二元搜寻树（balanced binary search tree）

5.1.3 AVL tree（Adelson-Velskii-Landis tree）

5.1.4 单旋转（Single Rotation）

5.1.5 双旋转（Double Rotation）

5.2 RB-tree（红黑树）

5.2.1 插入节点

5.2.2 一个由上而下的程序

5.2.3 RB-tree 的节点设计

5.2.4 RB-tree 的迭代器

5.2.5 RB-tree 的数据结构

5.2.6 RB-tree 的构造与内存管理

5.2.7 RB-tree 的元素操作

元素插入动作 insert_equal

元素插入动作 insert_unique

真正的插入执行程序 __insert

调整RB-tree（旋转及改变颜色）

元素的搜寻 find

5.3 set

5.4 map

5.5 multiset

5.6 multimap

5.7 hashtable

5.7.1 hashtable 概述

线性探测（linear probing）

二次探测（quadratic probing）

分离链（separate chaining）

5.7.2 hashtable 的桶子（buckets）与节点（nodes）

5.7.3 hashtable 的迭代器

5.7.4 hashtable 的数据结构

5.7.5 hashtable 的构造与内存管理

插入动作（insert）与表格重整（resize）

判知元素的落脚处（bkt_num）

复制（copy_from）和整体删除（clear）

5.7.6 hashtable 运用实例（find, count）

5.7.7 hash functions

5.8 hash_set

5.9 hash_map

5.10 hash_multiset

5.11 hash_multimap

第6章 算法（algorithms）

6.1 算法概观

6.1.1 算法分析与复杂度表示 O( )

6.1.2 STL算法总览

6.1.3 mutating algorithms - 会改变操作对象之值

6.1.4 nonmutating algorithms - 不改变操作对象之值

6.1.5 STL算法的一般形式

6.2 算法的泛化过程

6.3 数值算法 <stl_numeric.h>

6.3.1 运用实例

6.3.2 accumulate

6.3.3 adjacent_difference

6.3.4 inner_product

6.3.5 partial_sum

6.3.6 power

6.3.7 itoa

6.4 基本算法 <stl_algobase.h>

6.4.1 运用实例

6.4.2 equal

fill

fill_n

iter_swap

lexicographical_compare

max, min

mismatch

swap

6.4.3 copy，强化效率无所不用其极

6.4.4 copy_backward

6.5 Set 相关算法（应用于有序区间）

6.5.1 set_union

6.5.2 set_intersection

6.5.3 set_difference

6.5.4 set_symmetric_difference

6.6 heap算法：make_heap, pop_heap, push_heap, sort_heap

6.7 其它算法

6.7.1 单纯的数据处理

adjacent_find

count

count_if

find

find_if

find_end

find_first_of

for_each

generate

generate_n

includes （应用于有序区间）

max_element

merge （应用于有序区间）

min_element

partition

remove

remove_copy

remove_if

remove_copy_if

replace

replace_copy

replace_if

replace_copy_if

reverse

reverse_copy

rotate

rotate_copy

search

search_n

swap_ranges

transform

unique

unique_copy

6.7.2 lower_bound （应用于有序区间）

6.7.3 upper_bound （应用于有序区间）

6.7.4 binary_search （应用于有序区间）

6.7.5 next_permutation

6.7.6 prev_permutation

6.7.7 random_shuffle

6.7.8 partial_sort / partial_sort_copy

6.7.9 sort

6.7.10 equal_range（应用于有序区间）

6.7.11 inplace_merge（应用于有序区间）

6.7.12 nth_element

6.7.13 merge sort

第7章 仿函数（functor，另名 函数对象function objects）

7.1 仿函数（functor）概观

7.2 可配接（adaptable）的关键

7.2.1 unary_function

7.2.2 binary_function

7.3 算术类（Arithmetic）仿函数

plus, minus, multiplies, divides, modulus, negate, identity_element

7.4 关系类（Relational）仿函数

equal_to, not_equal_to, greater, greater_equal, less, less_equal

7.5 逻辑运算类（Logical）仿函数

logical_and, logical_or, logical_not

7.6 证同（identity）、选择（select）、投射（project）

identity, select1st, select2nd, project1st, project2nd

第8章 配接器（adapter）

8.1 配接器之概观与分类

8.1.1 应用于容器，container adapters

8.1.2 应用于迭代器，iterator adapters

运用实例

8.1.3 应用于仿函数，functor adapters

运用实例

8.2 container adapters

8.2.1 stack

8.2.2 queue

8.3 iterator adapters

8.3.1 insert iterators

8.3.2 reverse iterators

8.3.3 stream iterators (istream_iterator, ostream_iterator)

8.4 function adapters

8.4.1 对传回值进行逻辑否定：not1, not2

8.4.2 对参数进行系结（绑定）：bind1st, bind2nd

8.4.3 用于函数合成：compose1, compose2（未纳入标准）

8.4.4 用于函数指针：ptr_fun

8.4.5 用于成员函数指针：mem_fun, mem_fun_ref

附录A 参考资料与推荐读物（Bibliography）

附录B 侯捷网站简介

附录C STLport 的移植经验（by 孟岩）

Borland C++Builder 5

Microsoft Visual C++ 6.0

索引