STL 源碼剖析空間配置器

以STL的運用角度而言，空間配置器是最不需要介紹的東西，它總是隱藏在一切組件（更具體地說是指容器，container）的背后
但是STL的操作對象都存放在容器的內部，容器離不開內存空間的分配
為什么不說allocator是內存配置器而說它是空間配置器呢？因為空間不一定是內存，空間也可以是磁盤或其它輔助存儲介質。是的，你可以寫一個allocator, 直接向硬盤取空間。以下介紹的是SGI STL提供的配置器，配置的對象，這里分配的空間是指分配內存

?set_new_handler()總結

namespace JJ
{template <class T>inline T* _allocate(std::ptrdiff_t size,T*){std::set_new_handler(0);T* tmp = (T*)(::operator new ((std::size_t)(size * sizeof(T))));if (tmp == 0){std::cerr << "out of memory " << std::endl;exit(1);}return tmp;}template <class T>inline void _deallocate(T* buffer){::operator delete (buffer);}template <class T1,class T2>inline void _construct(T1* p,const T2& value){new(p) T1(value);}template <class T>inline void _destroy(T* ptr){ptr->~T();}template <class T>class allocator{public:typedef T           value_type;typedef T*          pointer;typedef const T*    const_pointer;typedef T&          reference;typedef const T&    const_reference;typedef size_t      size_type;typedef ptrdiff_t   difference_type;//rebind allocator of type Utemplate <class U>struct rebind{typedef allocator<U> other;};//hint used for locality. ref.[Austern],pl89pointer allocate(size_type n,const void* hint = 0){return _allocate((difference_type)n,(pointer)0);}void deallocate(pointer p,size_type n){_deallocate(p);}void construct(pointer p,const T& value){_construct(p,value);}void destroy(pointer p){_destroy(p);}pointer address(reference x){return (pointer)&x;}const_pointer const_address(const_reference x){return (const_pointer)&x;}size_type max_size()const{return size_type (UINT_MAX / sizeof(T));}};
}

SGI STL在這個項目上根本就逸脫了 STL標準規格，使用一個專屬的、擁有次層配置(sub-allocation)能力的、效率優越的特殊配置器，稍后有詳細介紹
?備次配置力 (sub-allocation)的 S G I 空間配置器
SGI STL的配置器與眾不同，也與標準規范不同，其名稱是a llo c 而非 allo ca to r,而且不接受任何參數。換句話說，如果你要在程序中明白采用SGI配置器，則不能采用標準寫法：

?SGI STL allocator未能符合標準規格，這個事實通常不會給我們帶來困擾，因為通常我們使用缺省的空間配置器，很少需要自行指定配置器名稱，而SGI STL的每一個容器都已經指定其缺省的空間配置器為a llo c .例如下面的vector聲明：

?S G I標準的空間配量器，std::allocator
SG I特殊的空間配置器，std::alloc
上一節所說的a llo c a to r 只是基層內存配置/釋放行為(也就是 ::operator new和 : ：operator delete)的一層薄薄的包裝，并沒有考慮到任何效率上的強化. S G I另有法寶供其本身內部使用。

?這其中的new算式內含兩階段操作3： (1 )調用 ::operator new配置內存; ⑵ 調用Foo：:Foo()構造對象內容。delete算式也內含兩階段操作：(1)調用Foo： :-Foo ()將對象析構；(2 ) 調用：：operator delete釋放內存。
為了精密分工，STL a llo c a to r決定將這兩階段操作區分開來。內存配置操作由 alloc： al locate ()負責，內存釋放操作由alloc : : deallocate ()負責；對象構造操作由：：construct:()負責，對象析構操作由：；destroy負責

?內存空間的配置/釋放與對象內容的構造/析構，分別著落在這兩個文件身上。其中 <stl_construct .h>定義有兩個基本函數：構造用的 construct() 和析構用的destroy。。在一頭栽進復雜的內存動態配置與釋放之前，讓我們先看清楚這兩個函數如何完成對象的構造和析構。

?構造和析構基本工具：co n stru ct()和 destroy()

?這兩個作為構造、析構之用的函數被設計為全局函數，符合STL的規范.此外，STL還規定配置器必須擁有名為construct ()和 destroy ()的兩個成員函數(見2.1節 )，然而真正在SGI STL中大顯身手的那個名為std：：alloc的配置器并未遵守這一規則(稍后可見
上述 construct ()接受一個指針p 和一個初值value,該函數的用途就是將初值設定到指針所指的空間上。C++的 placement new 運算子5 可用來完成這一任務。
destroy() 有兩個版本，第一版本接受一個指針，準備將該指針所指之物析構掉。這很簡單，直接調用該對象的析構函數即可。第二版本接受first和 last 兩個迭代器(所謂迭代器，第3 章有詳細介紹)，準備將 [first, last)范圍內的所有對象析構掉。我們不知道這個范圍有多大，萬一很大，而每個對象的析構函數都無關痛癢(所謂rrzvia/destructor), 那么一次次調用這些無關痛癢的析構函數，對效率是一種傷害。
因此，這里首先利用value_type()獲得迭代器所指對象的型別，再利用 _type_traits＜ T＞判斷該型別的析構函數是否無關痛癢.若是 (一true_type), 則什么也不做就結束；若否 (— false_type), 這才以循環方式巡訪整個范圍, 并在循環中每經歷一個對象就調用第一個版本的destroy ()

空間的配置與釋放， std::alloc

對象構造前的空間配置和對象析構后的空間釋放，由＜stl_alloc.h＞負責， S G I 對此的設計哲學如下：

?C + + 的內存配置基本操作是 ::operator new ( ) , 內存釋放基本操作是 : operator delete)). 這兩個全局函數相當于C 的malloc ( ) 和 f r e e O 函數。是的，正是如此，S G I 正是以malloc ()和 f r e e O 完成內存的配置與釋放。?
考慮到小型區塊所可能造成的內存破碎問題，S G I 設計了雙層級配置器，第一級配置器直接使用 malloc() 和 fme(),第二級配置器則視情況采用不同的策略：當配置區塊超過128 bytes時，視之為 “足夠大”，便調用第一級配置器；當配置區塊小于128 bytes時，視之為 “過小”，為了降低額外負擔(overhead,見 2.2.6 節 )，便采用復雜的memory pool整理方式，而不再求助于第一級配置器, 整個設計究竟只開放第一級配置器，或是同時開放第二級配置器，取決于_ use_malloc是否被定義(唔，我們可以輕易測試出來，SGI STL并未定義一_USE_MALLOC)

