【决战西二旗】|理解STL vector原理

大白斯基后端技术指南针

Vector概述

STL中的Vector是最为常用的顺序容器之一，与C/C++中的数组Array很相似，最重要的区别在于对连续内存空间运用的灵活性。

数组真叫人为难

我们在使用数组Array时要指定数组的大小，而后由系统来分配连续的内存空间，Array是静态空间必须指定大小且指定之后自动无法扩缩容，因此为了避免元素装不下，一般都把数组设置的比预期要大，但是往往导致空间的浪费。

另外往往很多时候需装载元素的数量无法预期，这样设置怎样的大小就取决于使用者了。如果最初数组设计比较小，那么就面临着开辟新的更大空间、将旧空间元素复制到新空间、释放旧空间三个大步骤，这一切都是需要使用者自己来维护实现的。

使用数组太大浪费空间、太小浪费效率，真的很希望有个助手帮我们做了这些事情，专业的人做专业的事情，让我们只关心业务逻辑即可，那该多好！

它来了，踏着七彩祥云

就这样盼望着盼望着东风来了春天的脚步近了，不不， vector的脚步近了….

vector底层与Array一样都是连续的内存空间，区别在于vector的空间是动态的，随着更多元素的加入可以自动实现空间扩展，并且vector针对这种扩展做了优化，并不是one by one的扩展，那样实在是低效，而是按照某种倍率来扩展，这样就有效了减少因为扩容带来的复制效率降低问题。

简单来说就是当需要放置1个元素时，vector空间已满，此时vector并不会只向系统申请1个元素的空间，而是按照目前已占用的空间的倍率来申请。

假如原来占用A字节，那么再次申请时可能是2A字节，由于此时向尾部地址扩展不一定有连续未分配的内存，大多时候还是会涉及开辟新的更大空间、将旧空间元素复制到新空间、释放旧空间三个大步骤。

所以和数组相比底层的操作都是一样的，不要把Vector神话，都是普通的结构只不过被封装了一层而已。

从本质上看，vector就是在普通Array和使用者中间加了一层，从而把使用者从对数组的直接管理权接手过来，让使用者有个管家一样，在毫无影响使用的前提下更加省心和高效。

透过现象看本质

空间分配

看中对vector的定义(节选部分成员变量)

//alloc是SGI STL的空间配置器template <class T,class Alloc=alloc>class vector{public:    typedef T   value_type;    typedef value_type*  pointer;    typedef value_type*  iterator;    typedef value_type&  reference;    typedef size_t   size_type;    typedef ptrdiff_t   difference_type;protected:    //simple_alloc是SGI STL的空间配置器    typedef simple_alloc<value_type,Alloc> data_allocator;    //表示目前使用空间的头    iterator start;     //表示目前使用空间的尾    iterator finish;     //表示目前可用空间的尾    iterator end_of_storage;}

从定义看vector 是一种前闭后开的容器，在vector里头有一些变量记录着一些信息，分别是三个迭代器：

start：表示目前使用空间的头
finish：目前使用空间的尾
end_of_storage：目前可用空间的尾
vector的空间示意图：

vector中有三个和容量空间相关的成员函数：size、capacity、empty。

其中size代表已存储的元素数量，capacity表示可以容纳的最大元素数量，empty判断是否无元素存储，这些判断也都是依据迭代器来实现的，定义如下：

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();}

迭代器

vector由于在底层和数组没有区别，都是地址连续的内存空间，因此普通指针具备vector迭代器的重要功能，诸如：
*、->、++、--、+、-、+=、-=
这些迭代器操作，都可以由指针来实现。

//迭代器举例iterator begin(){    return start;}iterator end(){    return finish;}reference front(){    return *begin();}reference back(){    return *(end() - 1);}

push_back

在使用push_back()将元素插入vector尾端时的基本流程：

仍有空间直接在剩余空间上构造元素，并调整迭代器finish指向
已无空间扩充空间（重新分配、移动数据、释放旧空间）
扩充空间时调用另外一个成员函数insert_aux来实现，其中我们可以看到更多的细节。
代码定义如下：

void push_back(const T& x)//添加元素{    //是否超出最大可容纳空间    if(finish !=end_of_storage){        /*全局函数，construct()接收一个指针p和一个初值value，        该函数的用途就是将        初值value设定到指针锁指的空间上。        */        construct(finish,x);        ++finish;    }    else{        insert_aux(end(),x);  //vector的成员函数    }}template <class T, class Alloc = 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;        try {            //将原vector的内容拷贝到新vector            new_finish = uninitialized_copy(start, position, new_start);            //将新元素设定初值x            construct(new_finish, x);            //调整水位            ++new_finish;            //将安插点的原内容也拷贝进来（提示：本函数也可能被insert(p,x)调用）            new_finish = uninitialized_copy(position, finish, new_finish);        }        catch(...) {            //"commit or rollback" semantics            destroy(new_start, new_finish);            data_allocator::deallocate(new_start, len);            throw;        }        //析构并释放原vector        destroy(begin(), end());        deallocate();        //调整迭代器，指向新vector        start = new_start;        finish = new_finish;        end_of_storage = new_start + len;    }}

insert

insert成员函数也是实现元素添加的主要函数，因此也涉及了与push_back类似的扩容过程，但是比push_back更复杂一些，在插入元素时需要根据插入点、备用空间大小、待插入元素数量等角度进行分类对待，详细过程看下代码定义：

//从position开始，插入n个元素，元素初值为xtemplate <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) {                //“插入点之后的现有元素个数”大于“新增元素个数”                uninitialized_copy(finish - n, finish, finish);                finish += n;    //将vector尾端标记后移                copy_backward(position, old_finish - n, old_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);            //以下配置新的vector空间            iterator new_start = data_allocator::allocate(len);            iterator new_finish = new_start;            __STL_TRY {                //以下首先将旧vector的插入点之前的元素复制到新空间                new_finish = uninitialized_copy(start, position, new_start);                //以下再将新增元素(初值皆为n)填入新空间                new_finish = uninitialized_fill_n(new_finish, n, x);                //以下再将旧vector的插入点之后的元素复制到新空间                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 */        //以下清楚并释放旧的vector        destroy(start, finish);        deallocate();        //以下调整水位标记        start = new_start;        finish = new_finish;        end_of_storage = new_start + len;        }    }}

插入点、备用空间大小、待插入元素数量等角度进行分类：

1-1 插入点之后元素个数大于新增元素个数：

A. 将finish之前的n个元素移到finish之后
B. finish变更为finish + n得到newfinish
C. 将position之后到oldfinish - n之间的元素后移到oldfinish位置
D. 从position开始填充n个x

1-2 插入点之后元素小于新增元素个数

A. 将差值补到finish之后
B. finish变更为finish + n - elems_after得到newfinish
C. 将position到oldfinish的元素拷贝到newfinish之后
D. 在position到oldfinish之间插入x

2. 备用空间小于新增元素个数

A. 申请空间，old_size + max(old_size, n)
B. 复制填充：
c. 将原vector插入点之前的元素拷贝到新空间
D. 将新增元素填入新空间
E. 将原vector插入点之后的元素拷贝到新空间

这个过程还是比较有意思的，其中涉及到了几个泛型拷贝：
uninitialized_copy和copy_backward等，可以再自己细致地画一下图理解这个过程，在此不再赘述。

参考资料

STL源码剖析
https://ershengaaa.github.io/2018/11/19/STL-vector/

【决战西二旗】|理解STL vector原理