1. 空间配置器

空间配置器：是对空间进行分配和处理的部分。是空间而不是内存的原因是因为空间也可以是磁盘等其他介质。

SGI STL的配置器是alloc而不是allocator，而且不接受任何参数。
SGI STL对于标准的配置器只做了一层简单包装，且不推荐我们使用。
在一般使用类的动态内存申请时，我们使用的new和delete其实都分为两步：
- new首先调用operator new 配置内存
- new然后调用类的构造函数构造对象。
- delete首先调用类的析构函数析构对象。
- delete然后调用operator delete 释放内存
SGI STL的new和delete：
1. 内存配置由alloc::allocate()负责。
2. 内存释放由alloc::deallocate()负责。
3. 对象构造由::construct()负责。
4. 对象析构由::destroy()负责。

1.1 构造和析构：construct,destroy

1.2 空间的配置和释放::alloc

SGI对于空间配置的设计哲学如下：

向system heap要求空间

考虑多线程

考虑内存不足时的应变措施

考虑小区块带来的内存碎片问题

考虑到小区快带来的内存破碎问题，SGI设计了双层级配置器。

第一级配置器：直接使用C中的malloc和free。

第二级配置器：视情况不同，配置区块大于128byte时，调用第一级；小于128byte，采用更复杂的内存池模式。

1.3 第一级配置器剖析

SGI其实是直接使用了c中的malloc和free。
SGI不使用c++的new,而是使用c的malloc,有一部分原因是因为c++中没有提供realloc的功能。
但是当出现内存配置出现问题时，SGI又会仿照C ++ 实现一个new-handler机制。不能直接使用c++的该机制的原因是，它没有使用new来配置内存，所以无法直接使用这个c ++ 的特定机制，只能仿真一个类似的。
当第一级配置器的allocate（）和realloc（）不成功时，它会调用oom_malloc（）和oom_realloc（）函数（oom代表out of memory），这两个函数内部都是一个内循环，不断调用“内存不足处理例程”。
注意一点的是，上述的内存不足处理例程由调用者自己设计，如果没有被设定，配置器会直接丢出BAD_AALOC异常。

1.4 第二级配置器剖析

第二级配置器的存在就是为了解决小区块内存带来的内存碎片化和配置时带来的额外负担。

额外负担是指，当每一个区块内存被分配的时侯，他都需要一部分额外内存来纪录该块内存的大小，这一块纪录内存属于额外负担。

第二级配置器对于内存配置的做法是：
区块大于128byte时，移交给第一级配置器处理。
区块小于128byte时，使用内存池进行管理。

1.4.1 内存池管理

内存池每次的配置一大块内存，然后用一个freelist来进行维护。有内存需求则从freelist拨出，如果释放则有freelist收回。为了方便管理，SGI会将小区块的内存需求调整到8的倍数。这样一来，有8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128，总共16个freelist。

上调到8的倍数实现：

1 2	enum {__ALIGN=8}; { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN – 1)); }

free_list:为了节省空间，obj的结构是一个union类型。也就是说，当该区块给用户的时候，obj是一个指向实际区块的指针，当给系统时候，obj是一个指向下一个节点的指针。这个可以节省内存的开销。
1
2
3
4
union obj{
    union obj* free_list_link;
    char client_data[1];
}

1.4.2 空间配置函数allocate()

区块大于128byte时，移交给第一级配置器处理。
区块小于128byte时，在freelist中找可用区块，有则调用；没有则上调至8倍数边界，调用refill()来填充空间。

1.4.3 空间释放函数deellocate()

区块大于128byte时，移交给第一级配置器处理。
区块小于128byte时，找出对应区块，进行回收。

1.4.4 重新填充free_list函数refill()

当allocate()发现没有freelist没有区块的时候，就调用refill()，refill()从内存池中取出内存重新填充freelist。默认取得20个新区快，但是当内存池不够时，获得的会小于20.

1.4.5 从内存池取内存函数chunk_alloc()

chunk_alloc()通过两个指针：end_free和start_free的差值来判断内存池的剩下空间。

空间>20区块空间：调出20个区块空间给freelist.
1区块空间<空间<20区块空间：调出能调出的空间出来。
空间<1区块空间：使用malloc()从系统中申请内存，然后拨给freelist。新申请的量是需求量的两倍，加上一个随着配置次数增加不断变大的附加量。
特殊情况（系统内存不够，malloc失败）：chunk_alloc()开始寻找freelist中未被使用的够大的区块，找到了就拿走一块；找不到就调用第一级配置器。第一级配置器虽然使用也是malloc，但是有out-of-memory机制，可以有机会释放其他内存来使用。

1.5 内存基本处理工具

对于未初始化的空间，STL的处理工具有五个：
construct(),destroy(),uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n()
其中uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n()分别对应STL算法中的copy() ,fill(),fil_n()。
C++规格要求这三个函数具有commit or rollback语意。意思是要么就构造出所有必要元素。要么不构造任何东西。（很像数据库中的原子性）

1.5.1 uninitialized_copy()

1 2	template<class InputIterator, class ForwardIterator> ForwardIterator uninitialized_copy ( InputIterator first, InputIterator last,ForwardIterator result )