STL——分配器

operator new 和 malloc

分配器就是STL中底层的内存管理结构，在真正学习allocators前，需要了解下operator new() 和 malloc函数。

由源代码可知，operator new()最终调用的是malloc()函数，即使用malloc进行内存分配。malloc的大致内存操作如右上图所示，分配为size大小的内存，实际上还有额外的开销，即除蓝色以外的部分，这会造成资源的浪费，分配的字节越小浪费的比例越大，分配的子节越大，浪费的比例越小。当然这是不可避免的，若想减小这些额外开销，需要尽量少调用malloc函数。

VC6底层的allocator实现

底层实现也很简单，需要注意的只有两个内存管理函数，allocate和deallocate，它们的底层实现也很简单，就是调用new和delete两个函数。

BC5底层的allocator实现

实现方式也和VC底层的实现没什么区别

GCC2.9底层的allocator实现

乍一看也是没什么区别，但是在实际调用时不是使用的这种实现。
以上三种底层实现，在分配小对象时会造成大量的资源浪费，因此就产生一种新的内存管理方式，使用两级分配器组成。当申请的内存大小大于128byte时，就启动第一级分配器通过malloc直接向系统的堆空间分配，如果申请的内存大小小于128byte时，就启动第二级分配器，从一个预先分配好的内存池中取一块内存交付给用户，这个内存池由16个不同大小（8的倍数，8~128byte）的空闲列表组成，allocator会根据申请内存的大小（将这个大小round up成8的倍数）从对应的空闲块列表取表头块给用户。这种做法有两个优点：

• 小对象的快速分配。小对象是从内存池分配的，这个内存池是系统调用一次malloc分配一块足够大的区域给程序备用，当内存池耗尽时再向系统申请一块新的区域，整个过程类似于批发和零售，起先是由allocator向总经商批发一定量的货物，然后零售给用户，与每次都总经商要一个货物再零售给用户的过程相比，显然是快捷了。当然，这里的一个问题时，内存池会带来一些内存的浪费，比如当只需分配一个小对象时，为了这个小对象可能要申请一大块的内存池，但这个浪费还是值得的，况且这种情况在实际应用中也并不多见。
• 避免了内存碎片的生成。程序中的小对象的分配极易造成内存碎片，给操作系统的内存管理带来了很大压力，系统中碎片的增多不但会影响内存分配的速度，而且会极大地降低内存的利用率。以内存池组织小对象的内存，从系统的角度看，只是一大块内存池，看不到小对象内存的分配和释放。

上图是小对象内存的分配。

小结

STL中的内存分配器实际上是基于空闲列表(free list)的分配策略，最主要的特点是通过组织16个空闲列表，对小对象的分配做了优化。

1）小对象的快速分配和释放。当一次性预先分配好一块固定大小的内存池后，对小于128字节的小块内存分配和释放的操作只是一些基本的指针操作，相比于直接调用malloc/free，开销小。

2）避免内存碎片的产生。零乱的内存碎片不仅会浪费内存空间，而且会给OS的内存管理造成压力。

3）尽可能最大化内存的利用率。当内存池尚有的空闲区域不足以分配所需的大小时，分配算法会将其链入到对应的空闲列表中，然后会尝试从空闲列表中寻找是否有合适大小的区域，

但是，这种内存分配器局限于STL容器中使用，并不适合一个通用的内存分配。因为它要求在释放一个内存块时，必须提供这个内存块的大小，以便确定回收到哪个free list中，而STL容器是知道它所需分配的对象大小的，