1、STL六大组件
STL（Standard Template Library）是C++的标准模板库。主要作用是为了建立数据结构和算法的一套标准，并且降低其间的耦合（coupling）关系以 提升各自的独立性、弹性、交互操作性（相互合作性，interoperability），C++社 群里诞生了 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）：行为类似函数，可作为算法的某种策略。从实作的角度看，仿函数是一种重载了operator()的class或class template。
5、配接器（adapters）：一种用来修饰容器（containers）或仿函数（functors） 或迭代器（iterators）接口的东西。例如 STL 提供的 $queue$ 和 $stack$，虽然看似容器，其实只能算是一种容器配接器，因为它们的底部完全借重 $deque$，所有动作都由底层的 $deque$供应。改变functor接口者，称 为function adapter，改变container接口者，称为container adapter，改变 iterator界面者，称为iterator adapter。
6、配置器（allocators）：负责空间配置与管理。从实作的角度看， 配置器是一个实现了动态空间配置、空间管理、空间释放的 class template。
2、空间配置器
2.1 什么是空间配置器
空间配置器就是用来配置、管理和释放空间的，给所有的容器包括算法提供生存空间。
作用：
（1）提高代码复用率，功能模块化。
（2）减少内存碎片问题。
（3）提高内存分配的效率。
（4）有内存不足时的应对措施。
（5）隐藏实际中对存储空间的分配及释放细节，确保所有被分配的存储空间都最终获得释放。
（5）考虑多线程状态。
考虑到小型区块可能导致的内存碎片问题，设置了两级空间配置器。分别为：一级空间配置器、二级空间配置器。当区块大于128字节，调用一级空间配置器；小于等于128字节，为了降低额外开销，用底层较复杂的二级空间配置器。
2.2 SGI STL专属空间配置器
以下介绍的是 SGI STL 提供的配置器，配置的对象是内存 。
虽然标准 SGI 也配置了 allocatalor，但是它自己并不使用，原因是效率比较差。
SGI STL 的每一个容器都指定缺省的空间配置器是 alloc，当我们调用 new 和 delete 进行对象的创建和销毁的时候，也同时会有内存配置操作和释放操作。
一般而言，我们所习惯的 C++ 内存配置动作和释放动作是这样：
class Foo { ... };
Foo* pf = new Foo;//配置内存，然后建构对象
delete pf; //将对象解构，然后释放内存
即new和delete同时包含两阶段操作，new的两阶段操作如下：
(1)调用::operator new配置内存。
(2) 调用Foo::Foo()构造对象内容。
delete操作：
(1)调用 Foo::~Foo()将对象析构。
(2)调用::operator delete释放内存。
而为了精密分工，STL allocator将这两阶段动作区分开来。内存配置动作由alloc:allocate()负责，内存释放动作由alloc::deallocate()负责；对象构造动作由::construct()负责，对象析构动作由::destroy()负责。
STL配置器头文件如下图所示（截自STL源码剖析）：
2.3 构造和析构函数：construct()和 destroy()
construct()接受一个指针p和一个初值value，此函数的用途就是将初值设定到指针所指的空间上。
destroy()有两个重载版本，第一个版本接受一个指针，直接调用该对象的析构函数即可将其析构掉。第二个版本接受first和last两个迭代器，将[first,last)范围内的析构掉。
2.4 内存的配置与释放：std::alloc
对象构造前的空间配置，和对象析构后的空间释放，由<stl_alloc.h>负责，SGI 对此的设计原则如下：
向 system heap要求空间。
考虑多绪（multi-threads）状态。
考虑内存不足时的应变措施。
考虑过多「小型区块」可能造成的内存破碎（fragment）问题。
考虑小型内存块所可能造成的内存破碎问题，SGI 设计了双层级配置器。
第一级配置器直接使用 malloc()和free()。
第二级配置器则视情况采用不同的策略： 当配置区块超过128bytes，视之为“足够大”，便调用第一级配置器；当配置区块小于 128bytes，视之为“过小”，为了降低额外负担便采用复杂的memory pool整理方式，而不再求助于第一级配置器。
# ifdef __USE_MALLOC
...
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;//令 alloc为第一级配置器
# else
...
//令 alloc 为第二级配置器
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
#endif /* ! __USE_MALLOC */
一二级配置器关系见下图：
2.5 第一级配置器 __malloc_alloc_template 剖析
喜欢看源码的同学，可以去《STL源码剖析》一书详读具体源码，本小节只罗列几个要点。
（1）第一级配置器以malloc()， free()，realloc()等C语言函数执行实际的内存配置、释放、重配置动作，并实作出类似 C++的new-handler机制（不能直接运用 C++ new-handler机制，因为它并非使用::operatornew来配置）。 所谓 C++ new handler 机制是：你可以要求系统在内存配置需求无法被满足时， 调用一个你所指定的函数。换句话说一旦::operator new无法达成任务，在丢出std::bad_alloc异常状态之前，会先呼叫由客端指定的处理例程。
（2）SGI 第一级配置器的allocate() 和realloc()在调用malloc() 和realloc()不成功后，改调用oom_malloc()和oom_realloc()。后两者都有内循环，不断调用“内存不足处理例程”，期望在某次调用之后，获得足够的内存而圆满达成任务。但如果“内存不足处理例程”并未被客端设定， oom_malloc()和oom_realloc() 便调用__THROW_BAD_ALLOC， 丢出bad_alloc异常信息，或利用exit(1)中止程序。
2.6 第二级配置器 __default_alloc_template 剖析
第二级配置器设计了许多机制，避免太多”小区块“造成内存的破碎。小区块带来的不仅是内存破碎，还有配置时的额外负担。 因为系统要配置额外的空间来管理内存，并且区块越小，额外负担所占的比例就越大从而浪费资源。如下图所示：
为了解决上述问题，SGI第二级配置器的作法是，如果区块大小超过 128 bytes，就移交给第一级配置器处理。当区块小于 128 bytes，则以内存池（memory pool）管理，此法又称为次层配置（sub-allocation）：
每次配置一大块内存，并维护对应的自由链表（freelist）。下次若再有相同大小的内存需求，就直接从free-lists中取出。如果客端释放了小区块，就由配置器回收到free-lists中（配置器除了负责配置，也负责回收）。为了方便管理，SGI第二级配置器将区块的内存大小上调至8的倍数（例如客端要求 30 bytes，就自动调整为 32 bytes），并维护 16 个 free-lists，各自管理大小分别为 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128 bytes的小区块。
free-lists 的节点结构如下：
union obj {
union obj * free_list_link;
char client_data[1]; /* The client sees this. */
};
诸君或许会想，为了维护链表（lists），每个节点需要额外的指针（指向下一个节点），这不又造成额外负担吗？你的顾虑是对的，但早已有好的解决办法。没错，用的是union共用体！共用体表示几个变量共用一个内存位置，在不同的时间保存不同的数据类型和不同长度的变量。一物二用的结果是，不会为了维护链表所必须的指针而造成内存的另一种浪费。 在 union obj 中，从第一个字段看，obj 可以看做一个指针，指向链表中的下一个节点；从第二个字段看，obj 可以也看做一个指针，不过此时是指向实际的内存区。
2.7 空间配置函数allocate（）
allocate()：此函数首先判断内存区块大小，大于 128 bytes 就调用第一级配置器，小 于 128 bytes 就检查对应的 free list。如果free list有可用的区块，就直接拿来用，如果没有可用区块，就将区块大小上调至 8 倍数边界，然后调用refill()， 为 free list 重新填充空间。过程如下图所示：
2.8 空间释放函函数deallocate()
deallocate()：此函数首先判断内存区块大小，大于 128 bytes 就调用第一级配置器， 小于 128 bytes 就找出对应的 free list，将区块回收。过程如下图所示：
2.9 重新填充 free lists
回头讨论先前说过的 allocate()。当它发现free list中没有可用区块了，就调用 refill() 为free list重新填充 空间 。 新的空间取自内存池 （经由chunk_alloc()完成）。预设取得20个新节点（新区块），但万一内存池空间不足，获得的节点数（区块数）可能小于 20。
2.10 内存池（memory pool）
从内存池中取空间给free list使用，是 chunk_alloc()的工作：chunk_alloc()函数以end_free - start_free 来判断内存池的“水量”。 如果水量充足，就直接取出 20 个区块传回给 free list。如果水量不足以提供 20 个 区块，但还足够供应一个以上的区块，就拨出这不足20个区块的空间出去。这时候其pass by reference 的 nobjs 参数将被修改为实际能够供应的区块数。如果内存池连一个区块空间都无法供应，对客端显然无法交待，此时便需利用malloc() 从 heap 中配置内存，为记忆池注入活水源头以应付需求。新水量的大小为需求量的两倍，再加上一个随着配置次数增加而愈来愈大的附加量。
3、结语
STL源码博大精深，本人虽然参考了STL源码剖析以及许多优秀博客，但是难免有疏漏之处，还望大家指正！
参考文献：《STL源码剖析》等
