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

前言

C++ 標準庫容器透過 Allocator 抽象記憶體管理，預設使用 std::allocator（基於 new/delete）。針對高頻率小塊配置場景，可實作自訂配置器以提升效能。本文基於 SGI STL 二級配置器演算法，實作一個記憶體池配置器 MyAlloc，支援 map, set, multimap, multiset 等節點式容器。

設計架構

• 自由鏈表：依區塊大小分級管理（本例簡化為 2 級）
• 記憶體池：大塊向系統申請，內部切割小區塊
• 圓整對齊：配置大小對齊至 sizeof(Obj)
• Cookie 結構：集中管理池狀態、自由鏈表、使用統計

核心資料結構

// 節點聯合體：自由鏈表指標 / 客戶資料
union _Obj {
    _Obj* M_free_list_link;
    char M_client_data[1];
};
typedef _Obj Obj;

// 記憶體池控制結構
struct _Cookie {
    int iTotalsize;           // 池總大小
    void* pStartall;          // 池起始位址
    char* pStartfree;         // 可用空間起始
    char* pEndfree;           // 可用空間結束
    int iUseNum[NODENUMS];    // 各級使用節點數
    short sFreelistIndex[NODENUMS]; // 各級區塊大小
    Obj* uFreelist[NODENUMS]; // 各級自由鏈表頭
};
typedef _Cookie Cookie;

static Cookie* pHead = NULL;  // 全域池控制塊

配置器類別 MyAlloc

符合 C++ Allocator 概念需求：

template <class T>
class MyAlloc {
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;
    
    // rebind 機制
    template <class U> struct rebind { typedef MyAlloc<U> other; };
    
    // 位址取得
    pointer address(reference x) const { return &x; }
    const_pointer address(const_reference x) const { return &x; }
    
    // 建構/解構
    MyAlloc() throw() { std::cout << "MyAlloc\n"; }
    MyAlloc(const MyAlloc&) throw() { std::cout << "const MyAlloc\n"; }
    template <class U> MyAlloc(const MyAlloc<U>&) throw() { std::cout << "const MyAlloc<U>\n"; }
    ~MyAlloc() throw() { std::cout << "~MyAlloc\n"; }
    
    size_type max_size() const throw() {
        return std::numeric_limits<size_type>::max() / sizeof(T);
    }
    
    // 核心配置/釋放
    pointer allocate(size_type n, const void* = 0);
    void deallocate(pointer p, size_type n);
    
    // 物件建構/銷毀
    void construct(pointer p, const T& val) { new((void*)p) T(val); }
    void destroy(pointer p) { p->~T(); }
};

// 相等比較（標準要求）
template <class T1, class T2>
bool operator==(const MyAlloc<T1>&, const MyAlloc<T2>&) throw() { return true; }

template <class T1, class T2>
bool operator!=(const MyAlloc<T1>&, const MyAlloc<T2>&) throw() { return false; }

關鍵演算法實作

1. 大小圓整與索引對應

static const int ALIGN = sizeof(Obj);

int round_up(int bytes) {
    if (bytes < ALIGN) return ALIGN;
    return bytes;  // 簡化：實際應對齊至 ALIGN 倍數
}

int freelist_index(int bytes) {
    // 查找現有索引
    for (int i = 0; i < NODENUMS; ++i) {
        if (pHead->sFreelistIndex[i] == bytes) return i;
    }
    // 尋找空閒槽位註冊新大小
    for (int i = 0; i < NODENUMS; ++i) {
        if (pHead->sFreelistIndex[i] == 0) {
            pHead->sFreelistIndex[i] = bytes;
            return i;
        }
    }
    return NODENUMS;  // 滿載
}

2. 記憶體池擴充

char* chunk_alloc(int size, int* nobjs) {
    int total_bytes = size * (*nobjs);
    int bytes_left = pHead->pEndfree - pHead->pStartfree;
    
    if (bytes_left >= total_bytes) {
        // 池足夠
        char* result = pHead->pStartfree;
        pHead->pStartfree += total_bytes;
        return result;
    } else if (bytes_left >= size) {
        // 部分滿足
        *nobjs = bytes_left / size;
        total_bytes = size * (*nobjs);
        char* result = pHead->pStartfree;
        pHead->pStartfree += total_bytes;
        return result;
    } else {
        // 池耗盡：實際應嘗試回收其他自由鏈表、或向系統申請
        return NULL;  // 簡化處理
    }
}

3. 重新填充自由鏈表

void* refill(int n, int sz) {
    int nobjs = n;
    char* chunk = chunk_alloc(sz, &nobjs);
    if (!chunk || nobjs == 1) return chunk;
    
    Obj** my_free_list = pHead->uFreelist + freelist_index(sz);
    Obj* result = (Obj*)chunk;
    *my_free_list = (Obj*)(chunk + sz * n);  // 串接剩餘節點
    
    Obj* current = *my_free_list;
    for (int i = 1; ; ++i) {
        Obj* next = (Obj*)((char*)current + sz);
        if (i == nobjs - 1) {
            current->M_free_list_link = 0;
            break;
        }
        current->M_free_list_link = next;
        current = next;
    }
    return result;
}

