空間配置器是STL用來分配和管理空間的類型凌受；STL allocator將對象的構(gòu)造齿桃、析構(gòu)與內(nèi)存的配置和釋放分開 惠窄。對象的構(gòu)造和析構(gòu)由construct（placement new在指定空間創(chuàng)建對象） 和destroy負(fù)責(zé)（全局函數(shù)）谅辣。內(nèi)存的配置和釋放由allocate和deallocate負(fù)責(zé)懦窘。

SGI STL的兩級(jí)空間配置器

SGI STL 為了避免小型區(qū)塊的內(nèi)存碎片（fragment）問題,SGI設(shè)計(jì)了兩級(jí)配置器

當(dāng)配置區(qū)塊大于128字節(jié)時(shí)前翎，調(diào)用第一級(jí)配置器。小于128字節(jié)時(shí)調(diào)用第二級(jí)配置器畅涂。

第一級(jí)配置器（alloc）的allocate()和deallocate()函數(shù)只是簡單調(diào)用malloc()和free()函數(shù)港华；

如果出現(xiàn)了out_of_memory錯(cuò)誤，就不斷調(diào)用__malloc_alloc_oom_handler()錯(cuò)誤處理函數(shù)午衰，去嘗試釋放內(nèi)存立宜，然后重新調(diào)用malloc分配。不斷循環(huán)臊岸，直到分配成功橙数。（如果沒設(shè)置這個(gè)處理函數(shù)，就拋出bad_alloc異常）

第二級(jí)配置器為了降低額外開銷（overhead）扇单，采用內(nèi)存池(memory pool)管理內(nèi)存分配商模；具體使用的內(nèi)存塊從free-list(自由鏈表)中提取出。

具體流程為：

1.當(dāng)需要申請的內(nèi)存大小N 大于128bytes時(shí)蜘澜，直接使用第一級(jí)配置器施流，使用malloc分配

2.小于等于128bytes時(shí)，使用內(nèi)存池管理鄙信。內(nèi)存池管理步驟為：

a. 首先查看是否有可用的free-list瞪醋，如果有就直接使用。沒有的話装诡，將所需區(qū)塊大小上調(diào)至8的倍數(shù)银受，調(diào)用 refill()為free list重新分配空間践盼。

b. 新的空間將取自內(nèi)存池（經(jīng)由chunk_alloc()完成），如果內(nèi)存池不夠用宾巍，從堆空間（malloc配置空間） 拿來補(bǔ)充內(nèi)存池咕幻。如果堆空間也不夠了，就調(diào)用第一級(jí)配置器來補(bǔ)充內(nèi)存池顶霞。因?yàn)榈谝患?jí)配置器有out-of- memory處理機(jī)制肄程，看看它能不能釋放其它內(nèi)存然后拿來此處使用（如果可以就成功，否則bad_alloc異常）选浑。

這里要注意一點(diǎn)蓝厌，最初內(nèi)存池和free list都為空。

內(nèi)存池如何refill()鏈表

當(dāng)free list中無可用區(qū)塊古徒，將向內(nèi)存池申請空間拓提。當(dāng)內(nèi)存池空間充足時(shí)，新的空間將缺省獲得20個(gè)新的區(qū)塊大小N（所需內(nèi)存空間上調(diào)8的倍數(shù)）隧膘。當(dāng)內(nèi)存池空間不滿足需求量代态，先盡可能分配出大小為N的內(nèi)存塊。如果內(nèi)存池剩余空間小于N舀寓，先將內(nèi)存池的殘余分給free list,然后向堆空間申請內(nèi)存胆数。

內(nèi)存池以及free list一次配置這么大的空間，是為了不頻繁申請內(nèi)存互墓，減小不必要的開銷。

free list

free-list：是有16個(gè)大小分別為8蒋搜，16一直遞增到128字節(jié)的內(nèi)存塊構(gòu)成的鏈表篡撵。因此第二級(jí)配置器最大只能分配128字節(jié)。

free-list相比鏈表豆挽，如何實(shí)現(xiàn)減少額外負(fù)擔(dān)育谬？

普通鏈表不僅要有指針指向?qū)嶋H區(qū)塊，還要維護(hù)指向下一個(gè)節(jié)點(diǎn)的指針帮哈，所以會(huì)有額外的負(fù)擔(dān)膛檀。

free-list采用的是聯(lián)合體（union，算是一種數(shù)據(jù)類型）娘侍，聯(lián)合體數(shù)據(jù)成員共享一塊內(nèi)存咖刃。兩個(gè)數(shù)據(jù)成員，一個(gè)是指向下一個(gè)節(jié)點(diǎn)的指針憾筏，另外一個(gè)是指向?qū)嶋H區(qū)塊的指針嚎杨。

這兩個(gè)數(shù)據(jù)成員在任何時(shí)刻只有一個(gè)有值，對應(yīng)于分配的兩種情況——分配和不分配氧腰。不分配時(shí)枫浙，使用的是指向下一節(jié)點(diǎn)的這一數(shù)據(jù)成員刨肃。分配時(shí)（區(qū)塊拔出，不用指向下一節(jié)點(diǎn)）箩帚，則使用的指向?qū)嶋H區(qū)塊的這一數(shù)據(jù)成員真友。

內(nèi)存池：是一種內(nèi)存分配方式，頻繁使用new紧帕、malloc會(huì)造成大量內(nèi)存碎片锻狗。并且頻繁分配和回收內(nèi)存會(huì)降低性能。內(nèi)存池一次申請一定數(shù)量的內(nèi)存塊留作備用焕参，因此不用頻繁去申請新的資源轻纪。

聯(lián)合體（union）

聯(lián)合體（union）是一種節(jié)省空間的類，其特性是一個(gè)union可以有多個(gè)數(shù)據(jù)成員叠纷，但是在任意時(shí)刻只能有一個(gè)數(shù)據(jù)成員可以有值刻帚。聯(lián)合體的大小為最大數(shù)據(jù)成員的大小，本質(zhì)是數(shù)據(jù)成員共享內(nèi)存涩嚣，從而實(shí)現(xiàn)節(jié)省空間的目的崇众。

聯(lián)合體與類的區(qū)別

• 聯(lián)合體的數(shù)據(jù)成員默認(rèn)為public，與struct相同航厚，而class默認(rèn)為private顷歌。

• 聯(lián)合體不能作為基類，不能繼承幔睬，因此數(shù)據(jù)成員也不能有虛函數(shù)

• union的數(shù)據(jù)成員不能有引用類型（引用必須初始化且不能修改綁定）

• C++11允許union含有定義了構(gòu)造函數(shù)或拷貝控制成員的類類型成員