【STL源码分析】vector

vector 的成员变量

// vector的成员变量
// vector底层是可动态扩容的数组，所以
protected:
  _Tp* _M_start;  //数组首地址
  _Tp* _M_finish;  // 数组下一个可用位置
  _Tp* _M_end_of_storage; // 数组的末尾

push_back()

  void push_back(const _Tp& __x) {
  	//判断数组是否还有备用位置，如果有，直接添加
    if (_M_finish != _M_end_of_storage) {
      construct(_M_finish, __x);
      ++_M_finish;
    }
    //否则动态扩容后再添加
    else
      _M_insert_aux(end(), __x);
  }

_M_insert_aux

vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
 //如果又备用空间，则
  if (_M_finish != _M_end_of_storage) {
  	//将_M_finish位置的值置为最后一个元素的值
    construct(_M_finish, *(_M_finish - 1));
    ++_M_finish;
    _Tp __x_copy = __x;
	//将插入点之后的元素循环后移一位
    copy_backward(__position, _M_finish - 2, _M_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 = _M_allocate(__len);
    iterator __new_finish = __new_start;
    __STL_TRY {
		//将原来的vector中start 到指定位置__position中的数据copy到新的vector
      __new_finish = uninitialized_copy(_M_start, __position, __new_start);
		//添加新的元素
      construct(__new_finish, __x);
		//指针后移
      ++__new_finish;
	  //将原来vector 剩余的位置的元素copy到新的vector中
      __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
    }
    __STL_UNWIND((destroy(__new_start,__new_finish), 
                  _M_deallocate(__new_start,__len)));
    destroy(begin(), end());
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);
	//扩容之后跟新迭代器的位置
    _M_start = __new_start;
    _M_finish = __new_finish;
    _M_end_of_storage = __new_start + __len;
  }
}

insert

//插入—个连续的数组，以__first开始，到__last的位置
template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::insert(iterator __position, 
                            const_iterator __first, 
                            const_iterator __last)
{
	//如果当前vector中的元素个数不为0
  if (__first != __last) {
    size_type __n = 0;
    distance(__first, __last, __n);
  	//如果备用空间的大小足够插入一个连续的数组
    if (size_type(_M_end_of_storage - _M_finish) >= __n) {
		//计算插入点之后后移的元素的个数
      const size_type __elems_after = _M_finish - __position;
      iterator __old_finish = _M_finish;
		//如果后移的元素个数大于插入的元素的个数
      if (__elems_after > __n) {
	  	//从_M_finish - __n位置开始到_M_finish结束，逐一复制到_M_finish开始的位置
        uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
        _M_finish += __n;
	  	//将__position开始后移 __个位置
        copy_backward(__position, __old_finish - __n, __old_finish);
		//将元素插入到vector中
        copy(__first, __last, __position);
      }
      else {
        uninitialized_copy(__first + __elems_after, __last, _M_finish);
        _M_finish += __n - __elems_after;
        uninitialized_copy(__position, __old_finish, _M_finish);
        _M_finish += __elems_after;
        copy(__first, __first + __elems_after, __position);
      }
    }
	//备用位置不足以插入一个连续的数组
    else {
      const size_type __old_size = size();
	  //甲酸扩容后的大小，原数组的二倍 和 原数组加上插入数组的个数，取二者中的较大值
      const size_type __len = __old_size + max(__old_size, __n);
      iterator __new_start = _M_allocate(__len);
      iterator __new_finish = __new_start;
      __STL_TRY {
	  	//将_M_start到__position中的元素拷贝到新的vector
        __new_finish = uninitialized_copy(_M_start, __position, __new_start);
		//将__first到__last中的元素拷贝到新的数组
        __new_finish = uninitialized_copy(__first, __last, __new_finish);
		//将原数组中的__position到_M_finish中的元素拷贝到新数组中
        __new_finish
          = uninitialized_copy(__position, _M_finish, __new_finish);
      }
      __STL_UNWIND((destroy(__new_start,__new_finish),
                    _M_deallocate(__new_start,__len)));
      destroy(_M_start, _M_finish);
      _M_deallocate(_M_start, _M_end_of_storage - _M_start);
	  //修改迭代器的指向
      _M_start = __new_start;
      _M_finish = __new_finish;
      _M_end_of_storage = __new_start + __len;
    }
  }
}

erase

	//删除单个元素
  iterator erase(iterator __position) {
  	//如果删除的不是最后一个元素，组删除点之后的元素往前移动一个位置
    if (__position + 1 != end())
      copy(__position + 1, _M_finish, __position);
    --_M_finish;
    destroy(_M_finish);
    return __position;
  }
  //删除连续的元素
  iterator erase(iterator __first, iterator __last) {
  	//从last 开始到_M_finish写入到__first开始的位置，对删除的元素进行覆盖
    iterator __i = copy(__last, _M_finish, __first);
    destroy(__i, _M_finish);
    _M_finish = _M_finish - (__last - __first);
    return __first;
  }

其他

  bool empty() const
    { return begin() == end(); }

  size_type size() const
    { return size_type(end() - begin()); }

	//如果访问__n 越界了, 会抛出异常
  reference at(size_type __n)
    { _M_range_check(__n); return (*this)[__n]; }

	//如果访问__n 越界了， 程序会直接崩掉
 reference operator[](size_type __n) { return *(begin() + __n); }