4.2
內(nèi)存分配器的工作方式
（本節(jié)內(nèi)容可以參考操作系統(tǒng)書(shū)籍，cuigang）
內(nèi)存分配器如何工作？它管理一個(gè)由raw bytes所組成的內(nèi)存池。薄記結(jié)構(gòu)可以簡(jiǎn)單如下：
struct MemControlBlock{
std::size_t size_;
bool available_;
};
MemControlBlock對(duì)象管理的內(nèi)存緊隨其后，大小 size_，然后是另一個(gè)控制塊。初始時(shí)，內(nèi)存池中只有一個(gè)MemControlBlock，并將所有內(nèi)存視為一大塊，這就是所謂root控制塊，永不離開(kāi)最初位置。以
+===================+=================+==================+
| available_ : ture | size_ : 1048571 | mem[1048571] |
+===================+=================+==================+
|
|
|-----> 1 byte <----|----> 4 bytes <--|-> 1048571bytes <-|
|-----------------------> 1048576 bytes <----------------|
每次分配都引發(fā)一次線性查找，找到一個(gè)合適區(qū)塊，適合策略有最先匹配法則（first fit）、最佳匹配（best
fit），最差匹配（worst fit），甚至隨機(jī)匹配（random fit）。有趣的是最差匹配比最佳匹配好！
每次歸還區(qū)塊，同樣需要一次線性搜索，找出待歸還區(qū)塊的前一區(qū)塊并調(diào)整大小。
如你所看，這一策略時(shí)間上并非高效。但空間上開(kāi)銷較小，甚至我們可以再調(diào)整：
//注意下面代碼依賴編譯器和平臺(tái)
struct MemControlBlock{
std::size_t size_ : 31;
bool available_ : 1;
};
為了前序遍歷，我們可以定義為雙向鏈表：
struct MemControlBlock{
bool available_;
MemControlBlock* next_;
MemControlBlock* prev_;
};
這里我們不需要size_了，我們可以通過(guò)this->next - this 來(lái)得到。
盡管如此，分配動(dòng)作還是得消耗線性時(shí)間。要減輕這樣的消耗，有如多巧妙技術(shù)可用，但都各有利弊，存在某種情況下的不良性能（參考Knuth著作）。這里我們不對(duì)其討論，我們的焦點(diǎn)是可最佳處理小型對(duì)象的“專用分配器”。
4.3
小型對(duì)象分配器
本章介紹的小型對(duì)象分配器分為4層結(jié)構(gòu)。如圖所示，下層提供功能供上層使用。
+-------------------+
| SmallObject |
+-------------------+
| SmallObjAllocator |
+-------------------+
| FixedAllocator |
+-------------------+
| Chunk
|
+-------------------+
最下層是Chunk對(duì)象，每一個(gè)Chunk管理一大塊內(nèi)存，此大塊內(nèi)存包含整數(shù)個(gè)固定大小的區(qū)塊。可以用來(lái)分配和歸還，當(dāng)其中沒(méi)有剩余時(shí)，分配失敗返回零。
第二層是FixAllocator
class，其以Chunk為構(gòu)件。主要用來(lái)滿足那些“累計(jì)總量超過(guò)Chunk容量”的請(qǐng)求。FixAllocator通過(guò)一個(gè)array（實(shí)際是vector）組合Chunks。如果所有Chunk都被使用，FixAllocator分配新Chunk，并加入array，來(lái)滿足需求。
第三層是SmallObjectAllocator提供通用分配/歸還函數(shù)。擁有數(shù)個(gè)FixedAllocator對(duì)象，每個(gè)負(fù)責(zé)分配某特定大小對(duì)象。根據(jù)申請(qǐng)bytes個(gè)數(shù)不同，SmallObjAllocator對(duì)象會(huì)將內(nèi)存分配申請(qǐng)分發(fā)。如果請(qǐng)求量過(guò)大，會(huì)轉(zhuǎn)交系統(tǒng)new。
第四層是SmallObject，它包裝FixedAllocator，以便向C++
classes提供封裝良好的分配服務(wù)。SmallObject重載new和delete。你只需要讓你的對(duì)象派生于SmallObject。