STL容器deque，以及优先级队列 priority_queue。

deque

deque是双向开口的连续线性空间。

deque允许使用常数项时间对两端进行元素的插入和删除操作。

deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来

实现原理

deque是一段段定量的连续空间构成的。一旦有必要在deque的前端或者后端增加空间，便会配置一段连续定量的空间，串接在deque的头端或者尾端。

deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。

相关函数

//deque构造函数
deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将n个elem拷贝给本身。
deque(const deque &deq);//拷贝构造函数。

//deque赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符 
swap(deq);// 将deq与本身的元素互换

//deque大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果容器变短，则末尾超出容器长度的元素被删除。

//deque双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据

//deque数据存取
at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据

//deque插入操作
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。

//deque删除操作
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。

vector与deque的比较

1. vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置 却是不固定的。
2. 如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
3. deque支持头部的快速插入与快速移除，这是deque的优点。

不过操作上，两者的操作大致相同，deque比vector多一些在头部插入的算法，且deque没有容量capacity的概念。

优先级队列

• priority_queue
• 具体API与queue的相同！
• 底层采用的堆排序的算法，默认大根堆！，top元素是最大值

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct stu {
	int id;
	string name;
	stu(int tid, string tname) {
		id = tid;
		name = tname;
	}
	bool operator<(const stu & other) const {//重载比较运算符，改变优先级队列的排序规则
		return id > other.id;
	}
};

int main() {

	//构造优先级队列
	priority_queue<int> que;

	que.push(3);
	que.push(1);
	que.push(5);
	que.push(2);
	que.push(4);

	while (!que.empty()) {
		cout << que.top() << " ";//5 4 3 2 1
		que.pop();
	}
	cout << endl;

	priority_queue<int,vector<int>,greater<int>> que1;//指定排序方式

	que1.push(3);
	que1.push(1);
	que1.push(5);
	que1.push(2);
	que1.push(4);

	while (!que1.empty()) {
		cout << que1.top() << " ";//1 2 3 4 5
		que1.pop();
	}
	cout << endl;

	stu st[5] = { stu(1,"cc"),stu(3,"bb"),stu(5,"aa"),stu(4,"dd"),stu(2,"ee") };
	priority_queue<stu> stque{st,st+5};

	while (!stque.empty()) {
		cout << stque.top().id << "-" << stque.top().name << endl;
		stque.pop();
	}
	/*
	1-cc
	2-ee
	3-bb
	4-dd
	5-aa
	*/
	return 0;
}

参考连接：http://c.biancheng.net/view/480.html