C++ STL Allocator 空間配置器深度解析：從標準介面到 SGI 兩級分配策略

Allocator 存在的意義

STL 容器與演算法分離，記憶體管理同樣抽象為 Allocator。將配置策略獨立，容器得以專注資料結構邏輯，同時支援：

• 一般堆積配置（malloc/free）
• 記憶體池、物件池減少碎片
• 共享記憶體、記憶體映射檔、甚至磁碟儲存等特殊來源
• 除錯用配置器（記錄配置/釋放、偵測洩漏、邊界檢查）

標準 Allocator 介面規範（C++98/03）

型別定義群

template <class T> class allocator {
public:
    typedef T           value_type;
    typedef T*          pointer;
    typedef const T*    const_pointer;
    typedef T&          reference;
    typedef const T&    const_reference;
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;

    template <class U> struct rebind { typedef allocator<U> other; };
    // ...

rebind 讓容器從 allocator<T> 取得 allocator<Node>，實現節點配置。

核心配置/釋放操作

物件建構/銷毀

void construct(pointer p, const T& val) { ::new((void*)p) T(val); }
void destroy(pointer p) { p->~T(); }

分離「原始記憶體取得」與「物件初始化」，支援 vector::reserve() 僅配置不建構。

SGI STL 兩級配置器實現細節

設計動機

頻繁小區塊 new/delete 導致：

1. 記憶體碎片：堆積管理元資料開銷大於有效載荷
2. 效能瓶頸：全域堆積鎖競爭、系統呼叫開銷

第一級配置器（> 128 bytes）

• 直接呼叫 malloc()/free()
• 配置失敗觸發 _malloc_alloc_oom_handler 嘗試釋放備用記憶體

第二級配置器（≤ 128 bytes）

核心資料結構：

• 16 個 free-list，索引 0~15 對應 8~128 bytes（8 bytes 對齊）
• 記憶體池：向系統申請大塊記憶體，內部切割

配置流程：

1. 依大小計算 free-list 索引 index = (bytes + 7) / 8 - 1
2. 對應 free-list 非空 → 取出區塊、調整指標、回傳
3. free-list 空 → refill() 向記憶體池取 20 區塊（可配置）
4. 記憶體池不足 → chunk_alloc() 向系統 malloc() 申請大塊
5. 系統也無記憶體 → 嘗試從較大 free-list 拆分、或呼叫 OOM handler

釋放流程：

1. 依大小找 free-list 索引
2. 區塊插入 free-list 頭部（LIFO，利用 CPU 快取局部性）
3. 不歸還給系統，供下次複用

與 Linux Slab Allocator 異同

自訂 Allocator 實戰範例：記憶體池

template <class T, size_t PoolSize = 4096>
class PoolAllocator {
    alignas(T) char pool_[PoolSize];
    T* free_list_ = nullptr;
    size_t used_ = 0;

public:
    using value_type = T;
    PoolAllocator() noexcept = default;
    template <class U> PoolAllocator(const PoolAllocator<U>&) noexcept {}

    T* allocate(size_t n) {
        if (n != 1) throw std::bad_alloc();
        if (free_list_) {
            T* p = free_list_;
            free_list_ = *reinterpret_cast<T**>(free_list_);
            return p;
        }
        if (used_ + sizeof(T) <= PoolSize) {
            return reinterpret_cast<T*>(pool_ + used_ += sizeof(T));
        }
        throw std::bad_alloc();
    }
    void deallocate(T* p, size_t) noexcept {
        *reinterpret_cast<T**>(p) = free_list_;
        free_list_ = p;
    }
};

現代 C++ 發展：C++11 std::allocator_traits 與 C++17 std::pmr

• allocator_traits 統一介面、提供預設實作，容器不再直接依賴 Allocator 成員
• std::pmr::polymorphic_allocator + memory_resource 實現執行期多態配置策略，取代靜態模板參數
• 標準化 new (std::align_val_t)、std::allocator::allocate(size_t, size_t alignment) 支援對齊需求

總結

Allocator 是 STL 「政策基底類別」設計哲學的典範：將變動點（配置策略）參數化，讓容器在零開銷抽象下獲得極大靈活性。理解兩級配置器原理，不僅能優化高頻小物件場景，更能洞悉現代記憶體管理的核心權衡——碎片 vs 開銷、延遲 vs 吞吐、通用 vs 專用。