空间配置器

什么是空间配置器

空间配置器是为各个容器高效管理空间的工具，负责空间的申请与回收，虽然一般情况下我们用不到它，但是研究空间配置器可以让我们对STL有更深的理解。

为什么需要空间配置器

我们之前在实现各个容器的时候，需要申请空间大的地方都是通过new申请的，但是这样的申请方式有着很大的缺陷：
1、空间申请和释放需要自己管理，容易造成内存泄露。
2、频繁向系统申请小块内存，造成内存碎片。
3、频繁向系统申请内存，影响程序效率。
4、无法应对申请空间失败的情况。
5、代码复用度不高。
6、代码韧性较差。
7、没有考虑线程安全的问题。

空间配置器实现原理

以上所说的不足，主要原因就是程序频繁向操作系统申请小块内存导致的。在SGI-STL中以128字节作为小块内存和大块内存的分界线，同时也将空间配置器分为两级结构。一级空间配置器处理大块内存，二级空间配置器处理小块内存。

一级空间配置器

以及空间配置器的实现较为简单，它主要是对malloc和free进行了一层封装，和我们曾经说过的new和delete的实现类似，其封装具体添加的内容主要是用来处理异常的。并且向其中添加了一个回调函数handler，当空间申请失败时会执行其中的处理操作，我们可以选择抛异常，中断或是其他行为都可以自定义。

二级空间配置器

二级空间配置器所作的事情会更多一些，因为为了避免频繁向系统申请小内存空间，每次我们在释放小内存的时候空间配置器其实并不会将其让系统回收，而是自己进行了回收，等到用户重新想要申请小空间的时候，再从自己回收的内存中拿出一部分交给用户。
二级空间配置器在内部实现了一个内存池，空间配置器通过维护这个内存池来给用户分配空间。
当用户想要申请一小块内存的时候，空间配置器会先从内存池中拉出一份交给用户，当用户释放这块空间的时候，空间配置器并不会将这块内存还给内存池，而是当用户想要申请新的小空间时，优先使用这块已经从内存池中分配出来的空间。
当内存池中的所有空间都用完时，空间配置器才会重新去向操作系统申请一块大空间来补充内存池。
空间配置器中是通过哈希桶来向用户分配小块内存空间的，空间配置器将哈希桶分为一共16个桶，每个桶下面管理一部分小块字节的空间，此时的哈希函数为申请空间大小 / 8，例如我们要申请8字节空间，则会到一号桶下面拿到它下面的内存空间，因为对应桶会保证当前下面所挂内存空间至少为桶号 * 8的大小，例如1号桶下面的内存空间大小都是8字节，2号桶都是16字节的，以此类推，因此一共16个桶16号桶下面的空间都是128字节的，刚好以8字节为单位平分小内存空间。一开始所有内存都是在内存池中的，当有内存从内存池中分配出去，或者要回收回来时就会有新的空间挂到哈希桶对应的桶下面，方便下次我们继续分配。也正是因为这样的哈希关系，我们获取的内存空间一般都会向上取整为8的整数倍字节。
当拿到要分配的空间的大小n时（这里假设<=128byte使用二级空间配置器）会进行以下操作：
1、向上对其为8字节的整数倍。
2、计算桶的位置，这里的哈希函数即为n / 16。
3、查看桶中是否有内存块，如果有内存块则取出一块内存，如果没有，则向内存池索要。此时会调用chunk_alloc(size_t n, size_t& nobj)，n为一块空间大小，nobj为一共申请多少块，默认nobj = 20，共向内存池申请total = n * nobj的空间。
4、如果内存池剩余空间大于total，则直接分配，并且把一块交给用户，其他块交给哈希桶挂起；如果内存池剩余空间小于total，但是至少有一块的空间，则会重新计算nobj的大小，nobj = 剩余空间 / n，然后将能分配的空间交给用户，多余的挂到哈希桶上；如果内存池目前剩余空间已经不足一块要申请的空间，则会向系统申请大内存空间，并将剩余的一部分空间挂到对应的哈希桶上。
5、向系统申请新内存也会出现两种情况，如果申请成功，则放入内存池，递归chunk_alloc，如果申请失败则去搜索哈希桶，取出桶中尚未使用的内存放入内存池，再调用chunk_alloc。
6、如果连哈希桶中也没有多余空间，则会调用一级空间配置器，这里又出现两种情况，如果一级空间配置器申请内存成功则放入内存池，递归chunk_alloc，如果申请失败则会抛异常，处理异常。