vector容器的动态分配空间

vector容器的底层实现基于数组，里面封装了大量高效的方法，可以完美取代掉数组。整个容器的核心实际上就是动态分配内存，也是其性能优于数组的重要原因。下面重点解析它的核心函数push_back函数：

当数组中增加一个元素x的时候，先判断是否还有备用空间；如果还有备用空间，则将当前指针的值设为x，并将当前的指针加1；若备用空间已经用完，如果之前的空间为0，则重新分配大小为1的空间，否则将空间扩容为之前的两倍，然后将旧容器中的值重新拷贝到新空间中，并重新分配起始指针和当前指针。所以使用vector需要注意的一点就是尽量不要动态给它分配空间。而且空间重新分配之后，之前的所有指针都会失效（特别要注意）。

具体实现：

void push_back(const T& x) {
    if (finish != end_of_storage) { //若当前还有备用空间
      construct(finish, x); //将当前水位的值设为x
      ++finish; //提升水位
    }
    else
      insert_aux(end(), x); 
}
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  if (finish != end_of_storage) {
    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(); //获取之前数组的大小
    const size_type len = old_size != 0 ? 2 * old_size : 1; //将当前数组的容量扩大为原来的两倍
    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); //将当前数组的水位的值设为x
      ++new_finish; //提升新数组的水位
      new_finish = uninitialized_copy(position, finish, new_finish); //这语句感觉可有可无，因为它根本就不会执行，position即last，而finish也是last
    }

#       ifdef  __STL_USE_EXCEPTIONS 
    catch(...) { //如果重新构造的新数组出现异常，则销毁当前新创建的数组，并释放内存空间
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif /* __STL_USE_EXCEPTIONS */
    destroy(begin(), end()); //将旧数组的空间释放掉
    deallocate();
    start = new_start; //new_start记录新数组的起始位置
    finish = new_finish; //重新设置当前水位的指针
    end_of_storage = new_start + len; //设置新数组的容量
  }
}

[1]《STL源码分析》----侯捷

[2]《STL3.0源码》