?無論alloc被定義為第一級或第二級配置器，SGI還為它再包裝一個接口如下，使配置器的接口能夠符合STL規格：

?其內部四個成員函數其實都是單純的轉調用，調用傳遞給配置器(可能是第一級也可能是第二級)的成員函數.這個接口使配置器的配置單位從bytes轉為個別元素的大小(sizeof (T) ) . SGI STL容器全都使用這個simple_alloc接口，例如：

?第一級配置器 ―malloc_alloc_template 剖析

?第一級配置器以malloc () , free () , realloc ()等 C 函數執行實際的內存配置、釋放、重配置操作，并實現出類似C + + new-hand宜了的機制。是的，它不能直接運用 C++ new-handier機制，因為它并非使用:：operator n e w 來配置內存。?
所謂 C++ new handler機制是，你可以要求系統在內存配置需求無法被滿足時，調用一個你所指定的函數。換句話說，一旦：：operator new無法完成任務，在丟出 std::bad_alloc異常狀態之前，會先調用由客端指定的處理例程。該處理例程通常即被稱為new-handiero new-handier解決內存不足的做法有特定的模式，請參考《婀伽 e C++》2 e 條款7?
handler

?程通常即被稱為new-handiero new-handier解決內存不足的做法有特定的模式
注意，S G I 以 malloc而非 :：operator new來配置內存(我所能夠想象的一個原因是歷史因素，另一個原因是C + + 并未提供相應于 realloc () 的內存配置操作 )，因此，S G I 不能直接使用C + + 的 set_new_handler (),必須仿真一個類似的 set_malloc_handler ()?
請注意，S G I 第一級配置器的 allocate ()和 realloc ( ) 都是在調用 malloc ()和 realloc ()不成功后，改調用 oom_malloc ()和 oom_realloc ()=后兩者都有內循環，不斷調用 “內存不足處理例程”，期望在某次調用之后，獲得足夠的內存而圓滿完成任務。但如果 “內存不足處理例程”并未被客端設定，oom_malloc() 和 oom_realloc() 便老實不客氣地調用 — THROW_BAD_ALLOC,丟出 bad_alloc異常信息，或利用 exit(l)硬生生中止程序。?
記住，設計 “內存不足處理例程”是客端的責任，設定 “內存不足處理例程”也是客端的責任.再一次提醒你，“內存不足處理例程”解決問題的做法有著特定的模式，請參考［Meyers98］條款7

