stl源码剖析(七)vector（std源码）

一、概述

vector的数据安排及操作方式与array很相似，二者唯一差别在于空间运用的灵活性。

1.array是静态空间，一旦配置了大小，就不能改变，要换个大或者小点的空间，得有客户端自己来操作。

2.vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。vector相对于array来说就是可以自己内部进行内存的动态缩减，vector这种操作有有点也有缺点。

【优点】

vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，不必因空间不足而一开始就申请一大块内存。

【缺点】

vector内部空间的扩充主要经历三步：

1）配置新空间。

2）数据移动。

3）释放旧空间。

这种行为的时间成本很高。针对这个问题vector内部本身有一定的策略进行处理，同时使用者在使用的过程中也应该要有考虑到此问题并要有一定的处理策略。

二、迭代器

1.vector维护的是一个连续性的空间。

2.vector迭代器所需要的操作行为，普通指针天生就具备，例如：operator*，operator->，operator++，operator–，operator+，operator-，operator+=，operator-=。

3.vector支持随机存储，而普通指针也可以。

所以vector迭代器种类是Random Access Iterators。

template <class T, class Alloc = alloc>
class vector {
public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator; //Vector 的迭代器就是普通指针。
  ...
  }

如果客户端定义如下代码：

ivite的型别就是int*，svite的型别就是Shape*。

三、数据结构

vector采用的数据结构非常简单：线性连续空间。以两个迭代器start和finish分别指向配置得来的连续空间中已被使用的范围，并以迭代器end_of_storge指向整块连续空间（含备用空间）的尾端。

template<class T, class Alloc = alloc>
class vector
{
...
protected:
	iterator start;  		//表示目前使用空间的头
	iterator finish; 		 //表示目前使用空间的尾
	iterator end_of_storage; //表示目前可用空间的尾
...
}

为降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充，这便是容量(capacity)的观念，换句话说，一个vector的容量永远大于或等于其大小。一旦容量等于大小，便是满载，下次再有新增元素，整个vector就要开始进行新空间申请、元素的移动、旧空间的释放等操作。

以start，finish，end_of_storage三个迭代器元素操作及容量计算：

template<class T, class Alloc = alloc>
class vector
{
...
public:
	iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const { return size_type(end() - begin()); }
    size_type capacity() const { return size_type(end_of_storage - begin()); }
    bool empty() const { return begin() == end(); }
  	reference operator[](size_type n) { return *(begin() + n); }
  	reference front() { return *begin(); }
  	reference back() { return *(end() - 1); }
  	...
}

四、构造与内存管理

vector缺省使用alloc作为空间配置器，为方便以元素大小为配置单位，定义了一个data_allocator。

template< class T, class Alloc = alloc>
class vector
{
	typedef simple_alloc<value_type, Alloc> data_allocator;
...	
}

于是data_allocator::allocate(n)表示配置n个元素空间。

【构造】

vector提供许多constructors，其中一个允许我们指定空间大小及初值：

//构造函数，允许指定vector大小n和初值value
vector(size_type n, const T& value){fill_initialize(n, value)}
//填充并予以初始化
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个元素空间
	uninitialized_fill_n(result, n, x); //全局函数
	return result;
}

处于性能考虑，uninitialized_fill_n会根据第一个参数的型别特性（用到参数类型萃取，可参考Traits编程技法），决定使用算法fill_n( )，或反复调用construct( )来完成任务。

【内存管理】

当我们以push_back（）将新元素插入vector尾端时，会做以下处理步骤：

1.首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器finish，使vector变大。

2.如果没有备用空间，就扩充空间（重新配置、移动数据、释放原空间）。

