STL Priority Queue

STL Priority Queue

包含头文件<queue>

定义：

namespace std {
	template <	typename T,
			typename Container = vector<T>,
			typename Compare = less<typename Container::value_type> >
	class priority_queue;
}

内部Container默认用vector实现。内部比较标准是<。
可以用其他提供random-access iterator和front(), push_back(), pop_back()的顺序容器。随机存取迭代器时为了给元素排序，用的是STL的heap算法。也可以用deque来实现。
如果要定义自己的比较标准，应该传入一个二元运算的函数/函数对象/lambda用于比较两个元素。
如：std::priority_queue<float, std::vector<float>, std::greater<float> > pbuffer;

The Core Interface

• push() inserts an element into the priority queue.
• top() returns the next element in the priority queue.
• pop() removes an element from the priority queue.
• size()/empty()

Example of Using Priority Queues

#include <iostream>
#include <queue>
using namespace std;
int main(){

	priority_queue<float> q;
	// insert three elements into the priority queue
	q.push(66.6f);
	q.push(22.2f);
	q.push(44.4f);
	// read and print two elements
	cout << q.top() << ' ';
	q.pop();
	cout << q.top() << endl;
	q.pop();
	// insert three more elements
	q.push(11.1f);
	q.push(55.5f);
	q.push(33.3f);
	// skip one element
	q.pop();
	// pop and print remaining elements
	while (!q.empty())
	{
		cout << q.top() << ' ';
		q.pop();
	}
	cout << endl;
	system("Pause");
}

[1] The C++ Standard Library 2nd Edition