第二級配置器 __default_alloc_template 剖析

第二級配置器多了一些機制，避免太多小額區塊造成內存的碎片。小額區塊帶來的其實不僅是內存碎片，配置時的額外負擔(overhead)也是一個大問題％額外負擔永遠無法避免，畢竟系統要靠這多出來的空間來管理內存，如圖2-3所示。但是區塊愈小，額外負擔所占的比例就愈大，愈顯得浪費。

SGI第二級配置器的做法是，如果區塊夠大，超過128 bytes時，就移交第一級配置器處理.當區塊小于128 bytes時，則以內存池(memory pool)管理，此法又稱為次層配置(sub-allocation)：
每次配置一大塊內存，并維護對應之自由鏈表 {free-list). 下次若再有相同大小的內存需求，就直接從free-lists中撥出。如果客戶端釋還小額區塊，就由配置器回收到free-lists中—— 是的，別忘了，配置器除了負責配置，也負責回收。
為了方便管理，SGI第二級配置器會主動將任何小額區塊的內存需求量上調至8 的倍數(例如客端要求30 bytes,就自動調整為32 bytes),并維護 16 個free-lists,各自管理大小分別為 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128 bytes的小額區塊。free-lists的節點結構如下：

諸君或許會想，為了維護鏈表(lists), 每個節點需要額外的指針(指向下一個節點)，這不又造成另一種額外負擔嗎？你的顧慮是對的，但早已有好的解決辦法。
注意’上述 obj所用的是union,由于union之故，從其第一字段觀之， obj可被視為一個指針，指向相同形式的另一個。切從其第二字段觀之。obj可被視為一個指針，指向實際區塊，如圖2-4所示。一物二用的結果是，不會為了維護鏈表所必須的指針而造成內存的另一種浪費(我們正在努力節省內存的開銷呢)。這種技巧在強型(strongly typed)語言如Java中行不通，但是在非強型語言如C++中十分普遍

?空間配置函數 allocate()

此函數首先判斷區塊大小，大于 128 bytes就調用第一級配置器，小于 128 bytes就檢查對應的free listo 如果 free list之內有可用的區塊，就直接拿來用，如果沒有可用區塊，就將區塊大小上調至8 倍數邊界，然后調用refilio, 準備為free list重新填充空間。refill ()將于稍后介紹。

?free_list維護8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128 bytes的小額區塊，需要分配內存的時候，如上圖所示，需要分配的大小是96，my_free_list先找到96對應的鏈條，result指向想要的96區塊，my_free_list移動到下一個區塊，將result需要的區塊排除到鏈外，表示為其分配了區間

空間釋放函數 deallocate。

身為一個配置器， _ default_alloc_template 擁有配置器標準接口函數deallocated o 該函數首先判斷區塊大小，大于128 bytes就調用第一級配置器，小于128 bytes就找出對應的free list,將區塊回收。