void push_back(const T& x) 
{
    if (finish != end_of_storage) 
    {
      //还有备用空间
      construct(finish, 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) 
	 {
	   //还有备用空间
	   //在备用空间起始处构造一个元素，并以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();
		const size_type len = old_size != 0 ? 2 * old_size : 1;
		//以上配置原则：如果原大小为0，则配置1（个元素大小）
		//如果原大小不为0，则配置原大小的两倍。
		//前半段用来放置原数据，后半段用来放置新数据。
		iterator new_start = data_allocator::allocate(len);
		iterator new_finish = new_start;
		__STL_TRY 
		{
		    //将原vector的内容拷贝到新vector
			new_finish = uninitialized_copy(start, position, new_start);
			//为新元素设置初值
			construct(new_finish, x);
			//调整水位
			++new_finish;
			//将安插点的原内容也拷贝过来
			new_finish = uninitialized_copy(position, finish, new_finish);
		}
	
		#ifdef  __STL_USE_EXCEPTIONS 
		catch(...) 
		{
			destroy(new_start, new_finish); 
			data_allocator::deallocate(new_start, len);
			throw;
		}
		#endif /* __STL_USE_EXCEPTIONS */
		//析构并释放原vector
		destroy(begin(), end());
		deallocate();
		
		//调整迭代器，指向新vector
		start = new_start;
		finish = new_finish;
		end_of_storage = new_start + len;
	}
}

上述push_back()进行了备用空间大小检查，insert_aux()也进行了备用空间检查，那是因为insert_aux()不仅仅给push_back()使用，还被其它调用这使用。

【1】插入单个元素时如果空间不足，申请新空间规则如下：

insert_aux(iterator position, const T&)
{
...
	const size_type old_size = size();
	const size_type len = old_size != 0 ? 2 * old_size : 1;
...
}

【2】插入批量数据时如果空间不足，申请新空间规则如下：

insert(iterator position, size_type n, const T& x)
{
...
	 const size_type old_size = size();        
     const size_type len = old_size + max(old_size, n);
...
}

所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置空间），而是心申请特定大小的空间，然后将原内容拷贝过来，并释放原空间。因此对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了，这个要多注意。

五、元素操作

vector提供的元素操作很多，为搭配上文对内存管理的操作讨论，这里只讲解下erase和insert。

5.1 erase()

【清除某个位置上的元素】

 //清除某个位置上的元素
 iterator erase(iterator position)
 {
    //1、如果清除的不是最后一个元素，就将要清除位置之后的元素向前移动，然后删除掉最后一个元素。
    //2、如果清除的是最后一个元素，直接调整finish位置，然后清除最后一个元素即可。
    if (position + 1 != end())
      copy(position + 1, finish, position);
    --finish;
    destroy(finish);
    return position;
  }
【清除某个区间中的所有元素】
//清除[first, last)中的所有元素，前闭后开区间
 iterator erase(iterator first, iterator last) 
 {
    iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first);
    return first;
  }

5.2 insert()

5.2.1 源码

从position开始，插入n个元素，元素初值为x。

template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) 
{
  if (n != 0) 
  {
    //n非0，才会进行如下操作
    if (size_type(end_of_storage - finish) >= n) 
    {
        //备用空间大于等于“新增元素个数”
		T x_copy = x;
		//计算插入点之后的现有元素个数
		const size_type elems_after = finish - position;
		iterator old_finish = finish;
		if (elems_after > n) 
		{
		    //“插入点之后的现有元素” 大于 “新增元素个数”
		    //1、将finish前面的n个元素拷贝到finish后面（内部会考虑是一个一个拷贝构造还是
		    //直接移动内存内容来实现复制行为）。
			uninitialized_copy(finish - n, finish, finish);
			//2、调整水位线。
			finish += n;
			//3、直接[position, old_finish-n]以后拷贝方式拷贝到之前的finish位置。
			copy_backward(position, old_finish - n, old_finish);
			//4、开始填充新元素。
			fill(position, position + n, x_copy);
			
			<!注意：这里为什么不直接将position之后的元素移动拷贝到相应位置之后呢？
			<!只所以不这样操作是处于内存效率考虑，因为针对未初始化的区域涉及到内存的配置和元素的构造，
			<!如果是已知区域，可直接调用copy_backward()，省略内存的配置这一步操作。
		}
		else 
		{
		    //“插入点之后的现有元素个数” 小于等于 “新增元素个数”
		    //1、先在finish位置之后，填充n-elems_after个元素
			uninitialized_fill_n(finish, n - elems_after, x_copy);
			//2、调整finish位置
			finish += n - elems_after;
			//3、将[position, old_finish)范围内的元素复制到新finish之后
			uninitialized_copy(position, old_finish, finish);
			//4、再次调整finish位置
			finish += elems_after;
			//5、插入剩余的x_copy元素
			fill(position, old_finish, x_copy);
		}
    }
    else 
    {
        //备用空间小于“新增元素个数”（那就必须配置额外的内存）
        //首先决定新长度：旧长度的两倍，或旧长度+新增元素个数
		const size_type old_size = size();        
		const size_type len = old_size + max(old_size, n);
		iterator new_start = data_allocator::allocate(len);
		iterator new_finish = new_start;
		__STL_TRY 
		{
		    //1、将[start, position)元素拷贝到新内存区域
			new_finish = uninitialized_copy(start, position, new_start);
			//2、从new_finish开始填充n个元素个数
			new_finish = uninitialized_fill_n(new_finish, n, x);
			//3、将[position，finish)区间元素拷贝到新内存区域
			new_finish = uninitialized_copy(position, finish, new_finish);
		}
  #ifdef  __STL_USE_EXCEPTIONS 
      	catch(...) 
		{
		    //如果有异常发生，实现“commit or rollback” semantics
			destroy(new_start, new_finish);
			data_allocator::deallocate(new_start, len);
			throw;
		}
  #endif /* __STL_USE_EXCEPTIONS */
      //释放旧内存区域元素
      destroy(start, finish);
      //释放旧内存
      deallocate();
      //调整新的水位线
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}