19.03 vessel description and simple application examples continued

One ：deque and stack： Sequence containers

<1>deque： deque double-enden queue（ Two way opening ）. It's like a dynamic array , Both the header and the tail insert and delete data very quickly .

#include <deque>
#include <iostream>

using namespace std;

class A
{
public:
	A(int tmpv) :m_i(tmpv)  // Constructors 
	{
		cout << "A::A() Constructor execution " << endl;
	}
	A(const A& tmpA) :m_i(tmpA.m_i)
	{
		cout << "A::A() Copy constructor execution for " << endl;
	}

	~A()
	{
		cout << "A::~A() The destructor of " << 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 << " Subscript to be i = " << i << "  The value of is  " << mydeque[i].m_i << endl;
		// Output address 
		printf(" The address of each element is : %p\n", &mydeque[i]);
	}
}

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

summary ： Internally, it uses a segmented array to store , Segmented continuous memory .

<2>stack（ Stack / Stack ）： Last in, first out , There is only one opening , Just put deque The left opening is sealed , We can think of it as a stack.

and vector The difference between ：vector Supports inserting and deleting from the middle , Although the efficiency is not high .
stack It only supports putting elements from the top of the stack and taking them out from the top of the stack （ Delete ） Elements . This characteristic is stack The original intention of the container design .
deque It actually contains stack function .

Two ：queue

queue： queue . This is a normal queue ： fifo , Compare basic data structures ;
deque Also includes this queue function .

3、 ... and ：list

Double linked list , There is no need to connect the memory between the elements ; Search efficiency is not outstanding , Inserting and deleting elements anywhere is very fast .
During the interview ,vector and list difference ：
<1>vector It's like an array , Its memory space is continuous ;list Double linked list , Memory space is not continuous （ At least memory space is not required to be continuous ）.
<2>vector Inserting elements from the middle or the beginning is inefficient , however list Inserting elements is very efficient .
<3>vector When there is not enough memory , Will find a new piece of memory , Destruct the original memory object , Rebuild the object in the newly found memory .
<4>vector Efficient random access , and list You can't do that , For example, to access the fifth element .vector Memory is continuous , You can navigate to the fifth element at a glance .list Find the fifth element , To follow a chain all the way down , Until you find the fifth element , therefore vector Random access is faster , and list Random access is slow .

Four ： other