大家好，我是小賀。
1. 前言
天下大事，必作于細。
源碼之前，了無秘密。
你清楚下面這幾個問題嗎？
- 當你調用 new 和 delete 時編譯器底層到底做了哪些工作？
- STL 各大容器底層空間配置原理是怎樣的？
- STL 空間配置器到底要考慮什麼？
- 什麼是記憶體的配置和釋放？
- …
這篇，我們就來回答這些問題。
2. STL 六大元件
在深入配置器之前，我們有必要了解下 STL 的背景知識：
标準模闆庫（英文：Standard Template Library，縮寫：STL），是一個 C++ 軟體庫。
STL 的價值在于兩個方面，就底層而言，STL 帶給我們一套極具實用價值的零部件以及一個整合的組織；除此之外，STL 還帶給我們一個高層次的、以泛型思維 (Generic Paradigm) 為基礎的、系統化的“軟體元件分類學”。
STL 提供六大元件，了解這些為接下來的閱讀打下基礎。
1、容器（containers）:各種資料結構，如 vector, list, deque, set, map 用來存放資料。從實作的角度來看，STL 容器是一種 class template。
2、算法（algorithms）：各種常用的算法如 sort, search, copy, erase…從實作角度來看，STL 算法是一種 function template。
3、疊代器（iterators）：扮演容器與算法之間的膠合劑，是所謂的“泛型指針”。從實作角度來看，疊代器是一種将 operator *, operator ->, operator++, operator– 等指針相關操作予以重載的class template。
4、仿函數（functors）：行為類似函數，可以作為算法的某種政策。從實作角度來看，仿函數是一種重載了 operator() 的 class 或class template。
5、擴充卡（adapters）：一種用來修飾容器或仿函數或疊代器接口的東西。例如 STL 提供的 queue 和 stack，雖然看似容器，其實隻能算是一種容器擴充卡，因為它們的底部完全借助 deque，所有操作都由底層的 deque 供應。
6、配置器（allocator）：負責空間配置與管理，從實作角度來看，配置器是一個實作了動态空間配置、空間管理、空間釋放的 class template。
初學作圖，有點醜，還能看，嘿嘿
3. 何為空間配置器
3.1 為何需要先了解空間配置器？
從使用 STL 層面而言，空間配置器并不需要介紹 ，因為容器底層都給你包裝好了，但若是從 STL 實作角度出發，空間配置器是首要了解的。
作為 STL 設計背後的支撐，空間配置器總是在默默地付出着。為什麼你可以使用算法來高效地處理資料，為什麼你可以對容器進行各種操作，為什麼你用疊代器可以周遊空間，這一切的一切，都有“空間配置器”的功勞。
3.2 SGI STL 專屬空間配置器
SGI STL 的空間配置器與衆不同，且與 STL 标準規範不同。
其名為 alloc，而非 allocator。
雖然 SGI 也配置了 allocatalor，但是它自己并不使用，也不建議我們使用，原因是效率比較感人，因為它隻是在基層進行配置/釋放空間而已，而且不接受任何參數。
SGI STL 的每一個容器都已經指定預設的空間配置器是 alloc。
在 C++ 裡，當我們調用 new 和 delete 進行對象的建立和銷毀的時候，也同時會有記憶體配置操作和釋放操作:
這其中的 new 和 delete 都包含兩階段操作：
a. 對于 new 來說，編譯器會先調用 ::operator new 配置設定記憶體；然後調用 Obj::Obj() 構造對象内容。
b. 對于 delete 來說，編譯器會先調用 Obj::~Obj() 析構對象；然後調用 ::operator delete 釋放空間。
為了精密分工，STL allocator 決定将這兩個階段操作區分開來。
c. 對象構造由 ::construct() 負責；對象釋放由 ::destroy() 負責。
d. 記憶體配置由 alloc::allocate() 負責；記憶體釋放由 alloc::deallocate() 負責；
STL配置器定義在 <memory> 中，下圖直覺的描述了這一架構結構：
4. 構造和析構源碼
我們知道，程式記憶體的申請和釋放離不開基本的構造和析構基本工具：construct() 和 destroy() 。
在 STL 裡面，construct() 函數接受一個指針 P 和一個初始值 value，該函數的用途就是将初值設定到指針所指的空間上。
destroy() 函數有兩個版本，第一個版本接受一個指針，準備将該指針所指之物析構掉。直接調用析構函數即可。
第二個版本接受 first 和 last 兩個疊代器，将[first,last)範圍内的所有對象析構掉。
其中 destroy() 隻截取了部分源碼，全部實作還考慮到特化版本，比如判斷元素的數值類型 (value type) 是否有 trivial destructor 等限于篇幅，完整代碼請參閱《STL 源碼剖析》。
再來張圖吧，獻醜了。
5. 記憶體的配置與釋放
前面所講都是對象的構造和析構，接下來要講的是對象構造和析構背後的故事—（記憶體的配置設定與釋放），這塊是才真正的硬核，不要搞混了哦。
5.1 真· alloc 設計奧義
對象構造和析構之後的記憶體管理諸項事宜，由 <stl_alloc.h> 一律負責。SGI 對此的設計原則如下：
a. 向 system heap 要求空間
b. 考慮多線程 (multi-threads) 狀态
c. 考慮記憶體不足時的應變措施
d. 考慮過多“小型區塊”可能造成的記憶體碎片 (fragment) 問題
考慮到小型區塊可能造成的記憶體破碎問題，SGI 為此設計了雙層級配置器。當配置區塊超過 128bytes 時，稱為足夠大，使用第一級配置器，直接使用 malloc() 和 free()。
當配置區塊不大于 128bytes 時，為了降低額外負擔，直接使用第二級配置器，采用複雜的 memory pool 處理方式。
無論使用第一級配接器（__malloc_alloc_template）或是第二級配接器（__default_alloc_template），alloc 都為其包裝了接口，使其能夠符合 STL 标準。
其中， __malloc_alloc_template 就是第一級配置器;
__default_alloc_template 就是第二級配置器。
這麼一大堆源碼看懵了吧，别着急，請看下圖。
其中 SGI STL 将配置器多了一層包裝使得 Alloc 具備标準接口。
6. alloc 一級配置器源碼解讀
這裡截取部分（精華）解讀
（1）第一級配置器以 malloc(), free(), realloc() 等 C 函數執行實際的記憶體配置、釋放和重配置操作，并實作類似 C++ new-handler 的機制（因為它并非使用 ::operator new 來配置記憶體，是以不能直接使用C++ new-handler 機制）。
（2）SGI 第一級配置器的 allocate() 和 reallocate() 都是在調用malloc() 和 realloc() 不成功後，改調用 oom_malloc() 和oom_realloc()。
（3）oom_malloc() 和 oom_realloc() 都有内循環，不斷調用“記憶體不足處理例程”，期望某次調用後，獲得足夠的記憶體而圓滿完成任務，哪怕有一絲希望也要全力以赴申請啊，如果使用者并沒有指定“記憶體不足處理程式”，這個時候便無力乏天，真的是沒記憶體了，STL 便抛出異常。或調用exit(1) 終止程式。
7. alloc 二級配置器源碼解讀
照例，還是截取部分（精華）源碼解讀。看累了嘛，遠眺歇會，回來繼續看，接下來的這部分，将會更加的讓我們為大師的智慧折服！
第二級配置器多了一些機制，專門針對記憶體碎片。記憶體碎片化帶來的不僅僅是回收時的困難，配置也是一個負擔，額外負擔永遠無法避免，畢竟系統要劃出這麼多的資源來管理另外的資源，但是區塊越小，額外負擔率就越高。
7.1 SGI 第二級配置器到底解決了多少問題呢？
簡單來說 SGI第二級配置器的做法是：sub-allocation （層次架構）：
前面也說過了，SGI STL 的第一級配置器是直接使用 malloc()， free(), realloc() 并配合類似 C++ new-handler 機制實作的。第二級配置器的工作機制要根據區塊的大小是否大于 128bytes 來采取不同的政策：
繼續跟上節奏，上面提到了 memory pool ，相信程式員朋友們很熟悉這個名詞了，沒錯，這就是二級配置器的精髓所在，如何了解？請看下圖：
有了記憶體池，是不是就可以了，當然沒有這麼簡單。上圖中還提到了自由連結清單，這個又是何方神聖？
我們來一探究竟！
7.2 自由連結清單自由在哪？又該如何維護呢？
我們知道，一方面，自由連結清單中有些區塊已經配置設定給了客端使用，是以 free_list 不需要再指向它們；另一方面，為了維護 free-list，每個節點還需要額外的指針指向下一個節點。
那麼問題來了，如果每個節點有兩個指針？這不就造成了額外負擔嗎？本來我們設計 STL 容器就是用來儲存對象的，這倒好，對象還沒儲存之前，已經占據了額外的記憶體空間了。那麼，有方法解決嗎？當然有！再來感受一次大師的智慧！
（1）在這之前我們先來了解另一個概念——union（聯合體/共用體），對 union 已經熟悉的讀者可以跳過這一部分的内容；如果忘記了也沒關系，趁此來回顧一下：
（a）共用體是一種特殊的類，也是一種構造類型的資料結構。
（b）共用體表示幾個變量共用一個記憶體位置，在不同的時間儲存不同的資料類型和不同長度的變量。
（c）所有的共用體成員共用一個空間，并且同一時間隻能儲存其中一個成員變量的值。例如如下：
一個union 隻配置一個足夠大的空間以來容納最大長度的資料成員，以上例而言，最大長度是 double 類型，
是以 ChannelManager 的空間大小就是 double 資料類型的大小。在 C++ 裡，union 的成員預設屬性頁為 public。union 主要用來壓縮空間，如果一些資料不可能在同一時間同時被用到，則可以使用 union。
（2）了解了 union 之後，我們可以借助 union 的幫助，先來觀察一下 free-list 節點的結構
來深入了解 free_list 的實作技巧，請看下圖。
在 union obj 中，定義了兩個字段，再結合上圖來分析：
從第一個字段看，obj 可以看做一個指針，指向連結清單中的下一個節點；
從第二個字段看，obj 可以也看做一個指針，不過此時是指向實際的記憶體區。
一物二用的好處就是不會為了維護連結清單所必須的指針而造成記憶體的另一種浪費，或許這就是所謂的自由奧義所在！大師的智慧躍然紙上。
7.3 第二級配置器的部分實作内容
到這裡，我們已經基本了解了第二級配置器中 free_list 的工作原理了。附上第二級配置器的部分實作内容源碼：
太長了吧，看懵逼了，沒關系，請耐心接着往下看。
8. 空間配置器函數allocate源碼解讀
我們知道第二級配置器擁有配置器的标準接口函數 allocate()。此函數首先判斷區塊的大小，如果大于 128bytes –> 調用第一級配置器；小于128bytes–> 就檢查對應的 free_list（如果沒有可用區塊，就将區塊上調至 8 倍數的邊界，然後調用 refill(), 為 free list 重新填充空間。
8.1 空間申請
調用标準接口函數 allocate()：
NOTE：每次都是從對應的 free_list 的頭部取出可用的記憶體塊。然後對free_list 進行調整，使上一步撥出的記憶體的下一個節點變為頭結點。
8.2 空間釋放
同樣，作為第二級配置器擁有配置器标準接口函數 deallocate()。該函數首先判斷區塊大小，大于 128bytes 就調用第一級配置器。小于 128bytes 就找出對應的 free_list，将區塊回收。
NOTE：通過調整free_ list連結清單将區塊放入free list的頭部。
區塊回收納入 free_list 的操作，如圖所示：
8.3 重新填充 free_lists
（1）當發現 free list 中沒有可用區塊時，就會調用 refill() 為free_list 重新填充空間；
（2）新的空間将取自記憶體池（經由 chunk_alloc() 完成）；
（3）預設取得20個新節點（區塊），但萬一記憶體池空間不足，獲得的節點數可能小于 20。
8.4 記憶體池（memory pool）
唔…在前面提到了 memory pool，現在終于輪到這個大 boss 上場。
首先，我們要知道從記憶體池中取空間給 free_list 使用，是 chunk_alloc() 在工作，它是怎麼工作的呢？
我們先來分析 chunk_alloc() 的工作機制：
chunk_alloc() 函數以 end_free – start_free 來判斷記憶體池的“水量”（哈哈，很形象的比喻）。
具體邏輯都在下面的圖裡了，很形象吧。
如果第一級配置器的 malloc() 也失敗了，就發出 bad_alloc 異常。
說了這麼多來看一下 STL 的源碼吧。
太長了，又看懵逼了吧，沒關系，請看下圖。
NOTE：上述就是 STL 源碼當中實際記憶體池的操作原理，我們可以看到其實以共用體串聯起來共享記憶體形成了free_list的實質組成。
9.本文小結
STL 源碼本身博大精深，還有很多精妙的設計等着大家去探索。
小賀本人才疏學淺，在這裡也隻是在自己掌握的程度下寫出自己的了解，不足之處希望對大家多多指出，互相讨論學習。
這篇肝了一個禮拜的文章，在周日的晚上終于寫完了，文中所有的圖都是自己一個個親手畫的，不畫不知道，畫完之後真心感覺不容易啊。
第一次寫這種圖解的文章，不知道讀者朋友們喜不喜歡。如果回報還不錯的話，後面有時間會繼續更新類型的圖解文章。
參考文章：
《STL源碼剖析-侯捷》
https://cloud.tencent.com/developer/article/1686585
https://dulishu.top/allocator-of-stl/
10.結尾
如果覺得文章對你有幫助，歡迎分享給你的朋友，也給小賀點個這對小賀非常重要，謝謝你們，給各位小姐姐小哥哥們比心了
。
我是 herongwei ，是男人，就該對自己狠一點，祝大家周末愉快，我們下期見。