ACM向：关于优先队列priority_queue自定义比较函数用法整理

心已赠人 2022-06-09 03:20 156阅读 0赞

关于优先队列priority\_queue自定义比较函数用法整理

原来上不了网，写在word里了，代码什么的直接贴过来了，有空整理成高亮的形式。

0.0、首先注意一点，priority\_queue没有front()方法，和一般的queue不一样，与这个方法对应的是top()

0.1默认的:

它的模板声明带有三个参数，priority\_queue<Type, Container, Functional> 
Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。 
Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list. 
       STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。

1、重载bool operator<，写在结构体外面

#include<queue>
 
 #include<iostream>
 
 using namespacestd;
 
 struct node
 
 {
 
 int x, y;
 
 node(int x=0, int y=0):x(x),y(y){}
 
 };
 
 booloperator<(node a, node b)
 
 {
 
 if(a.x > b.x) return 1;
 
 else if(a.x == b.x)
 
 if(a.y >= b.y) return 1;
 
 return 0;
 
 }
 
 int main()
 
 {
 
 priority_queue<node> pq; 
 
 pq.push(node(1,2)); pq.push(node(2,2));
 
 pq.push(node(2,3)); pq.push(node(3,3));
 
 pq.push(node(3,4)); pq.push(node(4,4));
 
 pq.push(node(4,5)); pq.push(node(5,5));
 
 while(!pq.empty())
 
 {
 
 cout<<pq.top().x<<pq.top().y<<endl;
 
 pq.pop();
 
 }
 
 return 0;
 
 }

或者写成 const node &a

bool operator < (const node &a,const node &b)
 
 {
 
 if(a.x > b.x) return 1;
 
 else if(a.x == b.x)
 
 if(a.y >= b.y) return 1;
 
 return 0;
 
 }

或者写成 const node a

bool operator < (const node a,const node b)
 
 {
 
 if(a.x > b.x) return 1;
 
 else if(a.x == b.x)
 
 if(a.y >= b.y) return 1;
 
 return 0;
 
 }

但是这样不行 node &a

bool operator < (node &a, node &b)
 
 {
 
 if(a.x > b.x) return 1;
 
 else if(a.x == b.x)
 
 if(a.y >= b.y) return 1;
 
 return 0;
 
 }

2、重载bool operator<，写在结构体里面

要是直接写在里面就只需要一个参数，但是后面必须加const修饰，否则报错，如：bool operator < (const node &b) **const**

同样const node &a和node a都可以，但node &a不可以

#include<queue>
 
 #include<iostream>
 
 using namespacestd;
 
 struct node
 
 {
 
 int x, y;
 
 node(int x=0, int y=0):x(x),y(y){}
 
 bool operator<(const node &b) const
 
 {
 
 if(x > b.x) return 1;
 
 else if(x == b.x)
 
 if(y >= b.y) return 1;
 
 return 0;
 
 }
 
 };
 
 
 int main()
 
 {
 
 priority_queue<node> pq; 
 
 pq.push(node(1,2)); pq.push(node(2,2));
 
 pq.push(node(2,3)); pq.push(node(3,3));
 
 pq.push(node(3,4)); pq.push(node(4,4));
 
 pq.push(node(4,5)); pq.push(node(5,5));
 
 while(!pq.empty())
 
 {
 
 cout<<pq.top().x<<pq.top().y<<endl;
 
 pq.pop();
 
 }
 
 return 0;
 
 }

友元必须要写在里面，且是两个参数，同样node &a不可以，const node &a和node a都可以，但是无需const在函数最后修饰，否则报错

struct node
 
 {
 
 int x, y;
 
 node(int x=0, int y=0):x(x),y(y){}
 
 friend bool operator<(const node&a, const node &b)
 
 {
 
 if(a.x > b.x) return 1;
 
 else if(a.x == b.x)
 
 if(a.y >= b.y) return 1;
 
 return 0;
 
 }
 
 };

3、可以自定义一个比较类，Compare

priority\_queue中的三个参数，后两个可以省去，因为有默认参数，不过如果，**有第三个参数的话，必定要写第二个参数。**

而且这个是一个类，这个类里重载operator()，和自定义sort排序不同，sort只需bool cmp（……）（当然sort也可以弄一个比较类，再重载operator()）,若是priority\_queue中写为sort的cmp形式则报错，如：bool cmp1(const node &a, const node&b)//报错！

