读<深入浅出STL>之内存管理
毕业以后，已经很少有大块连续的时间读书了，因为工作需要，STL是必备的技能之一，所以就抽空看了看侯捷老师的<深入浅出STL>，不敢说了解的有多细致，但是有一点自己的体会，这里也做一些总结，供以后自己回顾；倘若有幸能够给你带来一丝的帮助，也算是一件幸事儿。
SGI STL中效率问题考虑的很周全，这个思想始终贯穿STL的设计，自然内存管理这块是所有容器的基础，也会有很合理的设计。STL中内存的分配分为两个层次，一个外衣。两个层次：_malloc_alloc_template和_default_alloc_template；一个外衣：simple_alloc。两个层次分别实际负责内存的分配，区别下文详细介绍；一个外衣，负责和容器关联起来。这句话非常重要，刚看代码的时候有些细节没有注意到，后来看到容器的源码以后，才发现这个外衣的重要作用。
两个层次的区别：_malloc_alloc_template负责大于128byte的内存分配，是直接调用的malloc申请内存，free释放内存；而_simple_alloc_template负责不大于128bytes的内存分配。
_malloc_alloc_template的源码见图书p57，源码非常的简短，这里就不再罗列，说说里面的几个重要函数就可以了：负责分配内存的函数有：static void* allocate(size_t n)和static void* reallocate(void *p, size_t n, size_t new_size)；前一个函数调用C中的malloc( n )函数，返回一个void*的指针，如果成功申请到内存，那么就返回给客户端；如果申请失败，那么就调用oom_allocate()函数，该函数用调用用户设置的异常处理函数（利用的函数指针的方式实现，如果内存没有申请到内存，客户可以指定异常处理机制，如果不指定，那么毫不客气地抛出bad_alloc的异常）；后一个函数调用realloc（void *p, size_t new_size），也只是简单的封装，如果申请成功就返回给客户端，如果失败就调用oom_realloc(p, new_size)，该函数也会调用用户指定的异常处理函数。至于用户的指定的异常处理函数一般是去释放全局内存资源，让malloc函数可以重新获得到内存资源供客户端使用。
是不是很简单呢，确实是这样，这个就是一级内存分配器，整个代码很简单，不过这里最重要的就是，有内存不足情况下，异常处理机制的。这点很重要，因为二级内存分配器当内存不足的情况下，最后也会调用一级内存分配器，当然这是后话，那时自然也会调用这里的异常处理机制。
_default_alloc_template的源码见图书p61，这个内存分配器就相对比较复杂了。首先，二级内存分配器对外提供的内存是由内存池管理的，由变量static char* start,和static char* end指向内存池的头和尾；其次，二级内存分配器为了避免由于分配大量小内存，而导致的内存黑洞问题，采用了内存块分级策略，即只能分配8,16,24,32……128，都是8的倍数，如果客户申请的内存大小不是8的倍数，二级内存分配器会将其上调到8的倍数，以方便管理。每一个自己实现过内存池的朋友都清楚，其中会有一个链表负责维护哪些节点已经使用，哪些节点在资源列表中仍然没有使用。STL中也是一样的，只不过因为采用了分级的策略（每一级只负责固定大小内存节点的维护），所以有多个链表各自维护自己节点的资源。节点的定义考虑了额外内存的负担，定义如下：
union obj{union obj* free_list_link;char client_data[1];};
struct obj{struct obj* free_list_link;char client_data[1];};是的，每个节点的定义就是union类型的，而不是我们正常情况下的struct，如果你细心就会发现，union无论何时都只占用4字节，而struct却要占用8字节，STL考虑资源的消耗甚至到了吝啬的地步，所以STL是低消耗的。关于二级内存分配器就不涉及到具体的函数细节了，因为里面的内容太多了，不过重要的函数还是会提到，只是定性地介绍其功能和原理，以及一些重要的数据存储，而不从代码出发分析其代码实现。二级内存分配器中重要的一些存储如下：
enum {__ALIGN = 8 };enum {__MAX_BYTES = 128 };enum {__NFREEELISTS = __ALIGN / __NFREEELISTS};static obj* volatile free_list[__NFREEELISTS];static char* start_free;static char* end_free;static size_t heap_size;
第一个__ALIGH是指最小的存储单元大小，__MAX_BYTES指最大负责的存储单元，__NFREEELISTS指一共负责多少种节点的存储；free_list保存的就是指向各种链表的表头节点，也就是说free_list[0]负责维护8bytes节点的链表，free_list[1]负责维护16bytes节点的链表等等。所有的这些节点申请资源都是要从内存池中获取，内存池就是由start_free 和 end_free维护的，分别指向内存池的起始位置和结束位置。如果各个节点链表需要新的空闲节点加入到链表中，就要从start_free和end_free维护的内存块中去申请内存。
客户端使用二级分配器分配内存时调用static void* allocate(size_t n)函数去分配内存：判断n>128为真的话，直接调用malloc_alloc::allocate(n)去分配内存；否则从free_list对应的节点链表中拿一个节点给客户端使用，如图所示（图是直接截的侯捷老师书中的图）,图中清晰的显示出来如何从free_list中拿到对应字节数的节点单元。
当然，如果上述过程中对应的节点链表中如果没有节点，那怎么办呢？它会调用refill(size_t n)函数，该函数又调用chunk_alloc(size_t size, int & nobjs)函数，让其负责从内存池中为该节点链表补充新的节点。从这里我们可以理解函数的定义原则：每一个函数尽可能的功能单一，代码简介明了，难道不是嘛？我们试着回顾一下：对外接口allocate(size_t n)负责判断客户需要的内存大小是否是_default_allocate的责任：如果不是转给_malloc_alloc，否则负责从对应节点链表中拿出一个节点给客户端。当然对应的节点链表中可能已经没有剩余的节点了，再呼叫refill(size_t n)函数去申请新的节点。这个就是allocate全部负责的责任，是不是很清晰呢？ 而refill(size_t n)函数调用chunk_alloc(size_t size, int & nobjs)负责具体从内存池中申请多块内存节点（因为从内存池中取出节点是个复杂的功能，所以需要一个专门的函数负责），而自己做外围的控制工作：把申请到的内存节点合理的安插到对应的节点链表中，并且给客户端返回一个节点，供客户端使用。这就是refill()函数的功能，也很清晰，对不对？最后就是chunk_alloc(size_t size, int & nobjs)函数，如前文介绍的，专门负责对应链表节点的申请功能，并把实际申请到的节点个数返回给refill()函数，为其决策控制提供依据。你马上就会知道为什么需要一个专门的函数去负责申请节点了，因为其足够复杂！过程如下：
伪代码如下：
if( BytesOfMemoryPool > 20 * BytesOfNode)//内存池中的资源大于20块内存节点
{obj* start_node = start_free;start_free += 20*BytesOfNode;return start_node;}else if( BytesOfMemoryPool > BytesOfNode)//不足20块，但是大于1块{obj* start_node = start_free;int objNum = BytesOfMemoryPool / BytesOfNode;start_free += objNum * BytesOfNode;return start_node;}else{distributeBytesOfMemoryPoolToList;//把剩下的内存资源分配到对应的节点链表中}get bytes from heap to fill the memory pool by malloc();if has no any bytes //堆上没有多余的内存，内存池中已经补充不了内存了{put the node from the list which BytesOfNode is more than bytes required to the memory pool //从大于要求字节数的节点链表中删除一个节点，以补充内存池资源chunk_alloc();}if the list also has no any bytes {_malloc_alloc::allocate( bytes) //调用一级内存分配器给内存池补充水源，这里如果也申请不到内存，用调用用户的异常处理函数chunk_alloc();}
挺复杂吧？ 哈哈，不要害怕，其实很容易理解的，慢慢看流程，很清晰的。到此为止二级内存分配的过程就介绍完了。而释放内存就非常的简单了，客户端调用deallocate(void * p, size_t n)去释放内存：如果n大于128，还记得吗，当时申请内存的时候调用的是一级内存分配器分配的，所以这里也交给一级内存分配器去释放；否则负责放到对应节点的链表中。如果所示：
好了，上面的所有内容已经把2级内存分配完全介绍完了，后面的内容就是那个外衣了，还记得吗，很简单，但是很重要，下面我们看看其真实面貌。
template<class _Tp, class _Alloc>class simple_alloc {public: static _Tp* allocate(size_t __n) { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); } static _Tp* allocate(void) { return (_Tp*) _Alloc::allocate(sizeof (_Tp)); } static void deallocate(_Tp* __p, size_t __n) { if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); } static void deallocate(_Tp* __p) { _Alloc::deallocate(__p, sizeof (_Tp)); }};这个类是直接和容器交互的类，模板中_Alloc 可以是_malloc_alloc 也可以是_default_alloc，这个要具体看是否定义了 define __USE_MALLOC，如果定义了默认就使用_malloc_alloc，否则相反。其allocate(size_t n)中的参数是元素的个数，而不是具体需要的内存大小；而容器中需要申请内存的时候就直接告诉simple_alloc需要多少个，而不需要自己计算需要多少bytes,这个就是simple_alloc的作用，屏蔽了容器和内存分配器的接口不一致，是不是很简单方便呢？除此以外再没有其他的作用，整个类的全部代码就这么一点，想必大家已经清楚了。这些内容对应的SG_STL的源码是stl_alloc.h文件中，我的资源中有对应的源码，有需要的m我，我发给大家。
好了，到此为止，STL的内存分配已经总结完了，相信你对如何分配内存已经有了一个大致的映像了。如有什么不足，欢迎大家拍砖。