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        
索引