以下内容摘自http://blog.csdn.net/morewindows/article/details/6976468
priority_queue 优先级队列是一个拥有权值概念的单向队列queue,在这个队列中,所有元素是按优先级排列的(也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素优先权要高于后进入队列的元素)。在计算机操作系统中,优先级队列的使用是相当频繁的,进线程调度都会用到。在STL的具体实现中,priority_queue也是以别的容器作为底部结构,再根据堆的处理规则来调整元素之间的位置。下面给出priority_queue的函数列表和VS2008中priority_queue的源代码,本文中与heap有关的函数参见《STL系列之四 heap 堆》。

可以看出priority_queue的函数列表与栈stack的函数列表是相同的。
VS2008中priority_queue 优先级队列的源代码
友情提示:初次阅读时请注意其实现思想,不要在细节上浪费过多的时间
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
| template<class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type> > //默认以vector为容器的 class priority_queue { public: typedef _Container container_type; typedef typename _Container::value_type value_type; typedef typename _Container::size_type size_type; typedef typename _Container::reference reference; typedef typename _Container::const_reference const_reference; priority_queue() : c(), comp() { } explicit priority_queue(const _Pr& _Pred) : c(), comp(_Pred) { } priority_queue(const _Pr& _Pred, const _Container& _Cont) : c(_Cont), comp(_Pred) { make_heap(c.begin(), c.end(), comp); } template<class _Iter> priority_queue(_Iter _First, _Iter _Last) : c(_First, _Last), comp() { make_heap(c.begin(), c.end(), comp); } template<class _Iter> priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred) : c(_First, _Last), comp(_Pred) { make_heap(c.begin(), c.end(), comp); } template<class _Iter> priority_queue(_Iter _First, _Iter _Last, const _Pr& _Pred, const _Container& _Cont) : c(_Cont), comp(_Pred) { c.insert(c.end(), _First, _Last); make_heap(c.begin(), c.end(), comp); } bool empty() const { return (c.empty()); } size_type size() const { return (c.size()); } const_reference top() const { return (c.front()); } reference top() { return (c.front()); } void push(const value_type& _Pred) { c.push_back(_Pred); push_heap(c.begin(), c.end(), comp); } void pop() { pop_heap(c.begin(), c.end(), comp); c.pop_back(); } protected: _Container c; _Pr comp; };
|
下面先给出优级先级队列的使用范例。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
#include <queue> #include <list> #include <cstdio> using namespace std; int main() { priority_queue<int> a; priority_queue<int, list<int>> b; int i; for (i = 0; i < 10; i++) { a.push(i * 2 - 5); } printf("%d\n", a.size()); while (!a.empty()) { printf("%d ", a.top()); a.pop(); } putchar('\n'); return 0; }
|
下面程序是针对结构体的,对数据的比较是通过对结构体重载operator()。
程序功能是模拟排队过程,每人有姓名和优先级,优先级相同则比较姓名,开始有5个人进入队列,然后队头2个人出队,再有3个人进入队列,最后所有人都依次出队,程序会输出离开队伍的顺序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include <queue> #include <cstring> #include <cstdio> using namespace std;
struct Node { char szName[20]; int priority; Node(int nri, char *pszName) { strcpy(szName, pszName); priority = nri; } };
struct NodeCmp { bool operator()(const Node &na, const Node &nb) { if (na.priority != nb.priority) return na.priority <= nb.priority; else return strcmp(na.szName, nb.szName) > 0; } }; void PrintfNode(Node &na) { printf("%s %d\n", na.szName, na.priority); } int main() { priority_queue<Node, vector<Node>, NodeCmp> a; a.push(Node(5, "小谭")); a.push(Node(3, "小刘")); a.push(Node(1, "小涛")); a.push(Node(5, "小王")); PrintfNode(a.top()); a.pop(); PrintfNode(a.top()); a.pop(); printf("--------------------\n"); a.push(Node(2, "小白")); a.push(Node(2, "小强")); a.push(Node(3, "小新")); while (!a.empty()) { PrintfNode(a.top()); a.pop(); } return 0; }
|
简单来说,优先队列有如下使用方法
构建一个 内置类型 /具有operator < 的优先队列
priority_queue Queue;
其中Type必须有operator <, 否则将引起编译错误。另外,如果以成员函数重载operator <,需要注意this与传入相同的问题。友元重载就没有这个问题。
构建一个 自定义算法的 优先队列
priority_queue<Type,vector,TypeCmp> Queue;
其中vector是优先队列内部使用的容器,建议使用vector. TypeCmp是一个类(或结构体)重载()形成仿函数形式
struct TypeCmp
{
bool operator() (const Type& a,const Type& b);
};
如果TypeCmp()调用了Type的私有数据域,那么Type的定义中相应的应该加上friend TypeCmp;
(由于仿函数和lambda的相似性我又写了个lambda然而编译失败了….)
另外,优先队列的排序方法与实际结果正好是相反的,这一点需要注意。
文章转自: https://blog.csdn.net/Kiritow/article/details/51451574