vector容器
此节大概讲述一下VS STL的vector容器，对几个函数进行解析以及内部实现进行了解以下。
打开vector你会看到vector模板类真正含有的东西只有一个_Compressed_pair<_Alty, _Scary_val> _Mypair
_Mypair内部最重要的就是_Scary_val，它是一个别名，具体声明如下。
using
_Scary_val = _Vector_val<
conditional_t<
_Is_simple_alloc_v<_Alty>,
_Simple_types<_Ty>,
_Vec_iter_types<
_Ty,
size_type,
difference_type,
pointer,
const_pointer,
_Ty&,
const _Ty&>
>
>;
这个东西可有点长，简单点说，你可以就取前面的_Vector_val，如果你想要详细的解释的话……
_Vector_val中的conditional_t用来类型判断，它会根据第一个参数的true或false，也就是_Is_simple_alloc_v<_Alty>_的真值来选择后面两个类型的其中一个——是内置的int或double这样的类型，还是vector的类型。
比如说你定义了一个vector<vector<int>>，那么对于外面的vector来说，他的包含类型是vector<int>，而里面的就是int，这个判断过程就是利用模板参数自动判断类型的。
好了现在我们拿到了整个vector的类型，然后把他当作参数传给_Vector_val。而在_Vector_val里面有三个指针，这个指针的类型就是由刚才判断出来的类型定义的。
pointer _Myfirst;
pointer _Mylast;
pointer _Myend;
这三个指针就负责整个vector的大小指示。
请看：
_NODISCARD _CONSTEXPR20 size_type size() const noexcept {
auto& _My_data = _Mypair._Myval2;
return static_cast<size_type>(_My_data._Mylast - _My_data._Myfirst);
}
vector的size()内部就是用last指针减掉first指针算的，那么由此你也能想到capacity是怎么算得了。
_NODISCARD _CONSTEXPR20 size_type capacity() const noexcept {
auto& _My_data = _Mypair._Myval2;
return static_cast<size_type>(_My_data._Myend - _My_data._Myfirst);
}
由此，三个指针指出了vector的大小和容量。begin和end其实就是用这几个指针构造一个iterator出来然后返回（pass by value）。
容器函数
接下来我们讲解一个比较重要的函数，由此探究vector内部的细节。
insert
看过STL源码剖析的人可以不用看了，这东西20年都没变过，一模一样的。
那就直接来吧！（拔手榴弹）
_CONSTEXPR20 iterator insert(const_iterator _Where,
_CRT_GUARDOVERFLOW const size_type _Count,
const _Ty& _Val) {
// insert _Count * _Val at _Where
const pointer _Whereptr = _Where._Ptr;
auto& _Al = _Getal();
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
const pointer _Oldfirst = _My_data._Myfirst;
const pointer _Oldlast = _Mylast;
这里直接分析insert(position, n, value)这一插入函数，因为比较有代表性。
可以看到它首先取得一些需要的东西，比如分配器，限制范围的指针（就是刚才我们提到的那三个东西，他们都存在_Mypair._Myval2中），然后存一下插入之前的开头和结尾_Oldfirst, _Oldlast
...
const auto _Whereoff = static_cast<size_type>(_Whereptr - _Oldfirst);
const auto _Unused_capacity = static_cast<size_type>(_My_data._Myend -
_Oldlast);
const bool _One_at_back = _Count == 1 && _Whereptr == _Oldlast;
...
接下来继续计算，算出了插入位置之前的元素的数量，容量内未被使用的空间大小，以及一个bool值。
这个bool变量代表着插入的一个元素是否是在结尾。之后的程序根据这个bool值采取一些不同的行为（可能这种插入比较简单，不需要大量的移动或构造，所以直接单独拿出来简单处理）
...
if(_Count==0){}
else if(_Count > _Unused_capacity){
...
}
else if(_One_at_back){
...
}
else{
...
}
return _Make_iterator_offset(_Whereoffl)
这个是整个insert内部大致的结构，如果_Count为0，那么什么都不做。如果需要插入的元素大于剩余空间，就需要重新另找地方去放置这个vector了。而如果只在尾部插入一个元素，那就可以简单处理。
让我们按顺序看一下，首先就是_Count > _Unused_capacity的情况。
const auto _Oldsize = static_cast<size_type>(_Oldlast - _Oldfirst);
//max_size是分配器能分配的最大数量，也是vector容量上限
if(_Count > max_size() - _Oldsize){
_Xlength(); //如果_Count数量大于容量上限，则出错_Xlength();
}
const size_type _Newsize = _Oldsize + _Count;
//每次申请的容量是之前的1.5倍，之后我会谈及它的好处
const size_type _Newcapacity = _Calculate_growth(_Newsize);
//这里重新申请了新容量大小的vector空间
const pointer _Newvec = _Al.allocate(_Newcapacity);
const pointer _Constructed_last = _Newvec + _Whereoff + _Count;
pointer _Constructed_first = _Constructed_last;
//宏 try{
_TRY_BEGIN
//这里先将需要插入的数值率先复制，注意_Constructed_first指向目前已经构造的开头
_Uninitialized_fill_n(_Newvex + _Whereoff, _Count, _Val, _Al);
_Constructed_first = _Newvec + _Whereoff;
/*注意，这里是在重新_Count > _Unused_capacity的情况下在后面新插入一个元素
之前我们已经将插入的元素构造完毕了，加下来只要把之前源vector的元素复制过去就可以了
括号内部有一个很长的逻辑表达式，目的是选出最佳的复制方式。
如果_Ty类型定义了移动构造函数，则选择移动构造，否则复制构造
*/
if(_One_at_back){
if constexpr (is_nothrow_move_constructible_v<_Ty>||
!is_copy_constructible_v<_Ty>){
_Uninitialized_move(_Oldfirst, _Oldlast, _Newvec, _Al);
}else{
_Uninitialized_copy(_Oldfirst, _Oldlast, _Newvec, _Al);
}
}
//宏 }catch(...){
_CATCH_ALL
//异常发生，销毁复制的内存
_Destroy_range(_Constructed_first, _Constructed_last, _Al);
_Al.deallocate(_Newvec, _Newcapacity);
//宏 throw
_RERAISE
//宏 }
_CATCH_END
//这一步会销毁旧vector，将新的三个指针赋给_Mypair._Myval2
_Change_array(_Newvc, _Newsize, _Newcapacity);
接下来是_One_at_back的情况
_Emplace_back_with_unused_capacity(_Val);//直接尾部构造，同时更新大小
最后一种情况
const _Alloc_temporary2<_Alty> _Tmp_storage(_Al, _Val);//handle aliasing
const auto& _Tmp = _Tmp_storage._Get_value();
const auto _Affected_element = static_cast<size_type>(_Oldlast-_Whereptr);
//使指向受影响元素的迭代器失效，之后会讲解
_Orphan_range(_Whereptr, _Oldlast);
//以一图诠释
if(_Count > _Affected_elements){
_Mylast = _Uinitialized_fill_n(_Oldlast, _Count - _Affected_elements
_Tmp, _Al);
_Mylast = _Uninitialized_move(_Whereptr, _Oldlast, _Mylast, _Al);
STD fill(_Where, _Oldlast, _Tmp);
} else{
_Mylast = _Uninitialized_move(_Oldlast - _Count, _Oldlast,
_Oldlast, _Al);
_Move_backward_unchecked(_Whereptr, _Oldlast - _Count, _Oldlast);
_STD fill(_Whereptr, _Whereptr + _Count, _Tmp);
}
if中的两种情况对应以下两图
and
之后我们关注实现中的两个细节——一是扩容系数是1.5倍数，二是orphan_range的作用。
-
1.5倍扩增的优点
首先，按倍扩增的插入均摊复杂度是O(1)，而按固定数值扩增的均摊复杂度是O(n)。然后假如vector每次2倍扩增，那么它将无法利用已经删除的空间，比如有如下扩增序列
1,2,4,8,16,32，而每次扩增剩下的空间为——0,1,3,7,15,31。可以看到无论如何前面剩余的空间将放在那里，造成浪费。
假如是按1.5倍扩增，扩增序列如下（取整）
1,2,3,4,6,9,13,19，而每次扩增剩下的空间为——0,1,3,6(这里的6可以被下一次扩增填满),0,6,15,28（下一次扩增到19+9=28又可以利用前面的空间）。
-
_Orphan_range()
假设有如下程序
vector<int> test = {1,2,3,4,5}; test.reserve(20); vector<int>::iterator iter = a.begin() + 2; a.insert(a.begin(),3); cout<<*iter<<endl;运行之后你会发现程序报错，就在进行iter解引用输出那里发生了错误。
现在，我们把插入位置改一下，改成在iter指向元素的后面插入
a.insert(a.begin() + 3,3);程序正常运行。
你看，iter会根据你insert的位置决定自身是否合法，如果插入之后iter不再指向之前的元素，他就会失效。如果位置不变就不会。
这个决定哪些迭代器失效的函数就是
_Orphan_range()负责的。回到插入函数，再插入位置后面的所有元素都会被影响，所以那些指向他们的迭代器都会失效，所以才会在源代码中出现下列调用
_Orphan_range(_Whereptr, _Oldlast);
结语：通过_Mypair和insert的大致了解，其实你就能对vector容器有个大致的把握了，很多vector的接口都和三个标识大小的指针脱不了干系，而涉及到动态内存方面的……既然insert那几种情况都搞懂了，其他的还难吗？