#include <queue>
 
 #include <iostream>
 
 using namespace std;
 
 struct node
 
 {
 
 int x, y;
 
 node(intx=0, int y=0):x(x),y(y){}
 
 };
 
 struct cmp
 
 {
 
 booloperator()(const node &a, const node &b)
 
 {
 
 if(a.x> b.x) return 1;
 
 elseif(a.x == b.x)
 
 if(a.y>= b.y) return 1;
 
 return0;
 
 }
 
 };
 
 int main()
 
 {
 
 priority_queue<node,vector<node>, cmp> pq; //注意这里的写法
 
 pq.push(node(1,2)); pq.push(node(2,2));
 
 pq.push(node(2,3)); pq.push(node(3,3));
 
 pq.push(node(3,4)); pq.push(node(4,4));
 
 pq.push(node(4,5)); pq.push(node(5,5));
 
 while(!pq.empty())
 
 {
 
 cout<<pq.top().x<<pq.top().y<<endl;
 
 pq.pop();
 
 }
 
 return0;
 
 }

值得注意的是，这个比较类里node&a，const node &a和node a都可以了，重载bool operator() 最后加const修饰也可以。

最后忘写了，上面所有程序排序结果都为

请按任意键继续. . .

补充：STL中sort、priority\_queue、map、set的自定义比较函数

STL中，sort的默认排序为less，也就是说从小到大排序；priority\_queue默认是less，也就说大顶堆；map默认是less，也就说用迭代器迭代的时候默认是小的排在前面；set默认是less，也就是说用迭代器迭代的时候是从小到大排序的。

1、sort

