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];符合不同的人的使用习惯