4. 配置與釋放

pointer allocate(size_type n, const void* = 0) {
    int index = freelist_index(sizeof(T));
    if (index >= NODENUMS) return NULL;
    
    Obj** my_free_list = pHead->uFreelist + index;
    Obj* result = *my_free_list;
    
    if (!result) {
        result = (Obj*)refill(n, round_up(sizeof(T)));
    } else {
        *my_free_list = result->M_free_list_link;
    }
    
    pHead->iUseNum[index] += n;
    return (pointer)result;
}

void deallocate(pointer p, size_type n) {
    int index = freelist_getindex(sizeof(T));
    if (index >= NODENUMS) { /* 錯誤處理 */ }
    
    Obj** my_free_list = pHead->uFreelist + index;
    Obj* q = (Obj*)p;
    
    // 簡化：單節點歸還（向量容器需特殊處理）
    q->M_free_list_link = *my_free_list;
    *my_free_list = q;
    
    pHead->iUseNum[index] -= n;
}

初始化與除錯支援

void InitShm() {
    int size = 1000;
    pHead = (Cookie*)malloc(sizeof(Cookie) + size);
    pHead->iTotalsize = sizeof(Cookie) + size;
    pHead->pStartall = pHead;
    pHead->pStartfree = (char*)pHead + sizeof(Cookie);
    pHead->pEndfree = (char*)pHead + pHead->iTotalsize;
    for (int i = 0; i < NODENUMS; ++i) {
        pHead->sFreelistIndex[i] = 0;
        pHead->uFreelist[i] = 0;
        pHead->iUseNum[i] = 0;
    }
}

void PrintFreelistAndCookie() {
    std::cout << "Cookie info:\n";
    std::cout << "Totalsize=" << pHead->iTotalsize 
              << " Used=" << (pHead->pStartfree - (char*)pHead)
              << " Free=" << (pHead->pEndfree - pHead->pStartfree) << "\n";
    for (int i = 0; i < NODENUMS; ++i) {
        int cnt = 0;
        Obj* cur = pHead->uFreelist[i];
        while (cur) { ++cnt; cur = cur->M_free_list_link; }
        std::cout << "Level " << i << ": size=" << pHead->sFreelistIndex[i]
                  << " used=" << pHead->iUseNum[i] << " free_nodes=" << cnt << "\n";
    }
}

測試程式

#include <map>
#include <string>
#include <iostream>
#include "MyAlloc.h"

using namespace std;
using namespace happyever;

int main() {
    InitShm();
    
    // 使用自訂配置器的 multimap
    multimap<string, int, less<string>, MyAlloc<string> > m;
    m.insert(make_pair(string("Harry"), 32));
    m.insert(make_pair(string("Mary"), 59));
    m.insert(make_pair(string("Roger"), 18));
    m.insert(make_pair(string("Nancy"), 37));
    m.insert(make_pair(string("Mary"), 23));  // 重複鍵
    
    for (auto p = m.begin(); p != m.end(); ++p) {
        cout << p->first << "," << p->second << endl;
    }
    
    // 測試刪除
    auto it = m.find("Harry");
    if (it != m.end()) m.erase(it);
    
    for (auto p = m.begin(); p != m.end(); ++p) {
        cout << p->first << "," << p->second << endl;
    }
    return 0;
}

已知限制與改進方向

擴充：共享記憶體與進程間通訊

將 InitShm 改為 shmget/shmat，Cookie 加入 iShmKey, iSemKey，配置/釋放關鍵區段用 POSIX 信號量保護，即可實現跨進程的 STL 容器共享。作者已在 AIX/xlC 環境完成生產級實作，核心邏輯與本文一致。

總結

自訂配置器能針對特定容器使用模式優化記憶體管理。本文實作展示了自由鏈表、記憶體池、圓整對齊、rebind 機制等核心概念。雖有限制，但為理解 STL 記憶體模型、開發高效能/嵌入式/共享記憶體應用提供了紮實基礎。

1. 上一篇文章： Windows Workflow Foundation 權限控制實作：以 WebWorkflowRole 為例
2. 下一篇文章： C 與 C++ 標準輸入處理差異深度解析：緩衝區與換行符陷阱

關於C++

純 C++ 手寫圖像處理軟件 MagicHouse：無外部依賴實現幾何變換、濾鏡、加密、小波等算法

一、專案簡介 MagicHouse 是一款純 C++ 編寫的

C/C++ 學院 0907 —— 象棋五子棋編譯錯誤排查與經典查找排序算法實現集錦

本文記錄 MFC 專案編譯常見錯誤（MBCS/Unicode

Codeforces 305B Mike and Feet：單調棧求各長度區間最小值的最大值

題目大意 n (≤2×10⁵) 隻熊站成一排，高度 a[i]

C++ 三種繼承方式深度解析：公有、私有、保護繼承

核心規則總結 繼承方式基類 public基類 protec