STL空间配置器

stl_construct.h 本文定义了全局函数construct()和destroy()，负责对象的结构和分析。

stl_alloc.h文件中定义了一、二级配置器，相互合作，配置器称为alloc.

stl_uninitialized.h 这里定义了填充的一些全局函数(fill)或复制(copy)大量内存数据也属于STL标准规划。

在stl_alloc.h中定义了两级配置器，主要思路是申请大内存池，小内存直接从内存池中申请，不够的时候申请新内存池，大内存直接申请。

第一级配置器在申请空间大于128字节时被调用，第一级配置器不使用operator::new和operator::直接调用malloc/freee和delete申请空间realloc，并实现了类似c++中new-handler的机制。所谓c++ new handler机制是，当内存配置需求不能满足时，可以要求系统调用指定函数。换句话说，一旦:operator::new无法完成任务，丢失std::bad在_alloc异常状态之前，将首先调用客户端指定的处理例程，通常称为new-handler.new-handler有一个特定的解决内存的模式。

SGI一级配置器的allocate()和realloc都是在调用malloc和realloc失败后重新调用oom_malloc()和oom_realloc()后两者都有内循环，不断调用“内存不足处理例程”，希望在调用后获得足够的内存，顺利完成任务。但是，如果客户没有设置“内存不足处理例程”，oom_malloc()和oom_realoc调用_THROW_BAD_ALLOC, 输出bad_alloc异常信息，或使用exit(1)硬生生中止程序。

在stl_alloc.在h定义的二级配置器中，如果块足够大，超过128字节，则移交给一级配置器。

当块小于128字节时，内存池管理，也称为分层配置，每次配置大块内存，并维护相应的自由链表(free-list)。下次，如果有相同大小的内存需求，请直接从fre-list中拔出。如果客户释放小块，配置器将回收到fre-lists。此外，配置器还负责配置和回收。

为了便于管理，SGI二级配置器将主动将任何小块的内存需求提高到8倍。并维护16个freee-lists，各自的管理规模分别为8、16、24、32、40、48、56、64、72、88、96、104， 112，120，128 字节的小块。

当申请小于等于128字节时，将检查相应的freee list，如果free-list中有可用的块，直接拿走。如果没有，准备为相应的freee-list 重新填充空间。新空间将从内存池中取出，缺少20个新节点。如果内存池不足（足以超过一个节点），则返回相应的节点数量。如果内存池中的节点尺寸不够，请申请一个新的内存池，尺寸为2*total_bytes+ROUND_UP(heap_size>>4)，totoal_bytes 申请的空间大小，ROUND_UP调整为8倍数，heap_size是目前总申请内存池的大小。如果内存池申请成功，将原内存池中剩余的空间分配给适当的freee-list.万一山穷水尽，整个system heap空间不够(以至于无法将源头活水注入内存池)，malloc()如果行动失败，你会四处寻找是否有未使用的块，而且块足够大 “之free lists.找到了就挖一块交出，如果找不到，请调用一级配置器。第一级配置器实际上使用malloc来配置内存。事实上，一级配置器也使用malloc来配置内存。但它有outt。-of-memory处理机制(类似于new-handler机制)可能有机会在这里释放其他内存使用。若能成功，否则发出bad_alloc异常。

隐藏在这些容器后的内存管理是通过STL提供的默认allocator实现的。当然，用户也可以定制自己的allocator，只要实现allocator模板定义的接口方法，然后将自定义的allocator作为模板参数传输给STL容器，创建使用自定义allocator的STL容器对象，如:

stl::vector<int, UserDefinedAllocator> array;

在大多数情况下，STL默认的allocator就足够了。这个allocator是一个由两级分配器组成的内存管理器。当申请的内存大于128byte时，启动一级分配器通过malloc直接分配到系统的堆空间。如果申请的内存大小小于128byte，启动二级分配器，从预分配的内存池中取一个内存交付给用户。由8~128byte)的空闲列表组成，alllocator将根据申请内存的大小(roundyte的大小) up成8倍数)从相应的空闲块列表中取表头块给用户。

(1)快速分配小对象。

小对象从内存池分配，内存池是系统调用malloc分配一个足够大的区域备用程序，当内存池耗尽到系统申请一个新区域，整个过程类似于批发和零售，首先由allocator批发一定数量的商品，然后零售给用户，与总经营商品零售给用户的过程相比，显然很快。当然，当这里出现问题时，内存池会带来一些内存浪费。例如，当只分配一个小对象时，可能需要为这个小对象申请一个大的内存池，但这种浪费仍然是值得的。此外，这种情况在实际应用中并不常见。 (2)避免产生内存碎片。

程序中小对象的分配容易造成内存碎片，给操作系统的内存管理带来很大压力。系统中碎片的增加不仅会影响内存分配的速度，还会大大降低内存的利用率。从系统的角度来看，内存池组织小对象的内存只是一个大的内存池，看不到小对象内存的分配和释放。 实现时，allocator需要维护存储16个空闲块列表头的数组free_list，数组元素i指向块大小为8*(i+1)字节空闲块列表的表头，指向内存池起始地址的指针start_freee和指向结束地址的指针end_free。空闲块列表节点结构如下：