项目-STL空间配置器

这篇博客主要讲一下SGI-STL中的空间配置器的工作流程。

一、项目背景

1. 小块内存带来的内存碎片问题（外碎片问题）
2. 小块内存频繁申请释放带来的性能问题

二、空间配置器的思想

对于我们来说，对new和delete很熟悉，这两个函数可以分别完成内存的申请和释放，和c里面的malloc和free如出一辙。

Std::alloc的主要思想是：

（1）定义一个空间大小阈值，128bytes；

（2）如果申请的空间大于128bytes，那么就调用第一级空间适配器来完成分配工作；

（3）如果小于128bytes，那么就调用第二级空间适配器来完成。

一级空间配置器

一级空间配置器是以malloc()，free()，realloc()等C函数执行实际的内存配置、释放、重配置操作，并实现了C++的set_new_handler()函数。

它的内部设计实际就是为了压榨剩余的内存，达到内存的高效运用。所以一级空间配置器内部其实就是malloc和free的封装，然后尽量的开辟出用户想要的内存空间。

具体步骤如下：

​​一级空间配置器​

二级空间配置器

二级空间配置器使用内存池+自由链表的形式避免了小块内存带来的碎片化，提高了分配的效率，提高了利用率。

见下图：

项目流程

1. List.h、Vector.h是模仿STL容器中的两个list和vector的接口
2. Allocate.h里面定义了内存池即空间配置器的两级实现
3. Construct.h里面主要实现了对象的构造与析构接口
4. Iterator.h里面有五种迭代器的定义、迭代器萃取、反向迭代器定义、迭代器型别萃取以及两个非常有用的函数 Distance、Advance
5. TypeTraits.h定义了迭代器所指节点的值类型萃取，是否是POD类型
6. Uninitialized.h里面是主要是一些拷贝、填充类的函数
7. Main.cpp是测试文件，用来测试两个容器的接口和内存池实现正确与否

空间配置器的问题

1. 在空间配置器中所有的函数和变量都是静态的，所以他们在程序结束的时候才会被释放发。二级空间配置器中没有将申请的内存还给操作系统，只是将他们挂在自由链表上。所以说只有当你的程序结束了之后才会将开辟的内存还给操作系统。

2. 由于它没有将内存还给操作系统，所以就会出现二种极端的情况。

   2.1. 假如我不断的开辟小块内存，最后将整个heap上的内存都挂在了自由链表上，但是都没有用这些空间，再想要开辟一个大块内存的话会开辟失败。

   2.2. 再比如我不断的开辟char,最后将整个heap内存全挂在了自由链表的第一个结点的后面，这时候我再想开辟一个16个字节的内存，也会失败。

   解决方法：

   我想的是，针对2.1我们可以引入释放二级空间配置器的方法，但是这个释放比较麻烦。针对2.2我们可以合并自由链表上的连续的小的内存块。

3. 为什么引入复杂的两级空间配置器?

   (1). 频繁使用malloc，free开辟释放小块内存带来的性能效率的低下

   (2). 内存碎片问题，导致不连续内存不可用的浪费

4. 为什么所有成员函数都是静态的?

   是为了在外面通过作用域就可以调用，而不需要构造对象

5. ROUNT_UP的实现原理是什么?

static size_t ROUND_UP(size_t bytes)//作用是将非8倍数的整数上调到8的倍数。
{
       return (((bytes)+__ALIGN - 1) &~(__ALIGN - 1));
}