顺序性容器之双端队列deque

一、deque简介

双端队列deque是一种优化了的、可以高效地对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块。向deque两端添加或删除元素的开销很小。它不需要重新分配空间，所以向末端增加元素比vector更有效。

实际上，deque是对vector和list优缺点的结合，它是处于两者之间的一种容器。

deque的特点：

1. 随机访问方便，即支持[ ]操作符和vector.at() ，但性能没有vector好；
2. 可以在内部进行插入和删除操作，但性能不及list；
3. 可以在两端进行高效率插入和删除。

二、vector、deque、list三者比较

vector是一段连续的内存块；而deque是多个连续的内存块；list是所有数据元素分开保存，可能任何两个元素在内存中都不连续。

1. vector的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。
2. list是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。
3. deque兼顾vector和list的优点，它是分块的链表和多个数组的联合。所以它有比list好的查询性能，有比vector好的插入、删除性能。如果需要随机存取又关心两端数据的插入和删除，那么deque是最佳之选。

三、deque基本用法

使用deque需要引入deque头文件#include<deque>。deque的用法和vector几乎完全相同，两者使用方面的区别主要有以下两点：

1. vector有容量的概念（注意容量和元素的数量不是同一个概念），对应的有capacity()和reverse()两个与容量相关的成员函数；deque没有容量的概念，也就没有这两个成员函数；
2. deque可以高效地在两端插入、删除元素，vector只能高效地在末尾追加元素和删除末尾的元素，所以deque相比较vector多出了push_front()和pop_front()两个在头部插入、删除元素的成员函数。

#include<iostream>
#include<deque>
using namespace std;
int main()
{	
	deque<int> d;			//初始化一个元素类型为int的空deque
	cout<<d.size()<<endl;	//d是空的，输出元素数量，结果为0 
	
	d.push_back(12);		 //向d末尾增加元素 
	cout<<d[0]<<endl;		//访问d中的第0个元素，就像数组那样用下标访问 
	d.push_front(9);		 //向d头部增加元素 
	cout<<d[0]<<endl;		//访问d中的第0个元素
	d.push_back(23);		 //再向d末尾增加元素 
	cout<<d[1]<<endl;
	cout<<d.at(d.size()-1)<<endl;   //使用at获取元素
	
	d.pop_back();			 //pop_back()删除d尾部的元素
	d.pop_front();			//pop_front()删除d头部的元素
	cout<<d.size()<<endl;
	
	d.push_back(34);
	d.push_back(45);
	
	//遍历deque 
	for(size_t i = 0;i<d.size();i++){
		cout<<d[i]<<" ";
	}
	cout<<endl;
	
	//迭代器遍历deque 
	for(auto it=d.begin();it!=d.end();it++) cout<<*it<<" ";
	cout<<endl;
	
	//反向迭代器反向遍历deque 
	for(auto rit=d.rbegin();rit!=d.rend();rit++) cout<<*rit<<" ";
	cout<<endl;
	
	d.clear();				//清空d 
	cout<<d.size()<<endl;
	if(d.empty()) cout<<"none."<<endl;
	return 0;
}