type
status
date
slug
summary
tags
category
icon
password
Property
为什么需要空间配置器
频繁使用
malloc分配内存的造成的问题：- 空间申请与释放需要用户自己管理，容易造成内存泄漏
- 频繁向系统申请小块内存块，容易造成内存碎片
- 频繁向系统申请小块内存，影响程序运行效率
- 直接使用malloc与new进行申请，每块空间前有额外空间浪费
- 申请空间失败怎么应对
- 代码结构比较混乱，代码复用率不高
- 未考虑线程安全问题
内存碎片
- 内部碎片：页式管理、段式管理、段页式管理，无法避免，可以通过算法优化
- 外部碎片：申请堆空间之间的片段空隙，空间配置器优化的是外部碎片
系统依次分配了16byte、8byte、16byte、4byte，还剩余8byte未分配，此时要分配一个24byte的空间，操作系统回收了上面的两个16byte，总的剩余空间有40byte，但是却无法分配出一个连续24byte的空间，这就是外碎片问题。有足够内存，但是不连续，导致无法申请大块内存
因此，引入空间配置器
allocator。可以感知类型的空间分配器，用于分配和释放内存，将内存的分配释放与对象的创建销毁分开。allocator 接口层
接口层源码
针对容器来说，空间的分配
construct 与对象的创建 allocate 是分开的，并不是绑定在一起。提供的接口如下：源码位于
stl_alloc.h，接口层的源码如下：定位 new 表达式
定位
new表达式：在p指向的未初始化的内存中构造T类型对象。例：使用
std::allocator实现自定义的Vector类接口形式：
实现代码：
allocator 实现层
真正进行分配空间的是
std::alloc，见源码：SGI-STL以128byte作为小块内存与大块内存的分界线，将空间配置器其分为两级结构，在分配空间的时候，若申请的空间大小：
- 大于 128 字节，调用一级配置器，使用 malloc / free
- 小于等于 128 字节，调用二级配置器（默认空间配置器），使用内存池 + 16个自由链表。
一级空间配置器
对于大块内存（大于 128 字节），第一级空间配置器使用
malloc/free分配和释放内存，对应的源码：二级空间配置器
默认空间配置器，所有的容器最终调用它完成空间的分配和释放。由内存池 + 16 个自由空闲链表组成。
简单来说，
allocator根据用户申请的空间大小（8 的整数倍，向上取整），先向堆申请大块内存，然后拿出其中一部分将其分割成固定大小的内存块，并组织成空闲链表；另一部分作为内存池备用。此后，每次申请内存先向空闲链表申请空间，对应的空闲链表不存在则向内存池申请空间，否则向堆申请大块内存。
内存池就是：先申请一块比较大的内存块已做备用，当需要内存时，直接到内存池中去取，当池中空间不够时，再向内存中去取，当用户不用时，直接还回内存池即可。避免了频繁向系统申请小块内存所造成的效率低、内存碎片以及额外浪费的问题。
SGI-STL中二级空间配置器设计
SGI-STL中的二级空间配置器使用了内存池技术，但没有采用链表的方式对用户已经归还的空间进行管理(因为用户申请空间时在查找合适的小块内存时效率比较低)，而是采用了哈希桶的方式进行管理。那是否需要128桶个空间来管理用户已经归还的内存块呢？答案是不需要，因为用户申请的空间基本都是4的整数倍，其他大小的空间几乎很少用到。因此：SGI-STL将用户申请的内存块向上对齐到了8的整数倍。
二级空间配置器源码部分如下：
allocate
空间分配的核心函数在于：
_S_refill和 _S_chunk_alloc函数_S_refill函数：填充__nobjs个结点大小为 __n的自由空闲链表。其中__nobjs默认是 20，若内存池不够分割，则重新计算。_S_chunk_alloc函数：申请空间。比较内存池剩余空间与本次申请的内存空间大小：- 内存池剩余空间足够，则内存池一次分配相应大小的内存
- 内存池剩余空间不足，则判断剩余空间能否分割，若不能分割，则向堆上申请大块内存
deallocate
- 回收的空间大于 128 字节，直接使用 free 回收空间
- 回收的空间小于等于 128 字节，直接链回自由空闲链表