—vector 剖析—
vector是STL的容器，下面从源码的角度剖析vector的相关扩容原理
涉及知识点：
vector 的 push_back() 的PJ 和 SGI 版本源码剖析。
vector 扩容原理。等长扩容，1.5倍扩容，2倍扩容，3、4、n倍扩容的优缺点。
linux 下开辟空间的原理。
vector 中 push_back() 涉及到的构造函数。
起初看vector源码一头雾水，因为我发现我用 Visual Studio IDE来查看源码，与网络上的公开vector源码不一致。
查阅资料才知道：
因为vector 属于 STL ，由于STL有了很多年的历史，于是衍生出不同版本的 STL。
1.PJ STL—被Visual C++采用 ，故我在Visual Studio查看的版本是PJ STL版本。
2.HP STL–HP版本是所有STL的起源
3.SGI STL版本—-注释丰富，结构清晰，可读性最强，同时它也被GCC采用，所以是最流行的版本，网络上大部分基于此源码分析。
1.vector实际扩容大小？
一、预实验
想法： 逐一向vector容器里添加元素，观察vector的实际元素大小（size）和容量大小（capacity）的变化趋势，代码如下：
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> vec;
cout << vec.capacity() << endl;
//逐一添加元素，观察size和capacity的变化
for (int i = 0; i < 20; ++i)
{
vec.push_back(i);
cout << "size: " << vec.size() << " and capacity: " << vec.capacity() << endl;
cout << " ---------------------" << endl;
}
system("pause");
return 0;
}
结果如下：
二、分析
可以看到Size的增长规律：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> ….
对应Capacity增长规律：1 -> 2 -> 3 -> 4 -> 6 -> 6 -> 9 -> 9 -> 9 -> 13 -> ….
通过观察发现，随着size的线性增长
capacity 除 1 -> 2 为双倍增长， 剩余增长规律都符合1.5倍往下取整数。
下面从 PJ 和 SGI 两个版本的源码来分析验证 vector 的扩容机制：
PJ版本：
1、我们从Vector 中依次进入push_back() —> empalce_back() —> _Emplace_one_at_back() —> *_Emplace_reallocate()：
这部分代码简单来说就是 push_back() 实际调用了 emplace_back() 函数并向vector尾部插入了一个元素，若容量未满则直接向后添加元素，否则重新开辟空间
_CONSTEXPR20 void push_back(const _Ty& _Val) { // insert element at end, provide strong guarantee
emplace_back(_Val);
}
_CONSTEXPR20 decltype(auto) emplace_back(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
_Ty& _Result = _Emplace_one_at_back(_STD forward<_Valty>(_Val)...);
_CONSTEXPR20 _Ty& _Emplace_one_at_back(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
//判断插入后元素是否容量已满
if (_Mylast != _My_data._Myend) {
//未满则直接向后添加元素
return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
}
//否则重新开辟空间
return *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
}
_CONSTEXPR20 pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val) {
// reallocate and insert by perfectly forwarding _Val at _Whereptr
_Alty& _Al = _Getal();
auto& _My_data = _Mypair._Myval2;
pointer& _Myfirst = _My_data._Myfirst;
pointer& _Mylast = _My_data._Mylast;
_STL_INTERNAL_CHECK(_Mylast == _My_data._Myend); // check that we have no unused capacity
const auto _Whereoff = static_cast<size_type>(_Whereptr - _Myfirst);
const auto _Oldsize = static_cast<size_type>(_Mylast - _Myfirst);
if (_Oldsize == max_size()) {
_Xlength();
}
const size_type _Newsize = _Oldsize + 1;
const size_type _Newcapacity = _Calculate_growth(_Newsize); // 新的容量大小计算函数体
2、进入_Calculate_growth(）函数体
增长规律核心代码：
**可以看到 新的容量大小 _Geometric 以 1.5倍的原来容量大小 _Oldcapacity 增长，并且当扩容以后的 _Geometric 小于 添加元素后的大小时，则返回添加元素后的大小。否则返回扩容后 _Geometric大小。**
**这就解释了 Capacity增长规律：1 -> 2 -> 3 -> 4 -> 6 -> 6 -> 9 -> 9 -> 9 -> 13 -> ....中的 1 -> 2 不遵从1.5倍增长的原因。**
_CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {
// given _Oldcapacity and _Newsize, calculate geometric growth
const size_type _Oldcapacity = capacity();
const auto _Max = max_size();
if (_Oldcapacity > _Max - _Oldcapacity / 2) {
return _Max; // geometric growth would overflow
}
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
if (_Geometric < _Newsize) {
return _Newsize; // geometric growth would be insufficient
}
return _Geometric; // geometric growth is sufficient
}
SGI版本：
基本思想一致， 不同在于 SGI 版本 以原来容量的2倍进行扩容。
void push_back(const _Tp& __x) {
//finish指针 没有到达end的位置，表示还有空间可用
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, __x);
++_M_finish;
}
else
//否则，开始重新分配
_M_insert_aux(end(), __x);
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
_Tp __x_copy = __x;
copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = __x_copy;
}
else {
/* 获取旧的容量 */
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
/* 重新分配 */
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
/*try...catch子句，进行异常捕获，如果这个过程失败了，会回滚已经分配好了的空间*/
__STL_TRY {
/*
将原来的vector内容拷贝到当前vector：
*/
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish, __x); // 为新的元素设置初始值，添加到vector末尾
++__new_finish; // 调整水位
// 这里需要再次进行一次拷贝，是因为当前函数可能还会被insert(p,x)调用
// insert表示在第p个位置插入x元素，这个操作可能也会造成数组的扩容
// 所以需要将安插点之后的数据拷贝到当前位置
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
/*catch*/
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
/*销毁旧的存储空间，并更换三个指针为新的地址空间的指针*/
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
三、小结
到此我们就基本清楚了vector容器是根据 1.5倍 或 2倍 进行扩容的。
那么问题来了， 为什么当初创始人根据规定扩容的倍数为1.5或2，而不是等长（包括线性）增长或者以其他的倍数增长呢？
2. 为何不以等长方式进行扩容？
要回答这系列问题，离不开编写代码时最关注的两个概念—- 时间和空间。我们需要在这个矛盾体中找出一个平衡，得出一个最优解。
由之前分析可知： 当push_back()添加元素导致内存的重新分配时，会将原来空间中的元素拷贝移动到新内存中。
故push_back()总操作 包括了 插入元素操作 和 搬移元素操作 两部分。
当以等长方式进行push_back()：
公式推导得出等长增长的均摊复杂度为O(N)。
而以倍数方式进行push_back():
公式推导得出倍数增长的均摊复杂度为O(1)。
故以倍数的方式扩容比以等长个数的扩容方式效率高。
3. 那为什么选择1.5倍或者2倍方式扩容，而不是3倍、4倍甚至更大的倍数呢？
根据2.1的推导得出倍数增长的效率比等长增长效率高，那是不是任意的倍数都可行呢？答案是否定的。上述分析是从时间的复杂度上倍数增长效率高。而该问题就该从空间复杂度上来考虑。
当以2倍的方式扩容时：
1 –> 2 –> 4 –> 8 –> 16 – > ….
可以看到，每次扩容时，前面释放的空间都不能使用。比如：第4次扩容时，前2次空间已经释放，第3次空间还没有释放(开辟新空间、拷贝元素、释放旧空间)，即前面释放的空间只有1 + 2 = 3，假设第3次空间已经释放才只有1+2+4=7，而第四次需要8个空间，因此无法使用之前已释放的空间，但是按照小于2倍方式扩容，多次扩容之后就可以复用之前释放的空间了。
故如果倍数超过2倍(包含2倍)方式扩容会存在：
1.空间浪费可能会比较高，比如：扩容后申请了64个空间，但只存了33个元素，有接近一半的空间没有使用。
2.无法使用到前面已释放的内存。
而使用1.5倍（k=1.5)扩容时，在几次扩展以后，可以重用之前的内存空间了。同时 linux 下选择2倍扩容， windows 下的vs选择1.5倍扩容。
那么问题又来了，为什么在 linux 下要选择2倍扩容，上述分析不是1.5倍扩容的优势更多一些吗？
4. linux为什么选择2倍方式扩容？
这就要着手于各类操作系统的底层原理了。
4.1 windows下的1.5倍扩容原因。
Windows中堆管理系统会对释放的堆块进行合并,因此:vs下的vector扩容机制选择使用1.5倍的方式扩容,这样多次扩容之后,就可以使用之前已经释放的空间。
4.2 linux下的2倍扩容原因
—涉及到 linux 开辟空间的底层原理 见 linux 内存源码剖析专题。
在linux下开辟内存空间存在两种方式 ，通过malloc/free 库函数 或 new/delete 关键字，底层通过 brk() （ < 128 K ）或 mmap() （ > 128 K）的系统调用进入内核态，然后通过linux的伙伴系统为内核提供了一种用于分配一下连续的页而建立的一种高效的分配策略。
伙伴系统是将整个内存区域构建成基本大小basicSize的1倍、2倍、4倍、8倍、16倍等，即要求内存空间分区链均对应2的整次幂倍大小的空间，整齐划一，有规律的而不是乱糟糟的。在分配和释放空间时，可以通过log2(request/basicSize)向上取整的哈希算法快速找到对应内存块。
通过伙伴系统管理空闲分区的了解，可以看到在伙伴系统中的每条空闲分区链中挂的都是2i的页面大小，通过哈希思想进行空间分配与合并，非常高效。估计可能是这个原因SGI-STL选择以2倍方式进行扩容。
5. 再次剖析Vector的 push_back() 源码
上述通过对 vector 的 push_back() 分析 我们了解到 vector 是以 1.5倍或2倍进行扩容，但是在扩容的过程中运用到了哪些构造函数呢？
并且在对push_back()计算均摊复杂度的时候提到扩容会用到 插入元素操作 和 搬移元素操作，是否就是说 当没有发生内存扩容的时候，push_back()只调用了拷贝构造函数，而扩容后调用了 移动构造函数和拷贝函数呢？
预实验：
逐一添加自定义类型的对象，观察push_back()扩容与否对构造函数调用的结果。
#include <iostream>
using namespace std;
#include <vector>
class A {
public:
A() {
printf("A()--默认构造\n");
}
~A() {
printf("~A()--析构函数\n");
}
A(const A& a) {
printf("A(const A& a)--拷贝构造\n");
}
A(A&& a) noexcept{
printf("A(A&& a)--移动构造\n");
}
A& operator=(const A& a) {
printf("operator=(const A& a)--赋值构造\n");
return *this;
}
A& operator=(A&& a) {
printf("operator=(A&& a)--移动赋值构造\n");
return *this;
}
};
int main() {
std::vector<A> vec;
A a;
for (int i = 0; i < 14; ++i) {
cout << i+1 << endl;
vec.push_back(a);
cout <<" ---------" << endl;
}
system("pause");
return 0;
}
结果显示：
符合之前得出的windows下VS 1.5倍扩容规律。故得到结论：
在没有发生内存的重新分配的时，push_back()只调用了拷贝构造函数。
而发生内存的重新分配时，会将原先空间的元素 移动构造 到新内存中，并依次析构原来元素，在拷贝一个新元素。
这里需要注意的是： 移动构造函数转移了资源的所有权，但还是要析构原来的对象，防止不确定性发生。
我们翻开源码一一分析：发现C++11之前SGI的push_back只有构建临时对象和拷贝构造函数。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
