One 、deque Basic concept of container

1. function ： Double ended array , You can insert and delete the header
2. And vector The difference between ：
   • vector For the insertion and deletion of the head, the efficiency is low , More data , The less efficient
   • deque Relatively speaking , The insertion and deletion of the head is faster than vector fast
   • vector Accessing elements will be faster than deque fast , This has to do with the internal implementation of both
3. picture ：
4.   working principle ：
5. characteristic ：vector Container iterators are iterators that support random access ( Skip access ).

Two 、deque Constructors

• deque<T>  deqT;                                // Default structure
• deque(beg,  end);                       // The constructor will （beg,end） The elements in the interval are copied to themselves
• deque(n,  elem);                         // The constructor will n individual elem Copy to yourself
• deque(const  deque  & deq);         // copy constructor  

#include<iostream>
#include<deque>
using namespace std;
void print_Deque(deque<int>&d)
{
	for(deque<int>::const_iterator it = d.begin();it!=d.end();it++) //  Set the function to read only 
    {
		cout<<*it<<" ";
	}
	cout<<endl;
}
	int main()

	//  Default structure , No arguments structure 
	deque<int> d1;
	for(int i=0;i<10;i++)
	{
		d1.push_back(i);
	}
	print_Deque(d1);

	//  Interval assignment 
	deque<int>d2(d1.begin(),d1.end());
	print_Deque(d2);
	
	// n individual elem
    deque<int> d3(10,100);
	print_Deque(d3);
	
	//  Copy structure 
	deque<int> d4(d3);
	print_Deque(d4);
	return 0;
}

  3、 ... and 、deque Assignment operation

• deque  &  operator=(const  deque  & deq);     // Overload the equal sign operator
• assign(beg,  end);                                  // take （beg,end） The copy of the data in the interval is assigned to itself
• assign(n,  elem);                                                // take n individual elem Copy assignment to itself

#include<iostream>
#include<deque>
using namespace std;
void print_Deque(deque<int>&d)
{
	for(deque<int>::const_iterator it = d.begin();it!=d.end();it++) //  Set the function to read only 
	{
		cout<<*it<<" ";
	}
	cout<<endl;
}
int main()
{
	deque<int> d1;
	for(int i=0;i<10;i++)
	{
		d1.push_back(i);
	}
    print_Deque(d1);
	
	//  Equal sign assignment 
	deque<int> d2;
	d2 = d1;
    print_Deque(d2);
		
	// assign  Interval assignment 
	deque<int> d3;
	d3.assign(d1.begin(),d1.end());
	print_Deque(d3);

	// assign n individual elem assignment 
	deque<int> d4;
	d4.assign(10,100);
    print_Deque(d4);
	return 0;
}

  Four 、deque Size operation

• deque.empty();                          // Judge whether the container is empty
• deque.size();                              // Returns the number of elements in the container
• deque.resize();                  // Reassign the container length to num, If the container becomes longer , Then fill with the default value of zero

                                                  // If the container gets shorter , Then the element beyond the length of the container at the end is deleted

• deque.resize(num  ,elem);         // Reassign the container length to num, If the container becomes longer , with elem Value to fill the new position

                                                  // If the container gets shorter , Then the element beyond the length of the container at the end is deleted

#include<iostream>
#include<deque>
using namespace std;
void print_Deque(deque<int>&d)
{
	for(deque<int>::const_iterator it = d.begin();it!=d.end();it++) //  Set the function to read only 
	{
		cout<<*it<<" ";
	}
	cout<<endl;
}
int main()
{
	deque<int> d1;
	for(int i=0;i<10;i++)
	{
		d1.push_back(i);
	}
	print_Deque(d1);
	
	cout<<" Judge whether the container is empty ：( Empty return 1, Not empty return 0) "<<d1.empty()<<endl;
	cout<<"deque Size of container ："<<d1.size()<<endl;
	
	//  Reset size 
	d1.resize(20);
	print_Deque(d1);//  The default is 0 Fill in excess positions 
	d1.resize(6);  //  The excess part is deleted 
	print_Deque(d1);
	
	//  Overload version 
	d1.resize(20,5);//  The empty part is used 5 fill 
	print_Deque(d1);
	return 0;
}

  5、 ... and 、deque Insert and delete