?使用q指向需要回收的空間，使用my_free_list找到與之大小相匹配的存儲區塊的鏈條，使用q銜接對應的?存儲區塊的鏈條位置，移動初始位置

重新填充 free lists

回頭討論先前說過的allocate (). 當它發現free list中沒有可用區塊了時，就調用 refillO,準備為free list重新填充空間.新的空間將取自內存池(經由 chunk_alloC ()完成 )。缺省取得2 0 個新節點(新區塊)，但萬一內存池空間不足，獲得的節點數(區塊數)可能小于20：

?內存池 ( m e m o r y pool )

從內存池中取空間給斤e。使用，是 chunk_alloc()的工作：?

上圖存在一個錯誤，size是需要的大小，nobjs是需要的數量

?上述的chunk_alloc ( ) 函數以end_free - s t a r t _ f r e e 來判斷內存池的水量。如果水量充足，就直接調出20個區塊返回給free list。如果水量不足以提供20 個區塊，但還足夠供應一個以上的區塊，就撥出這不足20個區塊的空間出去。這時候其pass by reference的n o b js參數將被修改為實際能夠供應的區塊數。如果內存池連一個區塊空間都無法供應，對客端顯然無法交待,此時便需利用m alloc?從 heap中配置內存，為內存池注入活水源頭以應付需求。新水量的大小為需求量的兩倍，再加上一個隨著配置次數增加而愈來愈大的附加量。

?如果一開始free_list 和內存池都是空的，當用戶需求數據的時候，發現沒有內存，申請的空間是20的兩倍，也就是40,一半內存交給free_list用于數據的維護，一半數據給內存池；當再次申請內存時，所對應的free_list不存在數據，就會先向內存池索要內存，滿足一部分之后，將剩余的內存交給 free_list；

?內存基本處理工具

STL定義有五個全局函數，作用于未初始化空間上? 這樣的功能對于容器的實現很有幫助，我們會在第4章容器實現代碼中，看到它們肩負的重任?前兩個函數是2.2.3節說過的、用于構造的construct ()和用于析構的destroy (),另三個函數uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n(), 分別對應于高層次函數copy () fill () fill_n() 這些都是STL算法，將在第6 章介紹。如果你要使用本節的三個低層次函數，應該包含 <memory>, 不過SG I把它們實際定義于 <stl_uninitialized>。

uninitialized_copy

?uninitialized_copy ()使我們能夠將內存的配置與對象的構造行為分離開來。如果作為輸出目的地的[result/ result+(last-first))范圍內的每一個迭代器都指向未初始化區域，則 uninitialized_copy ()會使用copy constructor,給身為輸入來源之[first, last)范圍內的每一個對象產生一份復制品’放進輸出范圍中。換句話說，針對輸入范圍內的每一個迭代器該函數會調用
construct (&* (result+ (i-f irst) ) , *i), 產生 * i 的復制品，放置于輸出范圍的相對位置上。式中的construct ()已于2.2.3節討論過。
result 指向內存拷貝的目的地址，i和first指向的是同一個內存區間，使用i和first之間的差值，將*i（元素的數值）拷貝到指定的位置
果你需要實現一個容器，uninitialized.copy() 這樣的函數會為你帶來很大的幫助，因為容器的全區間構造函數(range constructor) 通常以兩個步驟完成：

?C++ 標準規格書要求 uninitialized_copy () 具有 'commit or rollback 語意，意思是要么“構造出所有必要元素”，要么(當有任何一個copy constructor失敗時)“不構造任何東西””

2.3.2 u n in itia liz e d _fill

?&*i? ?其實就是元素的位置，*i代表元素的數值，加上&，就是取地址，后面接入x，construct就是在指定的位置上填寫x
與 uninitialized_copy() 一樣,uninitialized_f ill ()必須具備 acommit or rollback語意，換句話說，它要么產生出所有必要元素，要么不產生任何元素。如果有任何一個 copy constructor 丟出異常(exception) ,uninitialized_f ill (),必須能夠將已產生的所有元素析構掉。

u n in itia liz e d _ fill_ n