【决战西二旗】|理解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和使用者中间加了一层，从而把使用者从对数组的直接管理权接手过来，让使用者有个管家一样，在毫无影响使用的前提下更加省心和高效。
透过现象看本质
空间分配
看
//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个元素，元素初值为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) {
//“插入点之后的现有元素个数”大于“新增元素个数”
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);
}
catch(...) {
//如有异常发生，实现”commit or rollback"semantics
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
//以下清楚并释放旧的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/
原创不易 生活更难点赞在看 养成习惯走心走肾不如走一波分享坚持写的我&坚持读的你 都比昨天更优秀！