1. Optimizing Memory Allocation

A common strategy is to preallocate memory to be used when new objects are created, constructing each new object in preallocated memory as needed. We need to decouple memory allocation from object construction. The obvious reason to decouple allocation and construction is that constructing objects in preallocated memory is wasteful.

In C++, When we use a new expression, memory is allocated, and an object is constructed in that memory. When we use a delete expression, a destructor is called to destroy the object and the memory used by the object is returned to the system. When we take over memory allocation, we must deal with both these tasks. When we allocate raw memory, we must construct object(s) in that memory. Before freeing that memory, we must ensure that the objects are properly destroyed. C++ provides two ways to allocate and free unconstructed, raw memory:

• The allocator class, which provides type-aware memory allocation. This class supports an abstract interface to allocating memory and subsequently using that memory to hold objects.
• The library operator new and operator delete functions, which allocate and free raw, untyped memory of a requested size.

C++ also provides various ways to construct and destroy objects in raw memory:

• The allocator class defines members named construct and destroy. The construct member initializes objects in unconstructed memory;
  the destroy member runs the appropriate destructor on objects.
• The placement new expression takes a pointer to unconstructed memory and initializes an object or an array in that space.
• We can directly call an object’s destructor to destroy the object. Running the destructor does not free the memory in which the object resides.
• The algorithms uninitialized_fill and uninitialized_copy execute like the fill and copy algorithms except that they construct objects in their destination rather than assigning to them.

// The behavior of copy template is equivalent to:
template<class InputIterator, class OutputIterator>
  OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
  while (first!=last) {
    *result = *first;
    ++result; ++first;
  }
  return result;
}

也就是说copy是赋值行为，uninitialized_copy是在一块raw内存中的初始化行为。赋值行为意味着将释放原来的数据。Assigning to an object in unconstructed memory rather than initializing it is undefined. For many classes, doing so causes a crash at run time. Assignment involves freeing the existing object. If there is no existing object, then the actions in theassignment operator can have disastrous effects.

Modern C++ programs ordinarily ought to use the allocator class to allocate memory. It is safer and more flexible. However, when
constructing objects, the placement new expression is more flexible than the allocator::construct member. There are some cases where placement new must be used. 因为allocator::construct只能使用拷贝构造函数来构造对象。

2. The allocator Class

The allocator class separates allocation and object construction. When an allocator object allocates memory, it allocates space that is appropriately sized and aligned to hold objects of the given type. However, the memory it allocates is unconstructed. Users of allocator must separately construct and destroy objects placed in the memory it allocates.

3. Using allocator to Manage Class Member Data

To understand how we might use a preallocation strategy and the allocator class to manage the internal data needs of a class, let’s think a bit more about how memory allocation in the vector class might work.

// pseudo-implementation of memory allocation strategy for a vector-like class
template <class T> class Vector {
    public:
        Vector(): elements(0), first_free(0), end(0) { }
        void push_back(const T&);
        // ...
    private:
        static std::allocator<T> alloc; // object to get raw memory
        void reallocate();  // get more space and copy existing elements
        T* elements; // pointer to first element in the array
        T* first_free; // pointer to first free element in the array
        T* end; // pointer to one past the end of the array
        // ...
};

template <class T>
void Vector<T>::push_back(const T&t)
{
    if(first_free == end)
        reallocate();
    alloc.construct(first_free, t);
    ++first_free;
}

template <class T>
void Vector<T>::reallocate()
{
    ptrdiff_t size = first_free - elements;
    ptrdiff_t newcapacity = max(size, 1) * 2;
    T *new_elements = alloc.allocate(newcapacity);
    uninitialized_copy(elements, end, new_elements);

    for(T *p = elements; p != end; ++p)
        alloc.destroy(p);

    // deallocate cannot be called on a 0 pointer
    if (elements)
        alloc.deallocate(elements, size);

    elements = new_elements;
    first_free = elements + size;
    end = elements + newcapacity;
}

注意静态成员alloc在实现文件中的定义
template<class T>
allocator<T> Vector<T>::alloc;

Each Vector type defines a static data member of type allocator to allocate and construct the elements in Vectors of the given type. deallocate expects a pointer that points to space that was allocated by allocate. It is not legal to pass deallocate a zero pointer.