C++ Primer 筆記：優化內存分配——通用緩存分配器基類 CachedObj

動機

頻繁 new/delete 小對象（如鏈表節點）會導致內存碎片與分配開銷大。解決方案：預分配大塊原始內存，維護一個「自由列表」（free list），分配時從列表取對象並構造，釋放時析構後歸還列表，不歸還給系統。

CachedObj 基類設計

模板類 `CachedObj`，T 為派生類類型。提供：
- `operator new(size_t)`：從自由列表取對象，空則批量分配。
- `operator delete(void*, size_t)`：將對象歸還自由列表。
- 靜態成員管理自由列表：`freeStore`（頭指針）、`chunk`（每次擴容塊大小）、`alloc_mem`（allocator）、`add_to_freelist`（鏈接節點）。
- `next` 指針嵌入基類，僅在對象空閒時用於串聯自由列表。

代碼實現

template <typename T> class CachedObj {
public:
    void *operator new(std::size_t);
    void operator delete(void *, std::size_t);
    virtual ~CachedObj() {}
protected:
    T *next;
private:
    static void add_to_freelist(T *);
    static std::allocator<T> alloc_mem;
    static T *freeStore;
    static const std::size_t chunk;
};

template <typename T>
void *CachedObj<T>::operator new(std::size_t sz) {
    if (sz != sizeof(T)) throw std::runtime_error("CacheObj: wrong size object in operator new");
    if (!freeStore) {
        T *array = alloc_mem.allocate(chunk);
        for (size_t i = 0; i != chunk; ++i)
            add_to_freelist(&array[i]);
    }
    T *p = freeStore;
    freeStore = freeStore->CachedObj<T>::next;
    return p;
}

template <typename T>
void CachedObj<T>::operator delete(void *p, std::size_t) {
    if (p != 0) add_to_freelist(static_cast<T*>(p));
}

template <typename T>
void CachedObj<T>::add_to_freelist(T *p) {
    p->CachedObj<T>::next = freeStore;
    freeStore = p;
}

template <typename T> std::allocator<T> CachedObj<T>::alloc_mem;
template <typename T> T *CachedObj<T>::freeStore = 0;
template <typename T> const std::size_t CachedObj<T>::chunk = 24;

使用方式

class Screen : public CachedObj<Screen> { ... };

template <typename T>
class QueueItem : public CachedObj< QueueItem<T> > { ... };

派生類無需修改其他代碼，自動獲得池化分配能力。

工作原理圖解

對象在使用時包含業務數據 + 繼承的 next 指針（無意義）；空閒時 next 串聯自由列表。

關鍵細節

1. 僅適用於非基類類型：自由列表存儲固定大小對象，若作基類會有派生類大小不一問題。
2. 顯式指定基類成員：`p->CachedObj<T>::next` 避免與派生類同名成員衝突。
3. 強制類型轉換：`operator delete` 接收 `void*`，調用 `add_to_freelist` 前需 `static_cast<T*>` 恢復實際類型。
4. allocator 使用：`allocate` 獲取原始內存，不調用構造函數；構造由 `new` 表達式自動觸發。

練習代碼片段

class iStack {
public:
    iStack(int capacity) : stack(capacity), top(0) {}
    iStack() : top(0) {}
private:
    vector<int> stack;
    int top;
};

int main() {
    iStack *ps = new iStack(20);
    const iStack *ps2 = new const iStack(15);
    iStack *ps3 = new iStack[100];
}

總結

CachedObj 封裝了自由列表分配策略，通過繼承複用，極大降低了為每個類單獨實現池化的成本。體現了 C++「零開銷抽象」與模板元編程的威力。