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