侯杰的《STL源码剖析》真的是一本太过晦涩的书（晦涩程度仅次于《深度探索C++对象模型》）。 晦涩来源于几个方面：

1. C++泛型编程本身的复杂性（比如traits等）；
2. 为了尽可能高的执行效率，STL源码中会做一些优化；
3. 侯杰先生的语言风格，以及书中大段大段的代码，的确让人不敢恭维。

不过好在书中干货很多，读后收获颇丰。本文旨在梳理星散在书中的各处要点，也算自己的读书心得。

空间配置器（allocator)

SGI空间配置器使用两级配置：第一级直接向操作系统申请，每次会申请一大块内存备用；第二级会根据需求， 把从一级配置器中得到的内存，分给调用方。二级配置器主要通过维护自由链表来管理小块内存。

空间配置器的工作就是减少直接向操作系统申请内存的次数，复用小块内存。

Traits

Traits是一种编程技巧，结合模板的特化、偏特化，用于获得类型相关信息。

在泛型编程时一个普遍的问题是，如何统一的处理C++中的两类类型：原生类型和class/struct。Traits正适合处理这类问题。 有关Traits的文章已经很多，可以参考这篇

序列式容器

vector和数组类似，当vector已满继续push时，会分配一块2倍大小的内存，然后把旧的数据拷贝过来，再释放旧的内存。 新分配的内存地址不必和原先的地址连续。

list本质是一个双链表。

deque是一个分段连续的容器，有点类似于vector，但是vector只能在尾部增长，而deque在头部和尾部都可以增长。 deque随机访问的能力比list好，但比vector差。

stack、queue是两个adapter，底层的实现有赖于list或者deque

priority_queue内部由一个heap实现，heap内元素按照优先级排列，顶端存放最大优先级的值。 取出操作复杂度O(1)，插入操作复杂度O(logN)。

slist单链表。

关联式容器

关联式容器底层都以红黑树（RB-tree）实现。RB-tree是二叉搜索树的升级版本，二叉搜索树如果处于不平衡状态时，效率会降低， 在极端情况下，就退化为一个链表，不利于查找。RB-tree在二叉搜索树的基础上，增加了新的约束条件：

1. 每个节点不是红色就是黑色；
2. 根节点是黑色；
3. 如果一个节点是红色，他的子节点必须是黑色；
4. 从任一节点至树尾端的任何路径，所含黑色节点数相同。

RB-tree从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，就很大程度的缓解了由于不平衡带来的性能降低。 插入元素时，先按照二叉搜索树的规则插入，然后检查是否满足RB-tree约束，如果不满足，通过调整节点颜色和 旋转树形，来让二叉树重新符合RB-tree约束。 查找，插入和删除等操作的复杂度都为O(logN)。

set的数据就直接存放在RB-tree的节点中。map的键和值组成一个pair存放在RB-tree的节点中。

hashtable一个开链哈希表。hash_set、hash_map、hash_multimap都是通过hashtable来实现。

algorithms、functors和adapters。