1.Vector内存分配原理解析

vector是动态数组，在堆中分配内存，元素是连续存放的，

即使减少了大小以后，内存也不会释放，

通常情况下不会移动内存，只有在保留内存不够的时候，才会对中间和开始处的元素进行移动

是单端开口容器，无push_front，只有push_back

示例代码：

#include <vector>
#include <iostream>
using namespace std;

int main()
{
	vector<int> myvec(2,5);
	myvec.push_back(1);
	myvec.push_back(2);
	myvec.push_back(3);
	for (size_t i = 0; i < myvec.size(); i++)
	{
		cout << myvec[i] << endl;
	}
}

内存分析：

执行vector<int> myvec(2,5);后

5

5

 

 

执行myvec.push_back(1);后（并且发生了元素移动）

5

5

1

 

 

执行myvec.push_back(2);后

5

5

1

2

 

 

执行myvec.push_back(2);后（并且发生了元素移动）

5

5

1

2

3

 

 

结论：对于vector增加新元素的时候，有可能很快完成，也有可能要进行扩容，效率下降：

          删除末尾元素效率很高，删除中间元素效率低

2.deque内存分配原理解析

deque可以随机存取元素（用索引直接存取）

头部和尾部添加或移除元素都比较快速，但是在中部安插元素比较费时

是双端开口容器，既有push_front，也有push_back

内存分配流程对比：

vector的内存分配流程：

建立空间——》填充数据——》重建更大的空间——》复制原空间的内容——》删除原空间——》添加新数据

vector是一块独立的连续存放的内存空间

deque的内存分配流程：

建立空间——》填充数据——》建立新空间——》填充新数据

deque相比vector少了原空间的复制和删除，是由多个分段连续的内存空间组成

示例代码演示：

#include <vector>
#include <deque>
#include <iostream>
using namespace std;

int main()
{
	vector<int> v(2);//建立一个进行值初始化的长度为2的vector,即此时v[0]=0;v[1]=0;
	cout << "v[0] = " << v[0] << endl;
	v[0] = 10;
	int *p = &v[0]; //移动前的内存空间
	cout << "vector在尾部安插数据前：*p = " << *p << "，v[0]的地址为：" << p << endl;
	v.push_back(20);//扩容：建立更大（原来的2倍）的空间，移动元素到新的空间，并在新的空间添加20，释放原来的空间
	p = &v[0];
	cout << "vector在尾部安插数据后：*p = " << *p << "，v[0]的地址为：" << p << endl;


	deque<int> d(2);//建立一个进行值初始化的长度为2的vector,即此时v[0]=0;v[1]=0;
	cout << "d[0] = " << d[0] << endl;
	d[0] = 10;
	int *q = &d[0]; 
	cout << "deque在尾部安插数据前：*q = " << *q <<"，d[0]的地址为："<< q << endl;
	v.push_back(20);//扩容：建立一个空间，添加20，原来的空间保持不变
	q = &d[0];
	cout << "deque在尾部安插数据后：*q = " << *q <<"，d[0]的地址为："<< q << endl;
}

运行结果：

分析：

可以发现在vector和deque尾部添加元素后，vector的第一个元素的内存位置发生了变化，而deque的内存位置没有变化，因为vector将原来的元素移动到了新的空间，而deque并没有发生内存移动，只是在添加新的空间