在 GNU 2.9 中默认的 allocator 内部是使用的 ::operator new 和 ::operator delete，并没有什么特殊操作，而它所有的容器实现，都是通过 std::alloc 实现的（作为容器初始化时的第二参数）。

而在 GNU 4.9 之后的版本，std::alloc 被移动到 ext/pool_allocator.h 中，通过 __gnu_xxx::__pool_alloc 调用

std::alloc 的内部实现

通过上图可以看到有如下特点

• std::alloc 内部维护了一个 16 长度的数组，用于记录从 8 bytes 到 128 bytes 16种大小的对象的 free_list_head 指针，实现内存池管理。如果超过 128 bytes，则仍旧使用 ::operator new。
• std::alloc 适用于所有大小在 8 - 128 bytes 的对象，它只关注对象的大小，而不在意 class 是否相同。
• 当对象的大小不满足 8 的倍数时，会做一次对齐，存到对应 8 倍数的上界位置。
• 默认 std::alloc 在 free_list 为空的时候会一次性申请一块大的内存作为 Memory Pool , 然后从 Pool 中取出CHUNK 大小为 20 的内存，作为当前长度的链表使用，同时剩下的内存供下次使用（所以可以看到64 bytes的 free_list_head 直接指向了 32 bytes 的下半部分，长度为 10）。也就是说在初次创建 32 bytes 的 free_list 时会申请 20 * size * 2 大小的内存。
• 一次申请最终得到的内存只会有 2个 Cookie，Cookie Head 和 Cookie tail，中间的对象不含 Cookie，即 Cookie Free Blocks 。

申请内存

在上面提到，申请内存的时候是先查看 Pool 还有没有余量，如果有，则从 Pool 中切割出一块空间挂上 free_list 的区块，free_list 的数量永远在 1 - 20之间（并不一定就是20）。

如果 Pool 没有余量，故会去申请 size * 20 * 2 + RoundUp(当前已经申请的内存大小 >> 4) 大小的内存，记为 Pool， 再从中切出一块区域（大小为size）给到返回对象，另为19个区块组成链表记录到对应的 free_list_head 中。余下的内存作为 Memory Pool 。在std::alloc 中会通过两个指针 start_free 和 end_free 指定 Memory Pool 的区域。

<aside> 💡 RoundUp 函数将内存大小调整到上界 8 的倍数

</aside>

碎片处理

有时候，当 Memory Pool 的余量还要小于下一个要创建的 free_list_head 的大小时（即小于 size），那么可以先将这一块余量大小的内存，挂在同样大小的 free_list 下。

比如说，剩余 80 bytes，但要申请的大小是 104 bytes，这时候就可以将这 80 bytes 挂在对应大小 80 bytes 的 free_list_head 的上一个。这样就完成了内存碎片处理。