《STL源码剖析》之vector

STL中容器分为序列式容器和关联式容器，其中vector作为最常用的序列式容器之一。

template<typename T,typename Alloc=alloc>
 class vector
 {
 public:
 typedef    T                    value_type;
 typedef   value_type*          pointer;
 typedef   ptrdiff_t             difference_type;
 typedef   value_type*           iterator;
 typedef   value_type&           reference;
 typedef   size_t                size_type;
 protected：
 typedef simple_alloc<value_type,Alloc> data_alllocator;
// .....                           其他的后面再说    
};

我们可以看出来，这里vector的Iterator是T，即vector::iterator-->T。当然这个显而易见，这与后面的deque等的iterator差别很大。这样在效率上就会有很好的保障，同样安全性也会有很好的体现。

在vector中有几个函数用到的非常多：fill_initialize，uninitialized_fill_n，以及copy，第一个为对已分配内存进行初始化并且指示出开头结尾，第二个为STL中的一个全局函数，用作将从heap得到的内存初始化。第三个就是数据转移，这个函数对于vector属于至关重要的一个。

//----------------------fill_initlialize------------------------------

  void fill_initialize(size_type n, const T& value)
{
start=allocate_and_fill(n,value);           //start已使用空间的头部iterator
finish=start +n;                           //finish已使用空间的尾部iterator    
end_of_storage=finish;                    //end_of_storage分配空间的尾部iterator

}

//------------------------alloccate_and_fill------------------------------
iterator allocate_and_fill(size_type n,const T&x)
{
iterator result=data_allocator::allocate(n);
uninitialized_fill_n(result,n,x);
return result;
}

我们可以看出fill_initialize函数是将allocate_and_fill函数和iterator的开头结尾工作进行合并。

//------------------------public函数部分体现--------------------------------
template<typename T,typename Alloc=alloc>
class vector
{//..............数据部分暂且不提及
public:
   iterator begin();
   iterator end();
   vector();
   vector(size_type n,const T&value);
   vector(int n,const T&value);
   vector(long n,const T&value);
  reference operator[](size_type n);
   size_type size();
   void push_back(const T&x);
//......其余省略
};

从上面我们可以看出vector具有至少三个构造函数，这里对应了上面提及的fill_initialize函数，利用这个函数可以进行同一数据的多点多次存储。

vector必须有[]操作，因为我们在使用过程中往往可以将它看成一个无底数组，这样大大增加了使用起来的便利程度。

size函数这里的实现非常简单，因为vector不同于deque。vector作为一种连续存储容器，且Iterator作为typedef value* iterator可直接对iterator进行operator-或者operator+。

push_back即首先判断finish++>end_of_storage,如果是，则先分配较前者内存大小两倍内存，然后进行大块数据copy，在进行内存的initialize。

//--------------------insert,erase实现--------------------------------------
iterator erase(iterator first,iterator last)
{
iterator i= copy(last,finish,first);           //copy全局函数
destroy(i,finish);
finish=finish-(last-first);
return first;
}
iterator erase(iterator position)
{
if(position+1!=end())
copy(position+1,finish,position);
--finish;
destroy(finish);
return position;
}
//______________________________________
template<typename T,typename Alloc>
void 
vector<T,Alloc>::insert(iterator position,size_type n,
const T& x)
{
if(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)
{
uninitialized_copy(finish-n,finish,finish);
finish+=n;
copy_backward(position,old_finish,finish);
fill(position,position+n,x_copy);
}
else
{
uninitialized_fill_n(finish,n-elems_after,x_copy);
finish+=n-elems_after;
uninitialized_copy(position,old_finish,finish);
finish+=elems_after;
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;
//---------------分配空间及异常处理，不再续写
}
}

上图作为insert操作的图示可以看出，insert需要保存position点或者position段之后的数据，也就是说我们需要在插入之前把finish到position->first点之间的所有数据全部向后移动size(position)个位置。

于是我们必须考虑以下情况：

1 size（position)==0，那就不用移动了。

2 为初始化空间尚能容下size(position),如果不能则需要重新分配更大空间然后进行数据复制，在进行insert操作

3 size（position)>position->last-finish，先在finish后面初始化position的元素的size(position)-(last-finish)部分，把last到finish之间的所有全部后移，再把position前部放进去

4size（position)last-finish ,直接进行后移即可。

erase操作不同于insert，他需要把数据磨灭即可，即不管从first部分到position从前向后移动或者是从finish到position从后向前移动都可以，但是问题就在于：

1，vector不是deque，vector在头部的操作复杂度太高，而deque则可以很好解决，故我们不需要判断position的位置与(finish-first)/2的关系，deque仍须要判断，因为在大容量数据的基础上，这个仍然属于考虑范围，算法暂时无法进行优化或者进行switch，以得到特殊情况下的优化。

2，不要忘了对finish到position移动后空余空间的数据placement delete，注意，此处不是operator delete，我们需要后面的分配的空间，但是不需要数据。

原文链接: https://www.cnblogs.com/dmq5488287/archive/2013/01/23/2873096.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