C++ STL 内存分配的思想以及使用union（共用体）的妙处

时间：2023-01-16 19:58:26

STL空间配置器

前言：

今天看书《STL源码剖析》，书中说道：空间配置器;空间配置器是用来为容器分配内存的一个东西，空间配置器中有两种配置器：第一级配置器，第二级配置器

当用户申请的内存小于128bytes的时候，用第二级配置器，当用户申请的内存大于128bytes的时候，第二级配置器已经不能满足，这个时候要祭出第一级配置器这个武器。

第一级配置器

第一级配置器直接调用malloc函数来分配内存。

第二级配置器

free_list结构：

第二级配置器才是重点：为了解决分配内存的时候出现碎片的问题，第二级配置器使用了内存池的机制，首先，free_list 维护了16个链表，每个链表my_free_list 存放的节点的大小是~~~这一类同样大小的内存（一般是20个），最小的是8个字节，然后开始以8的倍数递增，分别是 8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128，perfect  ！！！，刚好到128个字节，这就是为什么大于128bytes要使用第一级配置器了，因为，第二级配置器最多只能分配128bytes，

好了，这16个链表，里边每一个链表的节点都是这种结构

union obj{
        union obj *free_list_link;
        char client_data[1];
}

free_list分配：

如果用户要申请大小为N的内存，如果N>128,用第一级配置器，如果N<128,假设N=15,为了避免内存碎片，把N上调到8的倍数，这里是16，那么就去找到大小为节点16的那个空闲链表，my_free_list = free_list + FREELIST_INDEX(N),     FREELIST_INDEX(N),的功能是把通过N上调到合适的8的倍数，然后算出相应的那一个free_list的号数，比如说：N = 15 那就调到16，16/8 = 2，从0开始算那就是第一号free_list,,如果那个链表free_list 有可用的内存块，那么就把第一块拿出来,然后就把头指针往下移动一个单位 ，比如说找的了链表指针是my_free_list,取出第一个 result = * my_free_list ,   链表头指针下移my_free_list = result ->free_list_link;

free_list无可用，memory pool 登场之1：

如果第二号free_list的内存块都用完了，这个时候，向内存池申请，一般是20个大小为16bytes的内存，把第一个返回，其余19个加到free_list中

free_list无可用，memory pool 登场之2：

在退一步，如果我们的大本营memory pool，内存池不够提供20个大小为16的块，但是足够提供几个可能是7个，那么就把这7个给分配出去1个返回，6个加到free_list，注意这个时候内存池已经空了

free_list无可用，memory pool 登场之3：


再惨一点，如果内存池里边只有一个，那就直接返回这个，如果内存池里边的大小不足以提供一个申请的单位，如不足16bytes,那么也不要浪费，把剩下来的一点点进行判断 是否为8的倍数，分出去加到相应的free_list里边，这个时候就要开始使用malloc来分配heap内存了，这次申请的标准也定的挺巧妙，是 (40+n)*16 ,因为free_list向内存池申请20 * 16 bytes，那么我就申请双倍一半给free_list ，一半给memory pool,至于n嘛，为1个附加值，你申请的次数越多，n就越大，这更符合实际

感叹：

好了，以上就是内存分配的全部过程，比较复杂，不过真心巧妙，宛如一件艺术品。

释放：

如果要释放内存的话，很简单，若释放的大小size>128bytes，直接调用第一级配置器的释放函数dealloc()，其实就是内部调用free(),如果释放的大小<128那么判断大小从而确定 属于哪一号free_list，比如说是64，那就是64/8 -1，那就是第7号free_list,把这块要回收的内存插到第7号free的开头，然后指针my_free_list指针向前移动一个节点，ok!!!

这次真的领略到了大师的水准啊，这个内存分配回收机制太美妙了，极大的减少了开辟空间回收空间的损耗，不到迫不得已并不会使用malloc(),对于内存的利用无所不用其法，佩服佩服！！


附加：union的妙用

另外：free_list的节点的定义也是非常的巧妙！！

union 修饰的这种数据类型，里面可以存放多种不同类型的数据，并且公用一块内存，也就是说   free_list_link  和client_data 用的是同一块内存，前者表示指向下一个节点的指针，后者表示一个指向实际内存的指针，它们公用同一块内存，正是因为无论在什么情况下，二者只用其一，情况无非两种，分配和不分配，不分配的时候，节点就放在空闲链表里面，节点内容是下一个节点的地址，如果被分配了，那么节点内容就是指向一块实际的内存，这样就不用在节点里开两个不同内存的变量，节省的好多空间（正正符合STL的哲学），这个做法太完美了！！！！


union 主要用于这种 n选1的情况，也可以用例外一种情况以达到例外一种妙用，

union Matrix
{
       struct m{_11;_12,_13;_21,_22;_23;_31;_32;_33};
       int a[3][3];
}

3D中经常用到的Matrix 结构体，一个元素可以有两种，表示方式，_11,和a[0][0];符合不同的人的使用习惯



标签：

相关文章