1. A Memory-Allocator Base Class

One common strategy is to preallocate a block of raw memory to hold unconstructed objects. When new elements are created, they could be constructed in one of these preallocated objects. When elements are freed, we’d put them back in the block of preallocated objects rather than actually returning memory to the system. This kind of strategy is often known as maintaining a freelist . The freelist might be implemented as a linked list of objects that have been allocated but not constructed. We’ll define a new class that we’ll name CachedObj to handle the freelist.

The CachedObj class will have a simple interface: Its only job is to allocate and manage a freelist of allocated but unconstructed objects. This class will define a member operator new that will return the next element from the freelist, removing it from the freelist. The operator new will allocate new raw memory whenever the freelist becomes empty. The class will also define operator delete to put an element back on the freelist when an object is destroyed. Classes that wish to use a freelist allocation strategy for their own types will inherit from CachedObj.

As we’ll see, CachedObj may be used only for types that are not involved in an inheritance hierarchy. Unlike the member new and
delete operations, CachedObj has no way to allocate different sized objects depending on the actual type of the object: Its freelist holds objects of a single size. Hence, it may be used only for classes, such as QueueItem , that do not serve as base classes. The data members defined by the CachedObj class, and inherited by its derived classes, are:

• A static pointer to the head of the freelist
• A member named next that points from one CachedObj to the next

The next pointer chains the elements together onto the freelist. Each type that we derive from CachedObj will contain its own type-specific data plus a single pointer inherited from the CachedObj base class. When the object is in use, this pointer is meaningless and not used. When the object is available for use and is on the freelist, then the next pointer is used to point to the next available object.

The only remaining question is what types to use for the pointers in CachedObj. We’d like to use the freelist approach for any type, so the class will be a template. The pointers will point to an object of the template type:

template <class T>
class CachedObj
{
    public:
        CachedObj() : next(NULL) {}
        void * operator new(size_t);
        void operator delete(void *, size_t);
        virtual ~CachedObj() {}

    private:
        static void add_to_freelist(T*);
        static allocator<T> alloc_mem;
        static T *freeStore;
        static const size_t chunk;
        T *next;
};

The static members manage the freelist. These members are declared as static because there is only one freelist maintained for all the objects of a given type. The freeStore pointer points to the head of the freelist. The member named chunk specifies the number of objects that will be allocated each time the freelist is empty.

template <class T>
void * CachedObj<T>::operator new(size_t sz)
{
    // new should only be asked to build a T, not an object
    // derived from T; check that right size is requested

    if(sz != sizeof(T))
        throw runtime_error("CachedObj: wrong size object in operator new");

    if(NULL == freeStore)
    {
        T *array = alloc_mem.allocate(chunk);

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

    T *p = freeStore;
    freeStore = freeStore->CachedObj<T>::next;
    return p; // constructor of T will construct the T part of the object
}

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

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

The only tricky part is the use of the next member. Recall that CachedObj is intended to be used as a base class. The objects that are allocated aren’t of type CachedObj . Instead, those objects are of a type derived from CachedObj . The type of T , therefore, will be the derived type. The pointer p is a pointer to T , not a pointer to CachedObj . If the derived class has its own member named next , then writing p->next would fetch the next member of the derived class! But we want to set the next in the base, CachedObj class.

What remains is to define the static data members:

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

Here is how we use CachedObj:

class Screen: public CachedObj<Screen> {
    // interface and implementation members of class Screen are unchanged
};
template <class Type>
class QueueItem: public CachedObj< QueueItem<Type> > {
    // remainder of class declaration and all member definitions unchanged
};

2. 练习题

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

(a) iStack *ps = new iStack(20);        // ok
(b) iStack *ps2 = new const iStack(15); // error
(c) iStack *ps3 = new iStack[ 100 ];    // error

注意iStack中类类型的数据成员stack的初始化方式。b错误是因为返回的是const iStack *类型的指针。c错误是因为使用new表达式动态分配数组时，如果数组元素具有类类型，则使用该类的默认构造函数初始化，但是iStack没有。