#include <stdio.h> 
 
 #include <algorithm> 
 
 #include <functional> 
 
 using namespacestd; 
 
 
 bool comp(constint& a, const int& b ){ 
 
 return a < b ; //从小到大 
 
 } 
 
 struct cmp{ 
 
 bool operator()( const int& a , constint& b ) const{ 
 
 return a ()排序 
 
 sort( array , array+6 ,greater<int>() ) ; //从大到小排序 
 
 sort( array , array+6 , comp ) ; 
 
 sort( array , array+6 , cmp() ) ; 
 
 for(int i=0;i<6;++i) printf("%d ",array[i]);printf("\n"); 
 
 return 0 ; 
 
 }

2、priority\_queue

#include<stdio.h> 
 
 #include<queue> 
 
 using namespacestd ; 
 
 
 struct cmp{ 
 
 bool operator()( const int& a , constint& b )const{ 
 
 return a < b ; //大顶堆 
 
 } 
 
 }; 
 
 struct Node{ 
 
 int x, y ; 
 
 Node(int _x, int _y ):x(_x),y(_y){} 
 
 bool operator <(const Node&n1)const{ 
 
 if( x < n1.x ) return true ; //按照x为第一关键字由大到小排序 
 
 else if( x == n1.x ) return y < n1.y ; //y为第二关键字由大到小排序 
 
 else return false ; 
 
 } 
 
 } ; 
 
 
 int main(){ 
 
 //priority_queue<int> q ; //优先队列默认是less，大顶堆； 
 
 //priority_queue<int,vector<int>,cmp> q ; 
 
 priority_queue< Node > q ; 
 
 
 for(int i=0;i<10;i++) q.push( Node( rand() , rand() ) ); 
 
 while( !q.empty() ){ 
 
 printf("%d %d\n",q.top().x ,q.top().y ) ; 
 
 q.pop() ; 
 
 } 
 
 return 0 ; 
 
 }

3、map

#include<stdio.h> 
 
 #include<map> 
 
 using namespacestd; 
 
 
 struct cmp{ 
 
 bool operator()( const int& a, constint& b ) const{ 
 
 return a >mp ; //从大到小 
 
 map<int , int ,cmp> mp ; 
 
 for(int i=0;i<10;++i) mp.insert( map<int,int,cmp>::value_type(rand() ,i) ) ; 
 
 map<int, int, cmp >::iterator it =mp.begin() ; 
 
 for( ;it!=mp.end() ;it++) printf("%d %d\n",(*it).first ,(*it).second ); 
 
 return 0 ; 
 
 }

4、set

#include<stdio.h> 
 
 #include<iostream> 
 
 #include<algorithm> 
 
 #include<set> 
 
 
 using namespacestd; 
 
 
 struct cmp{ 
 
 bool operator()( const int& a , constint& b )const{ 
 
 return a s ; 
 
 set<int,cmp> s ; 
 
 for(int i=0;i<10;i++) s.insert( rand() ) ; 
 
 set<int,cmp>::iterator it = s.begin(); 
 
 for( ; it!=s.end();it++) 
 
 printf("%d\n",*it); 
 
 return 0 ; 
 
 }

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

<table style="width:668px;"> 
 <tbody> 
 <tr> 
 <td colspan="2"> priority_queue函数列表 </td> 
 </tr> 
 <tr> 
 <td> 函数 </td> 
 <td> 描述&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;by&nbsp;MoreWindows(&nbsp;<a href="http://blog.csdn.net/MoreWindows" rel="nofollow">http://blog.csdn.net/MoreWindows</a>&nbsp;) </td> 
 </tr> 
 <tr> 
 <td> 构造析构 </td> 
 </tr> 
 <tr> 
 <td> priority_queue &lt;Elem&gt; c </td> 
 <td> &nbsp;创建一个空的queue 。 注：priority_queue构造函数有7个版本，请查阅MSDN </td> 
 </tr> 
 <tr> 
 <td> 数据访问与增减 </td> 
 </tr> 
 <tr> 
 <td> c.top() </td> 
 <td> 返回队列头部数据 </td> 
 </tr> 
 <tr> 
 <td> c.push(elem) </td> 
 <td> 在队列尾部增加elem数据 </td> 
 </tr> 
 <tr> 
 <td> &nbsp;c.pop() </td> 
 <td> 队列头部数据出队 </td> 
 </tr> 
 <tr> 
 <td> 其它操作 </td> 
 </tr> 
 <tr> 
 <td> c.empty() </td> 
 <td> 判断队列是否为空 </td> 
 </tr> 
 <tr> 
 <td> c.size() </td> 
 <td> 返回队列中数据的个数 </td> 
 </tr> 
 <tr> 
 <td> &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

可以看出priority\_queue的函数列表与栈[stack][]的函数列表是相同的。

VS2008中priority\_queue 优先级队列的源代码

友情提示：初次阅读时请注意其实现思想，不要在细节上浪费过多的时间

//VS2008中 priority_queue的定义 MoreWindows整理( http://blog.csdn.net/MoreWindows ) 
 
 template<class_Ty, class _Container = vector<_Ty>, class _Pr = less<typename_Container::value_type> > //默认以vector为容器的 
 
 class priority_queue 
 
 { // priority queue implemented with a_Container 
 
 public: 
 
 typedef _Container container_type; 
 
 typedef typename _Container::value_typevalue_type; 
 
 typedef typename _Container::size_typesize_type; 
 
 typedef typename _Container::referencereference; 
 
 typedef typename_Container::const_reference const_reference; 
 
 
 priority_queue() : c(), comp() 
 
 { // construct with empty container, default comparator 
 
 } 
 
 
 explicit priority_queue(const _Pr&_Pred) : c(), comp(_Pred) 
 
 { // construct with empty container, specified comparator 
 
 } 
 
 
 priority_queue(const _Pr& _Pred, const_Container& _Cont) : c(_Cont), comp(_Pred) 
 
 { // construct by copying specified container, comparator 
 
 make_heap(c.begin(), c.end(), comp); //参见《STL系列之四 heap 堆的相关函数》 
 
 } 
 
 
 template<class _Iter> 
 
 priority_queue(_Iter _First, _Iter _Last) :c(_First, _Last), comp() 
 
 { // construct by copying [_First, _Last), default comparator 
 
 make_heap(c.begin(), c.end(),comp); 
 
 } 
 
 
 template<class _Iter> 
 
 priority_queue(_Iter _First, _Iter _Last,const _Pr& _Pred) : c(_First, _Last), comp(_Pred) 
 
 { // construct by copying [_First, _Last), specified comparator 
 
 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) 
 
 { // construct by copying [_First, _Last), container, and comparator 
 
 c.insert(c.end(), _First, _Last); 
 
 make_heap(c.begin(), c.end(),comp); 
 
 } 
 
 
 bool empty() const 
 
 { // test if queue is empty 
 
 return (c.empty()); 
 
 } 
 
 
 size_type size() const 
 
 { //return length of queue 
 
 return (c.size()); 
 
 } 
 
 
 const_reference top() const 
 
 { // return highest-priority element 
 
 return (c.front()); 
 
 } 
 
 
 reference top() 
 
 { // return mutable highest-priority element (retained) 
 
 return (c.front()); 
 
 } 
 
 
 void push(const value_type& _Pred) 
 
 { // insert value in priority order 
 
 c.push_back(_Pred); 
 
 push_heap(c.begin(), c.end(),comp); 
 
 } 
 
 
 void pop() 
 
 { // erase highest-priority element 
 
 pop_heap(c.begin(), c.end(),comp); 
 
 c.pop_back(); 
 
 } 
 
 
 protected: 
 
 _Container c; // the underlying container 
 
 _Pr comp; // the comparator functor 
 
 };

[stack]: http://blog.csdn.net/morewindows/article/details/6950881