本文内容主要来自以下资料：
STL源码剖析—侯捷
STL空间配置器那点事
STL空间配置器
一、六大组件简单介绍
1.容器（Containers）：各种数据结构，如：vector、list、deque、set、map。用来存放数据。从实现的角度来看，STL容器是一种class template。
2.算法（algorithms）：各种常用算法，如：sort、search、copy、erase。从实现的角度来看，STL算法是一种 function template。
3.迭代器（iterators）：容器与算法之间的胶合剂，是所谓的“泛型指针”。共有五种类型，以及其他衍生变化。从实现的角度来看，迭代器是一种将 operator*、operator->、operator++、operator- - 等指针相关操作进行重载的class template。所有STL容器都有自己专属的迭代器，只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
4.仿函数（functors）：行为类似函数，可作为算法的某种策略（policy）。从实现的角度来看，仿函数是一种重载了operator（）的class或class template。一般的函数指针也可视为狭义的仿函数。
5.配接器（adapters）；一种用来修饰容器、仿函数、迭代器接口的东西。例如：STL提供的queue 和 stack，虽然看似容器，但其实只能算是一种容器配接器，因为它们的底部完全借助deque，所有操作都由底层的deque供应。改变 functors接口者，称为function adapter；改变 container 接口者，称为container adapter；改变iterator接口者，称为iterator adapter。
6.配置器（allocators）：负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。
二、STL内存空间配置器
1.STL空间配置器产生的缘由：
在软件开发，程序设计中，我们不免因为程序需求，使用很多的小块内存（基本类型以及小内存的自定义类型）。在程序中动态申请，释放。
这个过程过程并不是一定能够控制好的，于是乎，
问题1：就出现了内存碎片问题。（ps外碎片问题）
问题2：一直在因为小块内存而进行内存申请，调用malloc，系统调用产生性能问题。
注：内碎片：因为内存对齐/访问效率（CPU取址次数）而产生 如 用户需要3字节，实际得到4或者8字节的问题，其中的碎片是浪费掉的。
外碎片：系统中内存总量足够，但是不连续，所以无法分配给用户使用而产生的浪费。
2.实现策略
1).考虑到小型区块所可能造成的内存破碎问题，设计了双层级配置器。
当配置区块超过128bytes时，调用第一层级配置器，第一层级配置器直接使用malloc()和free()．
当配置区块小于128bytes时，调用第二层级配置器，采用复杂的memory pool整理方式，降低额外开销．
2).内存池管理方式是每次配置一大块内存，并维护对应之*链表．
若有相同大小的内存分配，就直接从*链表中分配内存块．
若内存释放时，则由配置器回收到*链表中．
第二级配置器会主动将任何小额区块的内存需求量调至8的倍数．
3).*链表(free-list)节点的结构如下：
利用union的特性，从第一字段观之，obj可被视为一个指针，指向相同形式的另一个obj．
从第二字段观之，obj可被视为一个指针，指向实际区块．
一物二用，不会为了维护链表所必须的指针而造成内存的一种浪费．
具体代码实现，请参考STL源码．下面附几张图说明．
第一级配置器与第二级配置器之间的关系：
第二级配置器分配内存时，*链表变化示意图：
第二级配置器分配内存时，其具体步骤如下：
1).判断内存块大小，是否大于128bytes，若大于，则调用第一级配置器．若小于，进行步骤2).
2).从16个*链表中，根据内存块大小选择合适的*链表．
3).判断*链表是否为空，若为空，则重新真充*链表，否则，进行步骤4).
4).调整当前*链表指向一块内存块，并返回当前的内存块．(类似于链表的删除操作)
第二级配置器释放内存时，*链表变化示意图：
第二级配置器释放内存时，其具体步骤如下：
1).判断内存块大小，是否大于128bytes，若大于，则调用第一级配置器．若小于，进行步骤2).
2).从16个*链表中，根据内存块大小选择合适的*链表．
3).调整当前*链表回收当前的内存块．(类似于链表的插入操作)
内存池的实际操作结果示意图：
内存池管理：
1).三个变量来标识内存池的使用情况和大小，start_free,end_free,heap_size.
2).当free list中没有可用的区块时，新空间取自内存池，缺省取得20个新节点，主要分三种情况进行．
- a.内存池剩余空间完全满足需求量，则直接修改start_free的值，返回对应的区块．
- b.内存池剩余空间不能完全满足需求量，但足够供应一个(含)以上的区块，则减少分配的区块数目，然后分配．
- c.内存池剩余空间连一个区块的大小都无法提供，则利用malloc从heap中配置内存空间．
若malloc成功，则修改start_free,end_free,heap_size，然后递归调用自身，重新分配区块．
若malloc不成功，则寻找*链表中，看是否存在足够大的区块．
若存在，则将对应区块作为内存池，调整start_free,end_free，递归调用自身，重新分配区块． 若不存，则调用第一级配置器。第一级适配器也是调用malooc( )来配置内存，但它有out-of-memory处理机制，或许有机会释放其它的内存拿来此处使用。如果可以就成功，否则发出bad_alloc异常。
三、空间配置器的遗留问题
1、发现问题
二级空间配置器中的空间重头到尾都没看到他归还给系统。那么问题就是，内存池空间何时释放？
对于这个问题，在回头浏览一下源码及结构图，你就会发现
大于128的内存，客户程序Deallocate之后会调free释放掉，归还给了系统。
但是呢……………
内存池中获取的空间，最终，假定用户都调用Dealloc释放调了，那么他们又在哪里呢？
没有还给系统，没有在内存池，在*链表中。
Got it：程序中不曾释放，只是在*链表中，且配置器的所有方法，成员都是静态的，那么他们就是存放在静态区。释放时机就是程序结束。
2.如果需要释放，那么应该怎么处理呢？
因为真正可以在程序运行中就归还系统的只有*链表中的未使用值，但是他们并不一定是连续的（用户申请空间，释放空间顺序的不可控制性），所以想要在合适时间（eg一级配置器的handler中释放，或者设置各阀值，分配空间量到达时处理），就必须保证释放的空间要是连续的。保证连续的方案就是：跟踪分配释放过程，记录节点信息。释放时，仅释放连续的大块。
3.关于STL空间配置器的效率考究
既然已经存在，而又被广泛使用，那么，整体的效率，以及和STL内部容器之间的使用配合还是没问题的。
我们考虑几种情况：
a. 用户只需要无限的char类型空间，然而配置器中却对齐到8，于是乎，整个程序中就会有7/8的空间浪费。
b.对于假定用户申请N次8空间，将系统资源耗到一定程度，然后全部释放了，*链表中的空间都是连续的。却没有释放。
但是：用户需要申请大于8的空间时，却依旧没有空间可用。
总之：这个问题就是，空间可能全部积攒在小块*链表中，却没有用户可用的。这就尴尬了。