[系统运维]【STL源码剖析】总结笔记（3）：vector初识

00 写在前面

vector是我们在学习c++过程中最早接触也是比较常用的容器之一，从vector入手可以更加容易地理解STL的组织架构。这里我们侧重于vector的内部结构，而vector提供的接口操作不是我们的重点，使用方法可以参考cppreference。

01 概述

array我们经常使用，但它是静态空间，不能做到动态分配内存。大小在一开始就已经固定了。

vector和array很相似，区别在于vector是动态空间，它的内部机制会自行扩充空间以容纳新元素。也不需要像array一样在使用大空间前申请大块内存。而且我们也能看到vector在扩充时“未雨绸缪”的能力。

02 vector的数据结构

基本结构

先来看一张图

vector的结构如上图所示。因为是线性连续空间，所以较为简单。

vector内部有三个迭代器，start，finish和end of storage。

start和finish指向已占用空间的首端和尾端（注意这个尾端是最后一个元素的下一位，左闭右开）

end of storage指向整块连续空间的尾部。

代码如下：

template <class T,class Alloc=alloc>
class vector {
    ...
    protected:
    	iterator start;
    	iterator finish;
    	iterator end_of_storage;
    ...
}

这里所使用的分配器alloc我们后续深入探讨。迭代器iterator暂时理解为指针。

所以vector的大小也一目了然。一个指针4个字节（32位），所以vector在这个版本中的大小为12个字节。

衍生结构

因为这三个迭代器的存在，vector提供的其他诸如计算数据大小size,容器容量capacity的各种方法就可以很容易地实现了。

先来看代码，再逐一解释：

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

1. begin()和end()的实现很直接，返回我们上面说的的start和finish迭代器（指针）。
2. 数据的大小size()就是返回尾减去头的结果。这里使用finish-start更快，但是使用begin()-end()方便维护。
3. 容器的容量capacity()的实现是返回指向整块空间尾部的迭代器减去开头的结果。
4. 空的情况就是头与尾相等。
5. 重载[ ]，也就是我们常用的取vector中的下标元素，返回的是解引用的结果（下标从0开始）。
6. 返回第一个元素和最后一个元素的实现是使用begin()和end()解引用的结果。注意end()指向的是最后一个元素的下一位置。

03 vector的内存管理

原理

再来看一张图

vector的内存是二倍增长的，当放数据时发现空间已经满了，vector就会寻找新的二倍大小的空间，再将原来的值复制过去，然后释放原空间。

源码分析

我们从push_back()这个插入新元素的操作就可以看到vector内存管理的方法

void push_back(const T& x)
{
    if(finish != end_of_storage)
    {
        construct(finish,x);
        ++finish;//移动迭代器
    }
    else
    {
        insert_aux(end(),x);
    }
}

push_back()在数据没有满时将其加入，再重新调整迭代器位置。

如果满了则调用insert_aux()

再来看insert_aux()

template <class T,class Alloc>
    void vector<T,Alloc>::insert_aux(iterator position,const T& x){
        if(finish != end_of_storage){//1
            ...
            ++finish;
            ...
        }
        else{
            const size_type old_size=size();//2
            const size_type len=old_size!=0?2*old_size:1;//3
            
            iterator new_start =data_alloctor:allocate(len);//4
            iterator new_finish=new_start;
            
            try{
                new_finish=uninitialized_copy(start,position,new_start);//5
                construct(new_finish,x);//6
                ++new_finish;//6
                
                new_finish=uninitialized_copy(position,finish,new_finish);//7
            }
            catch(...){
                ...
            }
            
            destroy(begin(),end());//8
            dellocate();
            
            start=new_start;//9
            finish=new_finish;
            end_of_storage=new_start+len;
        }
    }

这段代码稍微长一点，我们详细解释一下。

1. 在insert_aux内部又做了一次判断，判断数据是否已经放满。
2. 如果已经满了，那么就记录一下原来的大小old_size
3. 这句很关键。如果原来的大小为0，就扩展为1；不为0就扩展为2倍大小。
4. 这里才是真正分配空间的地方。得到二倍空间后，建立新的start，然后让新的finish等于它。
5. 开始拷贝原来vector中的值。
6. 还有要添加的元素没有放进去。这时构造新元素，再调整new_finish的位置。
7. 其实到这里放入元素的操作已经可以结束了。但是insert_aux()可能还会被其他函数调用，比如insert()，这时就会有一个安插位置的概念。那么还需要把安插点后面的内容也拷贝过来。
8. 释放原来的vector空间
9. 调整新的迭代器的位置

需要特别注意的点

1. 动态空间增加不是单纯地增加大小，而是在新空间上进行拷贝操作。
2. 空间配置后所有指向原来vector的迭代器就会失效。

