SGI stl中容器默認(rèn)使用的空間配置器是alloc嘱蛋。

空間:可以存儲(chǔ)數(shù)據(jù)的地方淋肾，可以是內(nèi)存叫潦，磁盤蝇完，甚至設(shè)備等，能讀寫就行

內(nèi)存:字面意思

空間配置器分兩種:一級(jí)配置器(__malloc_alloc_template)和二級(jí)配置器(__default_alloc_template)矗蕊。當(dāng)請(qǐng)求的空間大于128byte時(shí)使用一級(jí)配置器短蜕，小于128byte時(shí)則使用二級(jí)配置器。

一級(jí)配置器底層是對(duì)malloc和free的簡(jiǎn)單封裝傻咖。

二級(jí)配置器維護(hù)一個(gè)內(nèi)存池和空閑鏈表朋魔，當(dāng)內(nèi)存池的內(nèi)存不足以滿足需求時(shí)將使用malloc分配內(nèi)存。

為什么使用二級(jí)配置器卿操？

我們知道二級(jí)配置器的使用場(chǎng)景是需要小塊內(nèi)存時(shí)警检。如果直接向系統(tǒng)申請(qǐng)小塊內(nèi)存的話孙援，由于操作系統(tǒng)在管理和回收內(nèi)存時(shí)需要知道內(nèi)存的長(zhǎng)度等信息，而對(duì)于c++用戶而言需要的是一段內(nèi)存的起始地址而包含任何頭部信息扇雕。所以系統(tǒng)在分配內(nèi)存時(shí)將多分配一段用以保存長(zhǎng)度信息的內(nèi)存赃磨，然后將剩余的內(nèi)存返回給用戶。也就是說(shuō)用戶申請(qǐng)n bytes,假如操作系統(tǒng)用一個(gè)struct __head_t保存信息洼裤，則需要在空閑列表中尋找一塊長(zhǎng)度大于等于(n+sizeof(__head_t))的內(nèi)存邻辉，假如這段內(nèi)存起始于p,則將長(zhǎng)度自己及下一節(jié)點(diǎn)等信息放在(_head_t*)p中，然后返回(void*)(p+sizeof(__head_t))給用戶腮鞍，如果我們申請(qǐng)的小塊內(nèi)存越多則花費(fèi)也更多值骇，除此之外也將完成更多內(nèi)存碎片。

而二級(jí)配置器維護(hù)十六個(gè)不同區(qū)塊大小的空閑鏈表移国，這些鏈表節(jié)點(diǎn)都來(lái)源于配置器一次性申請(qǐng)的一大片內(nèi)存里面吱瘩，當(dāng)內(nèi)存不足時(shí)也將按照所需要內(nèi)存的2倍進(jìn)行申請(qǐng)，這將減少系統(tǒng)分配的花銷迹缀。

一級(jí)配置器

一級(jí)配置器(__malloc_alloc_template)提供的allocate和deallocate是對(duì)malloc()函數(shù)使碾，realloc()函數(shù)和free()函數(shù)的簡(jiǎn)單封裝。除此之外它的內(nèi)部還擁有一組用于處理申請(qǐng)內(nèi)存時(shí)碰到oom情況的函數(shù)指針祝懂，并提供set_new_handler接口來(lái)達(dá)成類似c++ set-new-handler的效果票摇。

二級(jí)配置器

二級(jí)配置器(__default_alloc_template)主要由兩個(gè)部分組成:空閑鏈表和內(nèi)存池。

空閑鏈表

空閑鏈表的部分是一個(gè)16個(gè)元素的數(shù)組砚蓬，每個(gè)元素就是一個(gè)空閑鏈表矢门。每個(gè)鏈表用來(lái)保存不同大小的空閑區(qū)塊，分別是8,16,24,32,40,....,128灰蛙∷钐蓿空閑鏈表每個(gè)節(jié)點(diǎn)要保存下一個(gè)節(jié)點(diǎn)的信息，為了節(jié)省空間這里使用這樣一種類型來(lái)作為節(jié)點(diǎn):

union obj

{

? ? obj * free_list_link;

? ? char data[1];

};

原理是摩梧，當(dāng)區(qū)塊被使用時(shí)物延，假如鏈表頭為free_list,則可以將它的data字段保存，將free_list賦值為free_list->free_list_link仅父，返回保存的data即可叛薯。

區(qū)塊回收時(shí)將回收的內(nèi)存當(dāng)成obj指針看待，將其free_list_link賦值為當(dāng)前free_list,再將其賦值給free_list即可驾霜。

整個(gè)過(guò)程實(shí)際上是出棧入棧

內(nèi)存池

內(nèi)存池使用兩個(gè)指針表示開(kāi)始和結(jié)束案训，當(dāng)前剩下的大小可以用指針相減計(jì)算出來(lái)买置。

內(nèi)存池用于當(dāng)鏈表區(qū)塊不足時(shí)添加新的區(qū)塊粪糙，也就是直接"回收"進(jìn)去》尴睿空閑鏈表在申請(qǐng)空間時(shí)通常使用SxN的形式蓉冈，也就是N和S大小的塊城舞。內(nèi)存池對(duì)于這些請(qǐng)求，分三種情況處理:

剩余空間大于等于SxN,直接返回給空閑鏈表寞酿。

不足SxN家夺，但是大于等于SxM,1≤M<N。這種情況下將返回SxM的空間伐弹，并通過(guò)N的引用傳回實(shí)際大小拉馋。

不足N。這個(gè)情況下惨好，首先檢查自身剩下的空間煌茴，將它填充到合適的空閑鏈表。然后用malloc分配新的內(nèi)存日川，大小是當(dāng)前請(qǐng)求的兩倍蔓腐，然后調(diào)用自己。如果malloc分配失敗龄句，意味著系統(tǒng)內(nèi)存也不足回论，則通過(guò)遍歷空閑鏈表來(lái)尋找空閑的，足夠大的塊返回給空閑鏈表分歇。比如申請(qǐng)8x2傀蓉，內(nèi)存池為0了，而空閑鏈表(區(qū)塊大小為64)還有沒(méi)用的塊职抡，也可以拿來(lái)使用僚害。如果也沒(méi)，就直接調(diào)用一級(jí)配置器繁调，觸發(fā)異常萨蚕，興許系統(tǒng)會(huì)整理內(nèi)存，然后就有了蹄胰。

這一整個(gè)就是stl中空間配置器alloc的行為了岳遥。