為 STL 容器撰寫自訂記憶體配置器：基於 SGI 二級配置器的記憶體池實作

設計目標

• 降低小區塊頻繁 new/delete 的碎片與效能開銷。
• 符合 C++ Allocator 概念（value_type, pointer, rebind, allocate/deallocate, construct/destroy, max_size 等）。
• 支援 map, set, multimap, multiset；vector 因大小不固定暫不支援完美回收。

核心資料結構

enum { NODENUMS = 2 };          // 自由鏈表檔案數（示範用，實際應依區塊大小動態）
union Obj { Obj* next; char data[1]; };  // 節點
struct Cookie {                 // 記憶體池控制塊
    char* start_free; char* end_free;
    short free_list_index[NODENUMS];
    Obj*  free_list[NODENUMS];
    int   use_count[NODENUMS];
    // 共享記憶體擴充欄位略
};
static Cookie* pool = nullptr;

關鍵演算法

1. round_up(bytes)：對齊至 sizeof(Obj) 倍數。
2. freelist_index(bytes)：依區塊大小對應自由鏈表索引，動態註冊新尺寸。
3. chunk_alloc(size, nobjs)：從池大塊切割 nobjs 個 size 區塊，不足時嘗試較少數量。
4. refill(n)：chunk_alloc 取得新區塊，串成自由鏈表回傳首節點。
5. allocate(n)：對應自由鏈表取節點，空則 refill。
6. deallocate(p, n)：節點插回自由鏈表頭（註：vector 批次釋放需逐節點插入，當前簡化為單節點）。

初始化與除錯

static void InitPool() {
    int pool_size = 1000;
    pool = (Cookie*)malloc(sizeof(Cookie) + pool_size);
    pool->start_free = (char*)pool + sizeof(Cookie);
    pool->end_free = (char*)pool + sizeof(Cookie) + pool_size;
    // 索引、鏈表、計數歸零
}
static void DumpPool() { /* 列印池使用量、各自由鏈表節點數 */ }

使用範例

#include 

已知限制與改進方向

• vector 分配大小不固定，回收時無法直接對應單一自由鏈表，需實作大區塊回收合併（buddy system 或 segregated fit）。
• 執行緒安全：需在關鍵區加入 mutex 或改用 thread-local pool。
• 共享記憶體：將 Cookie 置於 shm_open/mmap 區域，配合信號量同步，即可跨進程共用池。
• 對齊支援：C++17 std::align_val_t 需在 allocate 額外處理。