?
[原創文章歡迎轉載，但請保留作者信息]
Justin 于 2009-10-28
看的版本是
侯捷的繁體版
，有些術語乃至字都有些難懂。進度和理解程度竟然也沒比英文的好多少@#￥%
侯捷把allocator譯為配置器。配置器的接口大多不被STL用戶看到，它的重要性在于幾乎所有的其他STL對象都會請到它來配置(內存)資源。
STL自己的配置器有兩套。第一套allocate是簡單的對C++的operator new和delete的封裝，STL自己沒有用，也不推薦別人用(那你寫來做啥捏？)；第二套alloc是基于malloc、realloc和free實現的。alloc自身又有兩級：
-
二級配置器實際上是個內存倉庫管理員。當有資源申請需求時，alloc會先判斷所需空間的大小。如果等于或小于128bytes，就使用二級配置器。這個內存倉庫管理員有16個儲藏室，分別存放著分配好的8bytes、16bytes、24bytes直至128bytes的內存塊。二級配置器的設計基本就是STL allocator的精華了，本文最后會繼續記錄有什么需要注意的地方。
-
當需求空間大于128bytes時，我們就需要一級配置器申請。它沒有什么現成的資源可以直接分配，而是用malloc/realloc向系統討的。對于申請失敗的處理，STL仿照C++的處理機制，提供了接口由客戶指定函數作為new handler，以處理內存不足的情況。如果用戶沒有指定相應的函數，則直接拋出異常。
OK，重新回到二級配置器的可圈可點之處：
-
union的使用。“內存倉庫管理員”的16個“儲藏室”實際上是16個單向的linked-list，list中的每個節點就是一塊內存。一塊掛在list上的內存是沒有被人用的，所以書上說它叫free list。說實話，如果是我來做這樣的list的話，節點的設計一定是小學生水平，用一個struct，里面兩個指針：一個指向空閑的內存，一個指向下一個節點。STL給我上了一課：使用union。(好吧，我還是要抄一下代碼)：
union?obj?
{
??????union?obj*?free_list_link;
??????char?client_data[1];?/**//*?The?client?sees?this.?*/
};
我認為這里巧妙的利用了free list的這一個特點：當一塊內存還掛在list上時，沒有人在意這塊內存里是什么；當真的有人要讀寫這塊內存的時候(也就是已經分配給用戶使用的時候)，這塊內存已經和list沒有任何瓜葛了。
因此，同一塊內存就可以在不同的時間扮演不同的角色：掛在list的時候就儲存下一塊內存的地址，脫離list后就隨便你存放什么了。union幾乎就是為這一功能量身定做的！減少了原來小學生設計的50%空間消耗！哇呀呀，太巧妙啦～～（請原諒我的淺薄，不知為不知，是知也……）
-
當申請空間的大小不是8bytes的整數倍時，用一個函數ROUND_UP向上取整為8bytes的整數倍數。這個函數是用位操作一次實現的。(好吧，我會去看Hacker’s Delight的……)
-
當沒有某一個“儲藏室”內內存用完了，而且這個時候又有用戶申請時(哪壺不開提哪壺啊)的處理方法比較曲折，以下是我的解讀(當然還是要免責一下：極小可能是完全正確的@#￥%)
?? 碰到開門后發現“儲藏室”沒有存貨的時候，二級配置器的第一個反應就是向內存池(memory pool)求助(外援？)：
-
如果內存池有足夠的貨，就直接把需要的內存撥到相應的list上(發貨到儲藏室)。大功告成。
-
如果內存池還有空余內存，但是不能完全滿足需要，那就本著互助互惠的原則，能給多少就給多少并且告訴你我只能給你XX個了，剩下的你自己去想辦法吧。仁至義盡。
-
如果內存池的庫存連一個單元的需求都滿足不了了，面對的事情就比較羅嗦了：
-
先看看內存池還有沒有剩下的資源，如果有，雖然不能滿足當前的申請需要(比如說是56bytes)，但可以放到更小一些的“儲藏室”里嘛(比如說24bytes)。既然來了，能拿走的就拿走，總比空手回去好……
-
通過malloc向系統要資源(爸，我要你的錢)。因為是malloc，所以是在堆上(heap)找空閑的內存。既然是申請，自然就有以下兩種結果：
-
malloc成功，總算抓住一根救命稻草。后面的工作就簡單了，把堆上的內存扔到內存池，然后通過函數嵌套重新回到內存池里申請資源。
-
malloc失敗(兒啊，家里也不寬裕了……)。外援是援不了了，這次真的是只能靠自己了。重新檢查free list(儲藏室)里的可用資源，不過這回是看看更大尺寸的free list里有沒有可以用的(比如申請的是56bytes，這次回頭看看有沒有64bytes、72bytes等可以利用的內存塊)，如果有，就拿出一塊，放回到內存池里。接下來就是通過函數嵌套重新回到內存池里去找資源了。說白了這種做法就是拆東墻補西墻@#￥%
如果自己家里也沒存貨了(所有大的儲藏室都沒有空余的內存塊可以返回到內存池里)，還真是屋漏偏逢連夜雨啊……沒有其他辦法了，只好求助本家兄弟——一級配置器，反正如果它也搞不定，就拋出異常，誰愛管就管去吧，老子管不了也不想管了@#￥%
-
__true_type與__false_type的使用。這個我會再專門寫一篇學習筆記。【鏈接臨時占位】
其實真正的STL配置器應該要更加復雜，因為侯捷在寫這本書的時候為了省事就把多線程(書中稱為多緒)的部分給跳過了。