STL庫的內存配置器（allocator）

正在學習中，如果有錯，還請多多指教，根據不斷的理解，會進行更改，更改之前的樣子都會保留下來，記錄錯誤是最大的進步，嗯嗯！

STL源碼剖析簡體中文完整版(高清晰掃描帶目錄)PDF 下載地址 http://www.linuxidc.com/Linux/2016-04/129761.htm

具有次配置力的SGI空間配置器（SGI是STL的一種版本，也有其他的版本）

這裡我就不貼出來具體成員和接口的實現了，網上可以搜到STL的源碼

C++中，new一個變量可以分為兩個階段，1.分配空間 2.調用構造函數；delete變量也分為兩個步驟，1.調用析構函數 2.釋放空間

SGI的alloc將這兩部分分開，讓空間的分配釋放和構造析構由不同的函數調用，區分他們的操作

空間的分配和釋放由alloc::alloclate() alloc::dealloclate()實現 構造和析構由alloc::construct() alloc::destory()函數負責，他們在頭文件

#include<stl_alloc.h> //負責內存空間的配置和釋放 2 #include<stl_construct.h> //負責對象內容的構造和析構 這兩個頭文件都包含在#include<memory>當中

先講一下析構和構造的大概思路　　

• • 這裡提到一個概念_type_traits<T>（這是個模板），首先通過value_type()獲得迭代器所指向對象的類型然後使用_type_traits進行類型判別，該對象是否是trivial（無關痛癢的） destructor，我對這裡的理解是，當迭代器所指對象的類型為POD(Plain Old Data)類型（PS：POD類型可以理解為傳統的C語言類型，就是int那一類的）是不需要專門調用析構函數的，等待系統自動釋放int所占用的空間即可，但當迭代器所指對象的類型為string對象（或者是其他你自己寫的類的對象），就不能依靠系統，需要調用專門的析構函數挨個析構。進行類型判別之後，就可以提高工作效率。（destory()對char*等類型也有相應的特化）
  • 構造函數就采用泛式構造，使用new進行構造
• 下面講一下我對空間的配置與釋放的理解
  • C++對內存配置的基本操作依靠::operator new()和::operator delete()這兩個全局函數，這兩個函數只起到分配和釋放內存的作用，並不會調用構造函數和析構函數，他們就相當於C語言中的malloc()和free()函數，SGI正是以malloc()和free()進行空間的管理
  • 為了解決內存碎片的問題（當不斷地malloc空間時候，找到足夠大小的空間就拿來用，不可避免的的會產生內存碎片），於是就有了內存池的概念（內存池就是系統實現給開辟出一大塊空間等待使用，當需要空間的時候直接從內存池中取，當內存池中的內存也不夠使用時，再去Heap中開辟新的空間注入到內存池當中）

下面就比較重要了，SGI空間配置器采用了兩級配置器，分為第一級配置器和第二級配置器，第一級配置器就是拿malloc()實現的，第二級配置器采用了內存池的概念；

先來講第一級配置器，第一級配置器的實現就是用的malloc()（因為很重要所以多說幾遍），它會不斷地嘗試開辟內存，如果沒有內存可供開辟，就會嘗試釋放空間，然後再取嘗試開辟空間，第一級配置器比較重要的一點就是實現了類似C++中new-handler機制，用來處理內存不足的情況

內存池是使用鏈表結構實現的（個人感覺和哈希桶的方法類似），而不采用順序表，這樣就可以更好的解決內存碎片的問題了。

注意，這裡的freelists是鏈表！

注意！這裡之前寫的不太清楚，freelists是一個順序表，每一個單元下邊都連接這一個鏈表，當區塊被客端（client）使用就會像上圖一樣將區塊撥出去，然後改變指針指向下一個節點（就是采用頭刪）

每個鏈表節點所管理的區塊大小也是不一樣的，第一個節點管理8bytes，第二個16bytes。。。以此類推，最後一個節點管理128bytes，所以當超過128字節第二級配置器無法處理，就只好調用第一級配置器（內存不足時也會調用第一級配置器，因為第一級配置器裡面有內存不足處理例程）

下面給出鏈表節點的實現

1 union obj
2 {
3     union obj *free_list_link;
4     char client_data[1];//The client sees this;
5 };   

裡面的聯合體指針就是指向下一個節點的指針，那個char是指向實際內存塊的指針，采用聯合體可以減少內存的消耗，不必專門維護一個指向下一個節點的指針

當節點所指的內存塊是空閒塊時，obj被看做一個指針，指向下一個節點，當節點已經被分配了內存之後，被視為一個指針，指向實際區塊

當分配函數allocate()（alloc中申請內存的函數）發現沒有可用的區塊之後，就會去內存池中申請新的區塊（調用chunk_alloc()函數） ，默認申請20個區塊，當內存池的可用內存不足20個區塊，有多少給多少，如果連一個區塊的內存都不夠，就往內存池中注入內存（就是再去開辟一些放進內存池裡），就會去free_lists中遍歷，尋找內存池分配給自由鏈表但是卻處於空閒狀態的節點，將這些節點的存儲空間歸還個內存池，再遞歸去使用chunk_alloc()函數判斷是否空間夠分配；如果很不幸，還是不夠用，那麼注意！！會將內存池中剩余的小空間分配成低位區塊分給自由鏈表（就是說假如需要申請16個字節的節點區塊，不夠了，但是內存池中有8個字節的空間，當然不能夠浪費咯，趕緊分配出去）然後去往內存池中注入內存（就是再去開辟一些放進內存池裡）。

這個是《STL源碼剖析》裡的一個例子

當整個系統堆得內存都不夠了的時候，就chunk_malloc()就會四處尋找可用內存，嘗試釋放一些沒用的空間，如果還是無法找到就去調用第一級配置器，因為一級配置器裡有內存不足處理例程