C++ Primer 學習筆記_100_特殊工具與技術 --優化內存分配[續2]

特殊工具與技術

--優化內存分配[續2]

七.一個內存分配器基類

預先分配一塊原始內存來保存未構造的對象，創建新元素的時候，可以在一個預先分配的對象中構造；釋放元素的時候，將它們放回預先分配對象的塊中，而不是將內存實際返還給系統。這種策略常被稱為維持一個自由列表。可以將自由列表實現為已分配但未構造的對象的鏈表。

我們將定義一個名為 CachedObj 的新類來處理自由列表。像 QueueItem 這樣希望優化其對象分配的類可以使用 CachedObj 類，而不用直接實現自己的 new 和 delete 成員。

CachedObj 類有簡單的接口：它的工作只是分配和管理已分配但未構造對象的自由列表。這個類將定義一個成員 operator new，返回自由列表的下一個元素，並將該元素從自由列表中刪除。當自由列表為空的時候，operator new 將分配新的原始內存。這個類還定義 operator delete，在撤銷對象時將元素放回自由列表.

希望為自己的類型使用自由列表分配策略的類將繼承 CachedObj 類，通過繼承，這些類可以使用 CachedObj 類的 operator new 和 operator delete 定義，以及表示自由列表所需的數據成員。因為打算將 CachedObj 類作為基類，所以將給它一個 public 虛析構函數。

正如我們將看到的，CachedObj 只能用於不包含在繼承層次中類型。與成員 new 和 delete 操作不同，CachedObj 類沒有辦法根據對象的實際類型分配不同大小的對象：它的自由列表保存單一大小的對象。因此，它只能用於不作基類使用的類，如 QueueItem 類。

由 CachedObj 類定義並被它的派生類繼承的數據成員是：

? 指向自由列表表頭的 static 指針。

? 名為 next、 從一個 CachedObj 對象指向另一個 CachedObj 對象的指針。

next 指針將元素鏈入自由列表。從 CachedObj 類派生的每個類型都包含自己的類型特定的數據，加上一個從 CachedObj 基類繼承的指針。每個對象具有由內存分配器使用但被繼承類型自己不用的一個額外指針，對象在使用的時候，該指針無意義且不使用；對象可供使用並在自由列表中的時候，就使用 next 指針來指向下一個可用的對象。

如果使用 CachedObj 類來優化 Screen 類的分配，Screen 類型的對象（概念上）看起來如圖所示:

1.CachedObj類

template 
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 alloc_mem;
    static T *freeStore;
    static const std::size_t chunk;
};

[說明]

new 和 delete 成員分別從自由列表取走對象和將對象返回到自由列表。

static 成員管理自由列表。這些成員聲明為 static，是因為只為所有給定類型的對象維持一個自由列表。freeStore 指針指向自由列表的表頭。名為chunk 的成員指定每當自由列表為空時將分配的對象的數目。最後,add_to_freelist 函數將對象放在自由列表，operator new 使用這個函數將新分配的對象放到自由列表，刪除對象的時候，operator delete 也使用該函數將對象放回自由列表。

2.使用CachedObj

當繼承 CachedObj 類的時候，用來實例化 CachedObj 類的模板類型將是派生類型本身。

為了優化 Screen 類的內存管理，我們將 Screen 聲明為：

class Screen : public CachedObj
{
    //...
};
因為QueueItem是一個模板類型,從CachedObj派生它有些復雜:
template 
class QueueItem : public CachedObj< QueueItem >
{
    //...
};

我們的類不需要其他改變。現在 QueueItem 類具有自動內存分配，這個內存分配使用自由列表減少創建新的 Queue 元素時需要的分配數目。

3.分配怎樣工作

因為我們從 CachedObj 類派生 QueueItem 類，任何使用 new 表達式的分配，如 Queue::push: 中的調用：

QueueItem *pt = new QueueItem(val); 

分配並構造一個新的 QueueItem 對象。每個表達式

1)使用 QueueItem::operator new 函數從自由列表分配一個對象。

2)為類型 T 使用元素類型的復制構造函數，在該內存中構造一個對象。

類似地，當像 delete pt這樣刪除一個 QueueItem 指針的時候，運行 QueueItem 析構函數清除指向的對象，並調用該類的 operator delete，將元素所用的內存放回自由列表。

4.定義operater new

operater new 成員從自由列表返回一個對象,如果自由列表為空,new必須首先分配chunk數目的內存:

template 
void *CachedObj::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.allocator(chunk);

        for (size_t i = 0; i != chunk; ++i)
        {
            add_to_freelist(&array[i]);
        }
    }

    T *p = freeStore;
    freeStore = freeStore -> CachedObj::next;
    return p;
}

operator new 函數檢查自由列表中是否有對象，如果沒有，它就請求allocator 成員分配 chunk 個新的未構造對象，然後，它通過新分配的對象進行迭代，設置 next 指針。調用了 add_to_freelist 函數之後，自由列表上的每個對象除了將保存下一個可用對象的地址 next 指針之外，將是未構造的。自由列表如圖所示:

在有可用對象可以分配的保證之下，operator new 返回自由列表上第一個對象的地址，將 freeStore 指針重置為指向自由列表上下一個元素。被返回的對象是未構造的。因為從 new 表達式調用 Z喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcGVyYXRvciBuZXejrMv50tQgbmV3ILHttO/Kvb2ruLrU8Lm51Oy21M/zoaM8L3A+PHA+IDwvcD48cD41Lrao0uVvcGVyYXRlciBkZWxldGU8L3A+PHA+CW9wZXJhdG9yIGRlbGV0ZSCzydSx1ru4utTwudzA7cTatOajrCDU2s72ubm6r8r91tDS0b6tx+Wz/cHLttTP87G+ye2jrGRlbGV0ZSCx7bTvyr3U2rX308Mgb3BlcmF0b3IgZGVsZXRlINaux7C199PDzva5ubqvyv2ho29wZXJhdG9yIGRlbGV0ZSCzydSxuty88rWlo7o8L3A+PHByZSBjbGFzcz0="brush:java;">template void CachedObj::operator delete(void *p,std::size_t) { if (p != 0) add_to_freelist(static_cast(p)); }

它調用 add_to_freelist 成員將被刪除對象放回自由列表。

令人感興趣的部分是強制類型轉換。在刪除動態分配的類類型對象時調用 operator delete，編譯器將該對象的地址傳給 operator delete。但是，指針的形參類型必須是 void*，在調用 add_to_freelist 之前，必須將指針從 void* 強制轉換為它的實際類型，本例中，那個類型是指向 T 的指針，它是 CachedObj 派生類型的對象的指針。

6.add_to_freelist成員

這個成員的任務是設置next指針,並且在將對象加到自由列表時更新freeStore指針:

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

為了避免任何與派生類中定義的成員可能的沖突，顯式指定我們正在給基類成員 next 賦值。

7.定義靜態數據成員

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

照常，對於類模板的靜態成員，每個類型使用不同的靜態成員來實例化 CachedObj 類。將 chunk 初始化為任意值，本例中為 24。將 freeStore 指針初始化為 0，指出自由列表開始時為空。alloc_mem 成員不需要初始化，但必須記得定義它。

//P646 習題18.10 源代碼修改之後
class iStack
{
public:
    iStack(int capacity):stack(capacity),top(0) {}
    iStack():top(0) {}

private:
    vector stack;
    int top;
};

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