19.03 容器的说明和简单应用例续

一：deque和stack：顺序容器

<1>deque：双端队列 double-enden queue（双向开口）。相当于动态数组，头部和尾部插入与删除数据都很快。

#include <deque>
#include <iostream>

using namespace std;

class A
{
public:
	A(int tmpv) :m_i(tmpv)  //构造函数
	{
		cout << "A::A()构造函数执行" << endl;
	}
	A(const A& tmpA) :m_i(tmpA.m_i)
	{
		cout << "A::A()的拷贝构造函数执行" << endl;
	}

	~A()
	{
		cout << "A::~A()的析构函数执行" << endl;
	}
public:
	int m_i;
};

void func()
{
	deque<A>mydeque;
	for (int i = 0; i < 5; i++)
	{
		cout << "----------begin1------------" << endl;
		mydeque.push_front(A(i));
		cout << "----------end1--------------" << endl;

	}
	for (int i = 0; i < 5; i++)
	{
		cout << "----------begin2------------" << endl;
		mydeque.push_back(A(i));
		cout << "----------end2--------------" << endl;

	}

	for (int i = 0; i < mydeque.size(); i++)
	{
		cout << "下标为i = " << i << " 的值为 " << mydeque[i].m_i << endl;
		//输出地址
		printf("每个元素的地址为: %p\n", &mydeque[i]);
	}
}

int main()
{
	func();
	return 0;
}

总结：内部是使用分段数组的方式存储，分段连续内存。

<2>stack（堆栈/栈）：后进先出，只有一个开口，只要把deque左边开口封死，我们就可以认为变成了一个stack。

和vector的区别：vector支持从中间插入中间删除，虽然效率不算高。
stack只支持从栈顶放入元素以及从栈顶取出（删除）元素。这种特性是stack容器设计初衷。
deque实际上是包含着stack功能。

二：queue

queue：队列。这是个普通队列：先进先出，比较基本的数据结构；
deque也包含这queue功能。

三：list

双向链表，不需要各个元素之间的内存连在一起；查找效率不突出，在任意位置插入和删除元素非常迅速。
面试中，vector和list区别：
<1>vector类似于数组，它的内存空间是连续的；list双向链表，内存空间并不连续（至少不要求内存空间是连续的）。
<2>vector从中间或者开头插入元素效率比较低，但是list插入元素效率非常高。
<3>vector当内存不够时，会重新找一块内存，对原来内存对象做析构，在新找的内存中重新构建对象。
<4>vector能够高效的随机存取，而list做不到这一点，比如要访问第五个元素。vector内存连续，一下就能定位到第五个元素。list找到第五个元素，要沿着一个链一直找下去，直到找到第五个元素，所以vector随机存取比较快，而list随机存取比较慢。

四：其他