?Vector的capacity(在必须重新分配Vector之前,可以定义的元素的总数)等于end- elements。

?自由空间(在需要重新分配之前,可以增加的元素的数目)是end? first_free。

２、使用construct

push_back成员使用这些指针将新元素加到Vector末尾：

template 
  
   
void Vector
   
    ::push_back(const T &item) { if (first_free == end) { reallocate(); //分配新空间并复制现存元素，将指针重置为指向新分配的空间 } alloc.construct(first_free,item); ++ first_free; } 
   
  

一旦push_back函数知道还有空间容纳新元素,它就请求allocator对象构造一个新的最后元素。construct函数使用类型T的复制构造函数将item值复制到由first_free指出的元素，然后,将first_free加 1以指出又有一个元素在用。

３、重新分配元素与复制元素

template 
  
   
void Vector
   
    ::reallocate() { std::ptrdiff_t size = first_free - elements; std::ptrdiff_t newcapacity = 2 * max(static_cast
    
     (size),1); T *newelements = alloc.allocate(newcapacity); uninitialized_copy(elements,first_free,newelements); for (T *p = first_free; p != elements; ) { alloc.destroy(--p); } if (elements) { alloc.deallocate(elements,end - elements); } elements = newelements; first_free = newelements + size; end = elements + newcapacity; } 
    
   
  

我们使用一个简单但效果惊人的策略:每次重新分配时分配两倍内存。函数首先计算当前在用的元素数目,将该数目翻倍,并请求allocator对象来获得所需数量的空间。如果Vector为空,就分配两个元素。

uninitialized_copy调用使用标准copy算法的特殊版本。这个版本希望目的地是原始的未构造内存,它在目的地复制构造每个元素,而不是将输入范围的元素赋值给目的地,使用T的复制构造函数从输入范围将每个元素复制到目的地。

for循环对旧数组中每个对象调用allocator的 destroy成员它按逆序撤销元素,从数组中最后一个元素开始,以第一个元素结束。destroy函数运行　T类型的析构函数来释放旧元素所用的任何资源。

一旦复制和撤销了元素,就释放原来数组所用的空间。在调用deallocate　之前,必须检查elements是否实际指向一个数组。

【注解】

deallocate期待指向由allocate分配的空间的指针,传给　deallocate一个零指针是不合法的。

最后,必须重置指针以指向新分配并初始化的数组。将first_free和 end　指针分别置为指向最后构造的元素之后的单元以及所分配空间末尾的下一单元。

//P636 习题18.1/2
//in Vector.h
#ifndef VECTOR_H_INCLUDED
#define VECTOR_H_INCLUDED

#include 
  
   
#include 
   
     template 
    
      class Vector { public: typedef T* iterator; public: Vector():elements(0),first_free(0),end(0) {} void push_back(const T &); void reserve(const size_t ); void resize(const size_t ); void resize(const size_t ,const T &); T &operator[](const size_t); const T &operator[](const size_t) const; size_t size() { return first_free - elements; } size_t capacity() { return end - elements; } iterator begin() { return elements; } iterator last() { return first_free; } private: static std::allocator
     
       alloc; void reallocate(); T *elements; T *first_free; T *end; }; template 
      
        std::allocator
       
         Vector
        
         ::alloc; template 
         
           void Vector
          
           ::reallocate() { std::ptrdiff_t size = first_free - elements; std::ptrdiff_t newcapacity = 2 * std::max(static_cast
           
            (size),1); T *newelements = alloc.allocate(newcapacity); std::uninitialized_copy(elements,first_free,newelements); for (T *p = first_free; p != elements; ) { alloc.destroy(--p); } if (elements) { alloc.deallocate(elements,end - elements); } elements = newelements; first_free = newelements + size; end = elements + newcapacity; } #endif // VECTOR_H_INCLUDED