5千字长文+30张图解 | 陪你手撕STL空间配置器源码

7. alloc 二级配置器源码解读

照例，还是截取部分（精华）源码解读。看累了嘛，远眺歇会，回来继续看，接下来的这部分，将会更加的让我们为大师的智慧折服！

第二级配置器多了一些机制，专门针对内存碎片。内存碎片化带来的不仅仅是回收时的困难，配置也是一个负担，额外负担永远无法避免，毕竟系统要划出这么多的资源来管理另外的资源，但是区块越小，额外负担率就越高。

7.1 SGI 第二级配置器到底解决了多少问题呢？

简单来说 SGI第二级配置器的做法是：sub-allocation （层次架构）：

前面也说过了，SGI STL 的第一级配置器是直接使用 malloc()， free(), realloc() 并配合类似 C++ new-handler 机制实现的。第二级配置器的工作机制要根据区块的大小是否大于 128bytes 来采取不同的策略：

继续跟上节奏，上面提到了 memory pool ，相信程序员朋友们很熟悉这个名词了，没错，这就是二级配置器的精髓所在，如何理解？请看下图：

有了内存池，是不是就可以了，当然没有这么简单。上图中还提到了自由链表，这个又是何方神圣？

我们来一探究竟！

7.2 自由链表自由在哪？又该如何维护呢？

我们知道，一方面，自由链表中有些区块已经分配给了客端使用，所以 free_list 不需要再指向它们；另一方面，为了维护 free-list，每个节点还需要额外的指针指向下一个节点。

那么问题来了，如果每个节点有两个指针？这不就造成了额外负担吗？本来我们设计 STL 容器就是用来保存对象的，这倒好，对象还没保存之前，已经占据了额外的内存空间了。那么，有方法解决吗？当然有！再来感受一次大师的智慧！

（1）在这之前我们先来了解另一个概念——union（联合体/共用体），对 union 已经熟悉的读者可以跳过这一部分的内容；如果忘记了也没关系，趁此来回顾一下：

（a）共用体是一种特殊的类，也是一种构造类型的数据结构。

（b）共用体表示几个变量共用一个内存位置，在不同的时间保存不同的数据类型和不同长度的变量。

（c）所有的共用体成员共用一个空间，并且同一时间只能储存其中一个成员变量的值。例如如下：

一个union 只配置一个足够大的空间以来容纳最大长度的数据成员，以上例而言，最大长度是 double 类型，

所以 ChannelManager 的空间大小就是 double 数据类型的大小。在 C++ 里，union 的成员默认属性页为 public。union 主要用来压缩空间，如果一些数据不可能在同一时间同时被用到，则可以使用 union。

（2）了解了 union 之后，我们可以借助 union 的帮助，先来观察一下 free-list 节点的结构

来深入了解 free_list 的实现技巧，请看下图。

在 union obj 中，定义了两个字段，再结合上图来分析：

从第一个字段看，obj 可以看做一个指针，指向链表中的下一个节点；

从第二个字段看，obj 可以也看做一个指针，不过此时是指向实际的内存区。

一物二用的好处就是不会为了维护链表所必须的指针而造成内存的另一种浪费，或许这就是所谓的自由奥义所在！大师的智慧跃然纸上。

7.3 第二级配置器的部分实现内容

到这里，我们已经基本了解了第二级配置器中 free_list 的工作原理了。附上第二级配置器的部分实现内容源码：

太长了吧，看懵逼了，没关系，请耐心接着往下看。