本文共 7417 字，大约阅读时间需要 24 分钟。

1.vector的数据结构

template 
   
      class vector {...protected:  iterator start;                    //表示目前已使用空间的头  iterator finish;				   //表示目前已使用空间的尾iterator end_of_storage;         //表示目前可用空间的尾（已分配）...public:  iterator begin() { return start; }  const_iterator begin() const { return start; }  iterator end() { return finish; }  const_iterator end() const { return finish; }  reverse_iterator rbegin() { return reverse_iterator(end()); }  const_reverse_iterator rbegin() const {     return const_reverse_iterator(end());   }  reverse_iterator rend() { return reverse_iterator(begin()); }  const_reverse_iterator rend() const {     return const_reverse_iterator(begin()); }//求取已使用容量  size_type size() const { return size_type(end() - begin()); }  size_type max_size() const { return size_type(-1) / sizeof(T); }  //求取目前可使用空间容量  size_type capacity() const { return size_type(end_of_storage - begin()); }  bool empty() const { return begin() == end(); }...}
   

2.vector的构造与内存管理

2.1初始化

容器的构造函数

1、C<T> c;   创建空容器

2、C c(c2);      创建c2的一个副本，C和c2必须有相同的容器类型及元素类型

3、C c(b,e);   创建c，其元素是迭代器b，e范围之间元素的副本。

       对于这一条，使用迭代器的时候，不要求容器类型相同。容器内的元素类型也可以不同，只要他们相互兼容，能够将要复制的元素转化为所构建的新容器的元素类型，即可以实现复制。

4、C c(n,t);   用n个值为t的元素创建容器c。（仅适用于顺序容器）。参数的顺序和语言相适应，n个t。

5、C c(n);    创建含n个默认值的容器c。（仅适用于顺序容器）。

       vector是顺序容器，所以上述5种构造函数都可以使用。

template 
   
      class vector {...protected://vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位//专属空间配置器，每次配置一个元素大小  typedef simple_alloc
    
      data_allocator;...  vector() : start(0), finish(0), end_of_storage(0) {}  vector(size_type n, const T& value) { fill_initialize(n, value); }  vector(int n, const T& value) { fill_initialize(n, value); }  vector(long n, const T& value) { fill_initialize(n, value); }  explicit vector(size_type n) { fill_initialize(n, T()); }...void fill_initialize(size_type n, const T& value) {    start = allocate_and_fill(n, value);  //配置空间并设初值    finish = start + n;					// 调整范围    end_of_storage = finish; 			// 调整范围  }iterator allocate_and_fill(size_type n, const T& x) {    iterator result = data_allocator::allocate(n); //配置n个元素空间    __STL_TRY {      // 全局函数，将result所指的未初始化空间设定为n个初值为x的变量      // 定义于 
     
      。      uninitialized_fill_n(result, n, x);  //全局函数      return result;    }
     
    
   

！！！uninitialized_fill_n()会根据第一参数的型别特性（type traits）决定使用算法fill_n()或反复调用construct()来完成任务。！！！

2.2 push_back()操作时vector内部的过程

    push_back()操作将新元素插入容器尾部，该函数首先检查是否还有备用空间（finish！=end_of_storage），如果有那么就直接在备用空间上构造元素，并调整迭代器finish。如果没有备用空间了（finish= end_of_storage），就扩充空间（重新配置，移动数据，释放原空间）。

void push_back(const T& x) {    if (finish != end_of_storage) {  // 还有备用空间      construct(finish, x);   		// 直接在备用空间中构建元素      ++finish;                          	// 调整范围    }    else                                  // 已无备用空间      insert_aux(end(), x);			  }template 
   
    void vector
    
     ::insert_aux(iterator position, const T& x) {  if (finish != end_of_storage) {  // 还有备用空间    // 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值      construct(finish, *(finish - 1));    ++finish;    // 以下做啥用？    T x_copy = x;    copy_backward(position, finish - 2, finish - 1);    *position = x_copy;  }  else {		// 已無備用空間    const size_type old_size = size();//此时的size（）等同于capacity（）    const size_type len = old_size != 0 ? 2 * old_size : 1;    // 以上配置原则：如果原大小为0，那么则配置1（个元素大小）    // 如果原大小不为0，那么配置原大小的2倍    // 前半段用来放置原数据，后半段用来放置新数据    iterator new_start = data_allocator::allocate(len); // 实际配置    iterator new_finish = new_start;    __STL_TRY {      // 复制      new_finish = uninitialized_copy(start, position, new_start);      construct(new_finish, x);      ++new_finish;      // 将安插点的原内容页拷贝过来（该函数也可能被insert（p,x）调用）      new_finish = uninitialized_copy(position, finish, new_finish);    }    catch(...) {      // "commit or rollback"（如果不成功那么一个都不留）      destroy(new_start, new_finish);       data_allocator::deallocate(new_start, len);      throw;    }    // 解构并释放原vector    destroy(begin(), end());    deallocate();    // 调整迭代器，指向新vector    start = new_start;    finish = new_finish;    end_of_storage = new_start + len;  }}
    
   

        所谓的vector的大小的动态增长，并不是在原空间之后连续新空间（因为无法保证原空间之后尚有可供配置的空间）。而是以原来大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作一旦引起重新配置，指向原vector的所有迭代器就都失效了。这就是为什么《C++ Primer》中说push_back和inser可能会使迭代器失效的原因。其本质是：空间已进行重新配置。

转载地址：http://ykafb.baihongyu.com/