C++的allactor

https://zhuanlan.zhihu.com/p/693267319

1 双层内存配置器

SGI设计了两层的配置器，也就是第一级配置器和第二级配置器。同时为了自由选择，STL又规定了 __USE_MALLOC 宏，如果它存在则直接调用第一级配置器，不然则直接调用第二级配置器。SGI未定义该宏，也就是说默认使用第二级配置器。

1.1 一级内存配置器

直接调用malloc和free来配置释放内存，简单明了。

template<int Inst>
class __MallocAllocTemplate //一级空间配置器
{typedef void (*OOM_HANDLER)();
private://these funs below are used for "OOM" situations//OOM = out of memorystatic void* OOM_Malloc(size_t n); //functionstatic void* OOM_Realloc(void *p, size_t newSZ); //functionstatic OOM_HANDLER OOM_Handler; //function pointerpublic:static void* Allocate(size_t n){void* ret = malloc(n);if (ret == NULL)ret = OOM_Malloc(n);return ret;}static void Deallocate(void* p, size_t n){free(p);}static void* Reallocate(void* p, size_t oldSZ, size_t newSZ){void* ret = realloc(p, newSZ);if (ret == NULL)ret = OOM_Realloc(p, newSZ);return ret;}//static void (* set_malloc_handler(void (*f)()))()//参数和返回值都是函数指针void (*)()static OOM_HANDLER SetMallocHandler(OOM_HANDLER f){OOM_HANDLER old = OOM_Handler;OOM_Handler = f;return old;}
};//让函数指针为空
template<int Inst>
void (*__MallocAllocTemplate<Inst>::OOM_Handler)() = NULL;template<int Inst>
void* __MallocAllocTemplate<Inst>::OOM_Malloc(size_t n)
{void* ret = NULL;void(*myHandler)() = NULL;for (;;){myHandler = OOM_Handler;if (myHandler == NULL)throw bad_alloc();(*myHandler)();ret = malloc(n);if (ret != NULL)return ret;}
}template<int Inst>
void* __MallocAllocTemplate<Inst>::OOM_Realloc(void* p, size_t newSZ)
{void* ret = NULL;void(*myHandler)() = NULL;for (;;){myHandler = OOM_Handler;if (myHandler == NULL)throw bad_alloc();(*myHandler)();ret = realloc(p, newSZ);if (ret != NULL)return ret;}
}typedef __MallocAllocTemplate<0> MallocAlloc; //一级空间配置重命名

1.2 二级内存配置器

1.如果用户需要的区块大于128，则直接调用第一级空间配置器
2.如果用户需要的区块大于128，则到自由链表中去找

• 如果自由链表有，则直接去取走
• 不然则需要装填自由链表（Refill）

1.2.1 自由链表

自由链表是一个指针数组，它的数组大小为16，每个数组元素代表所挂的区块大小，比如free _ list[0]代表下面挂的是8bytes的区块，free _ list[1]代表下面挂的是16bytes的区块…….依次类推，直到free _ list[15]代表下面挂的是128bytes的区块

同时我们还有一个被称为内存池地方，以start _ free和 end _ free记录其大小，用于保存未被挂在自由链表的区块，它和自由链表构成了伙伴系统。

1.2.2 工作原理

如果用户需要是一块n字节的区块，且n <= 128（调用第二级配置器），此时Refill填充是这样的：

• 系统会自动将n字节扩展到8的倍数，再将RoundUP（n）传给Refill。
• 用户需要n字节，且自由链表中没有，因此系统会向内存池申请nobjs * n大小的内存块，默认nobjs=20
• 如果内存池大于 nobjs * n，那么直接从内存池中取出
• 如果内存池小于nobjs * n，但是比一块大小n要大，那么此时将内存最大可分配的块数给自由链表，并且更新nobjs为最大分配块数x （x < nobjs）
• 如果内存池连一个区块的大小n都无法提供，那么首先先将内存池残余的零头给挂在自由链表上，然后向系统heap申请空间，申请成功则返回，申请失败则到自己的自由链表中看看还有没有可用区块返回
• 如果连自由链表都没了最后会调用一级配置器。

3 自定义内存配置器

// TODO:为vector写一个内存配置器，当空间大于1000时直接从堆分配内存#include <memory>
#include <vector>
#include <iostream>// 自定义内存配置器
template <typename T>
class CustomAllocator : public std::allocator<T> {
public:// 分配内存T* allocate(std::size_t n) {if (n * sizeof(T) > 1000) {// 大于1000字节时，使用堆分配return static_cast<T*>(::operator new(n * sizeof(T)));} else {// 小于或等于1000字节时，使用默认分配return std::allocator<T>::allocate(n);}}// 释放内存void deallocate(T* p, std::size_t n) {if (n * sizeof(T) > 1000) {// 大于1000字节时，使用堆释放::operator delete(p);} else {// 小于或等于1000字节时，使用默认释放std::allocator<T>::deallocate(p, n);}}
};int main() {// 使用自定义内存配置器的vectorstd::vector<int, CustomAllocator<int>> vec;vec.push_back(1); // 应该使用默认分配方式（通常很小）vec.push_back(2); // 同上vec.resize(1024); // 应该使用堆分配方式（因为1024 * sizeof(int) > 1000）vec.resize(1); // 应该再次使用默认分配方式（因为1 * sizeof(int) <= 1000）return 0;
}