04 vector的迭代器

虽然迭代器的结构我们还没有探究，但是由于vector维护的是一个连续线性的空间，所以一些需要的操作如*，->，++，–，+=，-=，普通指针都可以满足。

所以vector的迭代器其实就是普通指针，也就是random access iterators。

template <class T,class Alloc=alloc>
    class vector{
        public:
        	typedef T value_type;
        	typedef value_type * iterator;//普通指针
        ...
    };

05 vector的添加与删除

pop_back()

删除尾端元素实现比较简单，直接把末尾标记前移，再销毁元素。

void pop_back(){
    --finish;
    destory(finish);
}

erase

erase有两种用法，我们说一下清除first到last之间的元素。（注意是[first,last)左闭右开）

先看图:

基本思路就是把last后面的内容复制到first的位置，再调整新的finish位置。

iterator erase(iterator first,iterator last){
    iterator i= copy(last,finish,first);//复制last到finish位置的数据到first
    destroy(i,finish);
    finish=finish-(last-first);//调整新的finish
    return first;
}

1. 关于destroy()，会在迭代器部分细说。在这里是接受first和last两个迭代器，将两个迭代器范围内的对象析构。
2. 关于copy()，会在算法部分出现，就是我们上面说到的复制，但是会返回一个迭代器:result+(last-first),也就是返回复制后数据的下一个位置，这也是为什么在destroy中是从i到finish，翻译一下就是从新的finish到原来的finish。

insert

insert的用法是insert(position,n,x),即从position开始，插入n个元素，初值为x。

在实现过程中有以下几个情况：

首先是备用空间充足的情况下：

if(size_type(end_of_storage-finish)>=n)
{
    T x_copy=x;
    const size_type elems_after=finish-position;//计算插入点后现有的元素
    iterator old_finish=finish;
    ...
}

1. 插入点后现有的元素>新增元素个数
   比如插入2个，而现在position后面有三个

if(elem_after>n){    
	uninitialized_copy(finish-n,finish,finish);    
	finish +=n;    
	copy_backward(position,old_finish-n,old_finish);    
	fill(position,position+n,x_copy);}

图示中，第二步调用的是uninitialized_copy(),第三步调用的是copy_backward()。

当然大家都会很好奇为什么这两步要拆开拷贝，而不能一气呵成。

暂时理解为uninitialized_copy()是要将数据拷贝到未初始化的区域，比如移动两位则需要占用两位备用空间，所以要移动的范围是[finish-2,finish)

另外也不能单独调用copy_backward()，会出现没有调用构造函数就被析构的情况（uninitialized_copy()调用构造函数）

2. 插入点之后的现有元素<=新增元素个数
   比如插入3个，而现在position后面有两个
   

else{    
	uninitialized_fill_n(finish,n-elems_after,x_copy);    
	finish+=n-elems_after;    
	uninitialized_copy(position,old_finish,finish);    
	finish+=elem_after;    
	fill(position,old_finish,x_copy);}

先从finish开始添加n-elems_after个元素，再更新一下finish。

然后在把原来的元素拷贝到新的finish后面。

最后在将空缺位置补满。

这个也比较好理解，不管添加多少个元素（当然要满足前提条件），比如10个20个，那么插入位置后面的元素的位置都会被占用，所以先将后面的填满，再把有元素的地方替换即可。

在空间不足的情况下也会二倍增长

else{    
	const size_type old_size=size();//1    
	const size_type len = old_size+max(old_size,n);//2        
	iterator new_start=data_alloctor:allocte(len);//3    
	iterator new_finish=new_start;//3    _STL_TRY{//4        
	new_finish=uninitialized_copy(start,position,new_start);//5        
	new_finish=uninitialized_fill_n(new_finish,n,x);//6        
	new_finish=uninitialized_copy(position,finish,new_finish);//7    }  

1. 记录原来的size
2. 扩充空间，有可能是旧长度的二倍，如果插入元素个数大于原来的size，那么新长度就是old_size+n
3. 申请新的空间，设置新的start和finish
4. 因为这块空间都没有初始化，所以都是使用uninitialized_，注意这段操作一直在为new_finish赋值，更新new_finish
5. 首先将插入位置之前的数据拷贝过来。从start到position拷贝到new_start
6. 再从插入点（也就是new_finish）开始填入n个x
7. 将原来vector中插入点后的数据拷贝过来（position到finish）

06 总结

vector内部的实现大部分与我们预想的一致，也有小部分非常灵活的实现。只需要明确它有三个重要的迭代器，了解其内存分配的原理与主要功能的实现即可。

总的来说不管是学习STL的使用还是分析其内部结构，vector都是非常适合入手的。