一.理解new与delete
通常我们这样申请与释放C++内存
class Foo{…};
Foo* pf=new Foo();
delete pf;
在这段代码中,new包括3个过程。 1).调用operator new分配内存。 2).调用Foo::Foot()构造对象。 3).返回指针pf。同理,delete包括new相反的过程。1).调用Foo::~Foo()析构对象。2).调用operator::delete释放内存。
在分配好内存后，如何构造对象呢，答案是使用定位new(placement new)。
定位new形式如下(参见《C++ Primer》):
new (place_address) type
new (place_address) type (initializer)
new (place_address) type [size]
new (place_address) type {braced initializer-list}
因此，我们也就不难理解为什么有了malloc/free，还要new/delete了。
malloc/free是c/c++的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
对于非内部数据类型(例如自己定义的class)的对象而言，光用maloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。因此C++语言需要一个能完成动态内存分配和初始化工作的运算符new，以及一个能完成清理与释放内存工作的运算符delete。注意new/delete不是库函数。

二.构造与析构函数:construct()与destroy()
stl中construct()函数是通过定位new来构造对象,对于destroy()函数，分两种情况:
1).destroy函数参数为一指针,则直接调用其析构函数
2).destroy函数参数为两个迭代器first,last。将[first,last)范围内的所有对象析构掉,则首先判断该对象的析构函数是否为trivial destructor(若用户未定义析构函数，而是使用编译器隐式生成的析构函数，则说明此析构函数基本无用,称为trivial destructor)，若为trivial_destructor,则说明每个对象的析构函数都无关痛痒，为了效率考虑，可以直接跳过。若不是trivial destructor，则调用1)中的destory函数析构每个对象。

三.stl空间配置器的思想
stl空间配置器由3个文件实现。 stl_consturct.h,stl_alloc.h,stl_uninitialized.h。stl_construct.h文件定义了construct()以及destroy()，用于构造和析构函数。stl_alloc.h文件定义了allocate(),deallocate()，用于分配与释放内存。stl_uninitialized.h定义了uninitialized_copy等函数,用于大块内存的复制,填充。
stl_alloc.h定义了两级配置器，第 一级配置器直接调用malloc,free来分配和释放内存,它主要用于大块内存区域的分配与释放。第一级配置器可以指定自己的out-of-memory handler,若malloc失败，则调用此处理例程,并尝试再次malloc内存,直至成功，若未定义自己的out-of-memory handler，则直接抛出异常__THROW_BAD_ALLOC。
第二级适配器做法如下:首先判断要分配的块是否大于128 bytes,若大于128 bytes，则调用第一级配置器,否则使用内存池来管理，具体做法是每次malloc一大块内存，并维护对应的链表(free list)，将申请的内存，分3部分处理，第一部分返回给申请内存的客户端，第二部分由free list维护，第三部分由内存池维护。下次若再有相同大小的内存需要，则首先从free list中拨出(若是释放小块内存，则由free list回收)。若free list内存不足，则从内存池取空间，若内存池空间也不够，则再次malloc内存空间，若malloc空间失败，则查看是否有未用且区块足够大的free list,若有，则拿来用，否则调用第一级配置器，根据第一级配置器的out-of-memory处理例程来处理或者抛出bad_alloc异常。SGI第二级配置器将小额区块的内存需求量上调至8的倍数，并维护16个free list,各自管理大小分别为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128 bytes的小额区块。free list的节点结构如下:
union obj{
union obj* free_list_link;
char client_data[1];
}
采用union而非struct的原因是union更节省空间，否则每个节点还需要维护一个指针。可把free list看作数据结构中的链表,free_list_link指针指向下一个区块(注意区块大小为8的倍数)。
第二级适配器对于小块内存的分配有两种优点:
1).小块内存的快速分配,第二级适配器采用的是malloc一大块内存，并将其存储在free list以及内存池中,下次再分配小块内存时，可以直接从free list或内存池中取出适当大小的内存，这样可以减少malloc以及free的次数
2).避免太多小区块造成的内存的碎片。小额区块会带来额外的配置负担，同时也会降低内存的利用率。在系统的层面讲，它只能注意到malloc,free大块内存，对于分配大块内存之后的free list,内存池，它感受不到.
截图一张侯捷老师书中《stl源码剖析》中的一张图,free lists是一个16个元素的数组,数组中的每个元素都是一个union obj*的指针,同时也可存储数据(即client_data)。以free_list[11]为例,它既是obj*的指针，又可存储数据,obj*是指向下一个区块的指针，而不是指向紧邻obj的指针,free[11]区块的大小为96 bytes,假设free_list[11]头部为free_list_head,则free_list_head->free_list_link - free_list_head = 96

