STL文件的包含關(guān)系：
SGI STL 設(shè)計(jì)了雙層級(jí)配置器。第一層配置器直接使用malloc() 和 free().第二層配置器則視情況采用不同的策略：但配置區(qū)塊超過(guò) 128 bytes時(shí)，調(diào)用第一級(jí)配置器。當(dāng)配置區(qū)塊小于 128 bytes時(shí)，采用復(fù)雜的 memory pool 方式。下面我們分別簡(jiǎn)單的介紹一下第一級(jí)和第二級(jí)配置器。
第一級(jí)__malloc_alloc_template
第一級(jí)的配置比較簡(jiǎn)單，其實(shí)流程是這樣的：
1.我們通過(guò)allocate()申請(qǐng)內(nèi)存，通過(guò)deallocate()來(lái)釋放內(nèi)存，通過(guò)reallocate()重新分配內(nèi)存。
2.當(dāng)allocate()或reallocate()分配內(nèi)存不足時(shí)會(huì)調(diào)用oom_malloc()或oom_remalloc()來(lái)處理。
3.當(dāng)oom_malloc() 或 oom_remalloc()還是沒(méi)能分配到申請(qǐng)的內(nèi)存時(shí)，會(huì)轉(zhuǎn)如下兩步中的一步：
a).調(diào)用用戶自定義的內(nèi)存分配不足處理函數(shù)(這個(gè)函數(shù)通過(guò)set_malloc_handler() 來(lái)設(shè)定)，然后繼續(xù)申請(qǐng)內(nèi)存！
b).如果用戶未定義內(nèi)存分配不足處理函數(shù)，程序就會(huì)拋出bad_alloc異?；蚶胑xit(1)終止程序。
第二級(jí)配置__default_alloc_template
SGI第二級(jí)空間配置器較第一級(jí)空間配置器加入了內(nèi)存池(memory pool)管理，即次層配置。當(dāng)所申請(qǐng)的空間大于128bytes時(shí)，直接調(diào)用一級(jí)空間配置器處理，小于128bytes時(shí)，使用次層配置器管理。申請(qǐng)的空間不足8的倍數(shù)，默認(rèn)提升為最近的8的整數(shù)倍的空間大小。
二級(jí)內(nèi)存配置器（memory pool）的數(shù)據(jù)結(jié)構(gòu)采用的是freelist的數(shù)組，其實(shí)這個(gè)數(shù)據(jù)結(jié)構(gòu)實(shí)際上就是一個(gè)鄰接表（表示‘圖’的數(shù)據(jù)結(jié)構(gòu)之一），只是組成數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)類型所表示的實(shí)際意義發(fā)生了一些變化。
數(shù)組的長(zhǎng)度是16（128÷8=16），每個(gè)數(shù)組元素指向一個(gè)freelist頭節(jié)點(diǎn)，所以memory pool實(shí)際上就是16個(gè)freelists。每個(gè)freelist是一個(gè)單鏈表，單鏈表中的每個(gè)結(jié)點(diǎn)代表固定字節(jié)數(shù)的內(nèi)存塊。比如第一個(gè)freelist（數(shù)組的頭元素指向的freelist），表示由表示容量為8字節(jié)的內(nèi)存塊結(jié)點(diǎn)組成的單鏈表。那么按照數(shù)組順序，依次代表的是16，24，32，40，48，56，64，72，80，88，96，104，112，120，128字節(jié)的freelist。
參考上圖，假設(shè)我現(xiàn)在要申請(qǐng)大小為 56bytes 的內(nèi)存空間，那么就會(huì)到free lists 的第 7 個(gè)元素所指的鏈表上去找。如果此時(shí) #7元素所指的鏈表為空怎么辦？這個(gè)時(shí)候就要調(diào)用refill()函數(shù)向內(nèi)存池申請(qǐng)N(一般為20個(gè))個(gè)大小為56bytes的內(nèi)存區(qū)塊，然后掛到 #7 所指的鏈表上。這樣，申請(qǐng)者就可以得到內(nèi)存塊了。allocate()過(guò)程圖如下：
deallocate()函數(shù)釋放內(nèi)存的步驟如下圖：
資料來(lái)自：
