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就要優雅的多