四.分配算法

// 函数：allocate// 功能: 分配size大小的内存// 输入：申请内存的大小size// 输出：若分配成功，则返回一个内存的地址，否则返回NULLstatic void *allocate(size_t size){if(size 大于 128)调用第一级分配器(malloc内存)；else{将size上调至8的倍数并根据大小从free_list中取对应的表头free_list_headif(my_free_list 不为空){取出free_list_head指向的区块,并更新free_list_head指向下一个区块}else{调用refill为free list重新填充空间并返回所需的内存地址}}}// 函数：refill// 功能：为free list重新重新填充空间，新的空间取自内存池(由chunk_alloc()完成)// 输入：内存块的大小size// 输出：建立空闲块链表并返回第一个可用的内存地址template <bool threads,int inst>void* __default_alloc_template<threads,inst>::refill(size_t size){调用chunk_alloc算法分配若干个大小为size的连续内存区域并返回起始地址chunk和成功分配的块数nobjif(块数为1)直接返回 chunk;else{开始在chunk地址块中建立free_list根据size取free_list中对应的表头元素free_list_head将free_list_head 指向chunk中偏移起始地址为size的地址处，即free_list_head = (obj*)(chunk+size)再将整个chunk中剩下的nobj-1个内存块串联起来构成一个空闲列表返回chunk，即chunk中第一个空闲的内存块}}// 函数：chunk_alloc// 功能：从内存池取空间给free list// 输入：内存块的大小size,预分配的内存块数nobj(以引用传递)// 输出：一块连续的内存区域的地址和该区域内可以容纳的内存块的块数template <bool threads,int inst>char* __default_alloc_template<threads,inst>::chunk_alloc(size_t size,int &nobjs){计算总共所需的内存大小total_bytes=nobjs*sizeif(内存池足以分配，即end_free-start_free >= total_bytes){则更新start_free返回旧的start_free}else if(内存池不够分配nobj个内存块，但至少可以分配一个){计算可以分配的内存块数并修改nobj更新start_free并返回原来的start_free}else     // 内存池连一个内存块都分配不了{先将内存池的内存块链入到对应的free_list中后调用malloc操作重新分配内存池，大小为2倍的total_bytes为附加量，start_free指向返回的内存地址if(分配不成功){if(16个空闲列表中尚有空闲块)尝试将16个空闲列表中空闲块回收到内存池中再调用chunk_alloc(size,nobj)else调用第一级分配器尝试out of memory机制是否还有用}更新end_free为start_free+total_bytes，heap_size为2倍的total_bytes调用chunk_alloc(size,nobj)}}// 函数：deallocate// 功能：释放对象// 输入：需要释放的内存块地址p和大小sizestatic void deallocate(void *p,size_t n){if(size 大于128字节)直接调用free(p)释放else{将size向上取8的倍数，并据此获取对应的空闲列表表头指针free_list_head调整free_list_head将p链入空闲列表块中}}

五.举例
假设程序开始时,客户端申请32 bytes的内存，则第二级配置器首先malloc 40个32 bytes的区块,其中一个交出以构造对象，另外19个交给free_list[3]维护(16个free_list分别维护大小为8，16，….,128 bytes大小的小额区块)，余下的20个留给内存池。若接下来客户端申请64 bytes的内存，此时首先查看free_list[7],因为它是空的，所以需要从内存池申请内存，内存池只够供应(32*20)/64=10个的64 bytes区块，就把这10个区块返回，其中一个用于构造对象，另外9个交给free_list[7]维护。接下来，若客户端申请96 bytes的内存，首先查看free_list[11]，此时它是空的，然后查看内存池，此时内存池也是空的，因此malloc() 40+n(附加量)个96 bytes的区块，其中第一个交出，另外19个交给free_list[11]维护，余下20+n个区块留给内存池

附上一份自己加注释的stl_alloc.h文件，边看《STL源码剖析》，边看源码有助于理解。
http://download.csdn.net/detail/u010772289/9619941
参考:>
《stl源码剖析》
http://blog.csdn.net/hackbuteer1/article/details/7724534