1、vector源码刨析
1.1、数据结构以及动态扩充算法
其实vector内部有三个指针，分别是数据的第一个元素Myfirst、数据的最后一个元素的下一个位置Mylast，最后一个空间的下一个位置Myend；当你插入数据的时候，先判断当前容量够不够，不够的话通过内存分配子扩充容量，至于扩充的算法，可能有些编译器不大相同，像vc6.0的话，就是成倍扩充，比如当前是2，扩充到4，4不够用了之后，又扩充到8，以此类推。但是像visual studio，就是按照容量的一半进行扩充。
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> v;
v.push_back(1);
cout << v.capacity() << endl;
v.push_back(1);
cout << v.capacity() << endl;
v.push_back(1);
cout << v.capacity() << endl;
v.push_back(1);
cout << v.capacity() << endl;
v.push_back(1);
cout << v.capacity() << endl;
v.push_back(1);
cout << v.capacity() << endl;
v.push_back(1);
cout << v.capacity() << endl;
v.push_back(1);
cout << v.capacity() << endl;
return 0;
}
//输出
1
2
4
4
8
8
8
81.2、如何实现连续空间
如果是从尾部插入，分配内存结束后，先在尾部的位置插入数据，然后再将之前的数据一个个复制过去。
如果是从中间插入，分配内存后，先在该位置插入数据，然后再将该位置的前面数据搬下来，然后将该位置的后面数据依次搬到该位置的后面。
1.3、内存分配子
先上代码
#include <vector>
#include <iostream>
using namespace std;
class Test
{
public:
Test()
{
cout << "Test() ..." << endl;
}
Test(const Test& other)
{
cout << "copy Test ..." << endl;
}
~Test()
{
cout << "~Test() ..." << endl;
}
};
int main() {
vector<Test> v;
Test t1;
Test t2;
Test t3;
v.push_back(t1);
v.push_back(t2);
v.push_back(t3);
return 0;
}
// 输出
Test() ...
Test() ...
Test() ...
copy Test ...
copy Test ...
copy Test ...
~Test() ...
copy Test ...
copy Test ...
copy Test ...
~Test() ...
~Test() ...
~Test() ...
~Test() ...
~Test() ...
~Test() ...
~Test() ...
~Test() ...
根据例子来分析分配内存的过程
前三行的构造：是定义了三个变量打印出来的；
v.push_back(t1)具体过程：
1、先是调用_Allocate函数。_Allocate里面会调用operator new分配新内存，然后算出偏移量，也就是要在哪插入数据
2、然后调用_Ufill函数将数据插入进去。_Ufill里面最终会调用placement new去调用拷贝构造函数将复制的数据插入新内存。(在这边就会打印出第四行的拷贝构造)
这边为什么不直接调用new operator直接开辟空间和调用拷贝构造？因为要算出偏移量，每一个类型的偏移量都不一样，所以必须先分配内存，然后再根据偏移量插入到新内存。
3、然后再调用_Move将该位置的前面数据搬到新空间当中去（因为这是第一个元素，所以没有前面数据）
4、然后再调用_Move将该位置的后面数据搬到新空间当中去（因为这是第一个元素，所以没有后面数据）
5、代码中这边还有需要显示调用析构函数和释放旧内存，因为这是第一块内存，而且构造出来的数据是要放在第一块内存中，所以这边没有调用析构和释放内存。
6、然后将三个指针改成相对应的位置。
v.push_back(t2)具体过程：
第五行的拷贝原理同第四行。
前两步跟上面一样；
3、调用_Move将该位置之前的数据遍历，遍历里面调用placement new，调用拷贝构造将数据拷贝到新内存中，因为这个t2前面只有一个t1，所以就只拷贝t1，所以打印出了第六行的拷贝构造函数。
4、同上
5、这边已经将数据都拷贝到新的内存当中了，所以需要释放旧的内存。最后面会显示的调用析构函数，打印出了第七行的析构函数。然后再调用operator delete释放上面operator new的内存。这边析构的是：旧内存中的数据，因为已经将旧内存中的数据拷贝到新内存中了，旧内存就没用了，此时旧内存有t1和t2，所以就只打印出两行析构。跟第一个push_back不同的是，第一个的时候没有旧数据，所以不需要删除和析构。
6、然后将三个指针改成相对应的位置。
v.push_back(t3)具体过程：
第八行的拷贝原理同第四行。
前两步跟上面一样；
3、调用_Move将该位置之前的数据遍历，遍历里面调用placement new，调用拷贝构造将数据拷贝到新内存中，因为这个t3前面有t1和t2，拷贝了两个，所以打印出了第九、十行的拷贝构造函数。
4、同上（注意，如果是在中间插入，那这边第四步调用的函数和第三步一样，只是参数不一样，里面都是遍历，然后拷贝）
5、这边已经将数据都拷贝到新的内存当中了，所以需要释放旧的内存。最后面会显示的调用析构函数，打印出了第十一、十二行的析构函数。然后再调用operator delete释放上面operator new的内存。这边析构的是：旧内存中的数据，因为已经将旧内存中的数据拷贝到新内存中了，旧内存就没用了，此时旧内存就只有一个t1，所以就只打印出一行析构。跟第一个push_back不同的是，第一个的时候没有旧数据，所以不需要删除和析构。
6、然后将三个指针改成相对应的位置。
剩下的6个析构函数，分别是t1t2t3生命周期结束的时候调用，还有v生命周期结束的时候也会去销毁里面的元素，所以v里面也有三个析构，这样加起来，就是上面代码输出的样子。
这边再复习一下new的三种用法：
new operator：分配空间+构造函数
opearator new：只分配空间，不调用构造函数
placement new：不分配空间，调用构造函数