1. Two end insertion operation ：

• push_back(elem);                    // Add a data at the end of the container
• push_front(elem);                    // Insert a data in the head of the container
• pop_back();                              // Delete the last data in the container
• pop_front();                              // Delete the first data of the container

2. Specified location operation ：

• insert(pos,  elem);               // stay pos Insert a elem Copies of elements , Returns the location of the new element
• insert(pos,  n,  elem);          // stay pos Position insert n individual elem data , No return value
• insert(pos,  beg,  end);        // stay pos Position insert (beg,end) Interval data , No return value
• erase(beg,  end);                 // Delete （beg,end） Data in the interval , Return to the next data location
• erase(pos);                          // Delete pos Location data , Return to the next data location
• clear();                                  // Empty all data in the container

#include<iostream>
#include<deque>
using namespace std;
void print_Deque(deque<int>&d)
{
	for(deque<int>::const_iterator it = d.begin();it!=d.end();it++) //  Set the function to read only 
	{
		cout<<*it<<" ";
	}
	cout<<endl;
}
int main()
{
	deque<int> d1;
	for(int i=0;i<10;i++)
	{
		d1.push_back(i);
	}
	print_Deque(d1);
	
	//  Head insertion , Tail insertion 
	d1.push_back(10);
	d1.push_front(20);
	print_Deque(d1);
	d1.pop_back();
	d1.pop_front();
	print_Deque(d1);
	
	//  Insert 
	d1.insert(d1.begin(),1000);//  The first parameter is the iterator 
	print_Deque(d1);
	//  Overload version 
	d1.insert(d1.begin(),2,2000);//  Insert n individual elem
	print_Deque(d1);
	
	//  Insert interval 
	deque<int> d2;
	for(int i=0;i<10;i++)
	{
		d2.push_back(10+i);
	}
	print_Deque(d2);
	d1.insert(d1.end(),d2.begin(),d2.end());
	print_Deque(d1);
	
	//  Delete 
	d1.erase(d1.begin());
	print_Deque(d1);
	//  Delete by section 
	d1.erase(d2.begin(),d2.end());
	print_Deque(d1);
	
	//  Empty 
	d1.clear();
	print_Deque(d1);
	return 0;
}

  6、 ... and 、deque Data access

• at(int  idx);             // Returns the index idx The data
• operator[];             // Returns the index idx The data
• front();                   // Returns the first data in the container
• back();                   // Returns the last element of the container

#include<iostream>
#include<deque>
using namespace std;
int main()
{
	deque<int> d1;
	for(int i=0;i<10;i++)
	{
		d1.push_back(i);
	}
	
	for(int i=0;i<d1.size();i++)
	{
		cout<<d1[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<d1.size();i++)
	{
		cout<<d1.at(i)<<" ";
	}
	cout<<endl;
	
	//  Return header and footer data 
	cout<<" The first data :"<<d1.front()<<endl;
	cout<<" The last data :"<<d1.back()<<endl;
	return 0;
}

  7、 ... and 、deque Sort

• sort(iterator  beg ,iterator  end);      // Yes beg and end Sort the elements in the interval

For containers that support random access iterators , All available sort The algorithm sorts them directly

 vector Containers can also be used sort Sort

#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
void print_Deque(const deque<int>&d)
{
	for(deque<int>::const_iterator it = d.begin();it!=d.end();it++)
	{
		cout<<*it<<" ";
	}
	cout<<endl;
}
int main()
{
	deque<int> d1;
    d1.push_back(2);
	d1.push_back(7);
	d1.push_back(9);
	d1.push_back(2);
	d1.push_back(5);
	print_Deque(d1);
	sort(d1.begin(),d1.end()); //  The default is ascending 
	print_Deque(d1);
	return 0;
}