c++ - stl内存池中使用union节省空间的问题.

Question

最近在看sgi stl的内存池实现, 里面有如下的数据结构 :

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

据说可以节约空间, 但是不懂, 我个人感觉这种池应该是这样的, 也不知道对不对, 但是这为什么可以省内存呢? 难道说这个union省内存的地方在于它不需要一个指针来特意指向真正分配给用户的内存, 而是直接在这个union中分配, 也就是我图中这个下面的方块其实是由很多个union组成, 但是除了最后一个union其实是一个指针用来指向下一个方块的, 其它的其实都是用来直接分配给用户的, 不知道这样的理解对不对?

如图就是的左边就是我所理解的它的这种内存池的实现, 而右边就是那种使用结构体式的内存实现, 这样看得话确是每一个区块可以节约一个指针大小的空间, 但是我感觉其实用结构体也可以达到相同的效果啊, 并不会浪费内存啊... 比如如果我把右边的结构体中指向用户分配的内存那部分指针直接改成和左边一样, 直接用来作为用户所获得的区块, 那样两者就没有区别了...

Answer 1

谢邀

这句话是正确的：它不需要一个指针来特意指向真正分配给用户的内存, 而是直接在这个union中分配

一个自由链表(free_list)在同一时刻，具备且仅具备如下功能之一：
1、作为一个自由链表指针，指向下一个自由链表
2、自身作为一块可用内存，供用户使用
由于如上用途不可能同时出现，故将obj定义为union，将free_list_link和client_data共享同一块内存来节省内存。

这句话是错误的：除了最后一个union其实是一个指针用来指向下一个方块的, 其它的其实都是用来直接分配给用户的

注意，这是链表，链表在内存中的分布是杂乱而不连续的，并非你所示的连续一段区域。
上文说道，一个obj结构，要不作为一块已被分配内存供用户使用，要不作为待分配区域存在于自由链表中。所以，自由链表中的每个块，都是指向下一个自由链表块，即理解为：

struct node{
    node *next;
};

一旦这个自由链表块被分配给用户了，那么它就从自由链表中被移除了，不再被认为是一个自由链表块（由union的语义，从此它就是一块普通的，分配给用户的内存，直到被用户释放，它才会被再次加入自由链表中）

这句话并不妥当：其实用结构体也可以达到相同的效果啊
一旦内存分配完了，这块内存（即自由链表块）的指针就会被malloc()/new返回给用户，接下来保存指针的任务就交给用户了，我干嘛还在内存配置器里留着这货，多保存个指针不又把空间浪费掉了么。只有未分配的内存才能存在于自由链表中！

另，推荐侯捷翻译的《STL源码剖析》

Answer 2

你理解基本没问题，就是为了节省一个指针的空间，对与任一节点有两种情况：

1. 节点分配了内存，那么这个union就是一个指向实际分配内存的指针

2. 节点没分配内存，那么这个union就是一个指向下一个节点的指针

用结构体搞是可以，比如让这个结构体里面就一个指针，但你这个指针类型只能是void *了，每次还得强转类型，比较丑陋了。union就要优雅的多