特殊工具与技术

--优化内存分配[续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 <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;
};

[说明]

new 和 delete 成员分别从自由列表取走对象和将对象返回到自由列表。 

static 成员管理自由列表。这些成员声明为 static，是因为只为所有给定类型的对象维持一个自由列表。freeStore 指针指向自由列表的表头。名为chunk 的成员指定每当自由列表为空时将分配的对象的数目。最后,add_to_freelist 函数将对象放在自由列表，operator new 使用这个函数将新分配的对象放到自由列表，删除对象的时候，operator delete 也使用该函数将对象放回自由列表。

2.使用CachedObj

当继承 CachedObj 类的时候，用来实例化 CachedObj 类的模板类型将是派生类型本身。

为了优化 Screen 类的内存管理，我们将 Screen 声明为：

class Screen : public CachedObj<Screen>
{
    //...
};
因为QueueItem是一个模板类型,从CachedObj派生它有些复杂:
template <typename T>
class QueueItem : public CachedObj< QueueItem<T> >
{
    //...
};

我们的类不需要其他改变。现在 QueueItem 类具有自动内存分配，这个内存分配使用自由列表减少创建新的 Queue 元素时需要的分配数目。

3.分配怎样工作

因为我们从 CachedObj 类派生 QueueItem 类，任何使用 new 表达式的分配，如 Queue::push: 中的调用： 

QueueItem<Type> *pt = new QueueItem<Type>(val); 

分配并构造一个新的 QueueItem 对象。每个表达式 

1)使用 QueueItem<T>::operator new 函数从自由列表分配一个对象。 

2)为类型 T 使用元素类型的复制构造函数，在该内存中构造一个对象。 

类似地，当像 delete pt这样删除一个 QueueItem 指针的时候，运行 QueueItem 析构函数清除指向的对象，并调用该类的 operator delete，将元素所用的内存放回自由列表。

4.定义operater new

operater new 成员从自由列表返回一个对象,如果自由列表为空,new必须首先分配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.allocator(chunk);

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

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

operator new 函数检查自由列表中是否有对象，如果没有，它就请求allocator 成员分配 chunk 个新的未构造对象，然后，它通过新分配的对象进行迭代，设置 next 指针。调用了 add_to_freelist 函数之后，自由列表上的每个对象除了将保存下一个可用对象的地址 next 指针之外，将是未构造的。自由列表如图所示:

在有可用对象可以分配的保证之下，operator new 返回自由列表上第一个对象的地址，将 freeStore 指针重置为指向自由列表上下一个元素。被返回的对象是未构造的。因为从 new 表达式调用 operator new，所以 new 表达式将负责构造对象。

5.定义operater delete

operator delete 成员只负责管理内存， 在析构函数中已经清除了对象本身，delete 表达式在调用 operator delete 之前调用析构函数。operator delete 成员很简单：

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

它调用 add_to_freelist 成员将被删除对象放回自由列表。

令人感兴趣的部分是强制类型转换。在删除动态分配的类类型对象时调用 operator delete，编译器将该对象的地址传给 operator delete。但是，指针的形参类型必须是 void*，在调用 add_to_freelist 之前，必须将指针从 void* 强制转换为它的实际类型，本例中，那个类型是指向 T 的指针，它是 CachedObj 派生类型的对象的指针。 

6.add_to_freelist成员

这个成员的任务是设置next指针,并且在将对象加到自由列表时更新freeStore指针:

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

为了避免任何与派生类中定义的成员可能的冲突，显式指定我们正在给基类成员 next 赋值。

7.定义静态数据成员

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; 

照常，对于类模板的静态成员，每个类型使用不同的静态成员来实例化 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<int> stack;
    int top;
};

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