优先队列priority_queue、仿函数

优先队列如果要自定义排序函数，只能用仿函数，不能用普通函数的指针。

示例：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<functional>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class cmp
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
	bool operator()(int a, int b)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return a < b;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool cmp2(int a, int b)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	return a < b;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      template <typename A>
     
    
   

    

     

    
    

     

      void display()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	A q;
     
    
   

    

     

    
    

     

      	q.push(1);
     
    
   

    

     

    
    

     

      	q.push(3);
     
    
   

    

     

    
    

     

      	q.push(4);
     
    
   

    

     

    
    

     

      	q.push(2);
     
    
   

    

     

    
    

     
	while (!q.empty())
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		cout << q.top();
     
    
   

    

     

    
    

     

      		q.pop();
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	cout << endl;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	display < priority_queue<int, vector<int>> >();  //默认大顶堆 
     
    
   

    

     

    
    

     

      	display < priority_queue <int, vector<int>, greater<int>> >();//小顶堆
     
    
   

    

     

    
    

     

      	display < priority_queue <int, vector<int>, less<int>> >();//大顶堆
     
    
   

    

     

    
    

     

      	display < priority_queue<int, vector<int>, cmp>>();//大顶堆
     
    
   

    

     

    
    

     
	//display < priority_queue<int, vector<int>, cmp2>>(); 错误
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

输出：

4321
1234
4321
4321

附上priority_queue的实现代码：

  

   

    

     

    
    

     
		// TEMPLATE CLASS priority_queue
     
    
   

    

     

    
    

     

      template<class _Ty,
     
    
   

    

     

    
    

     
	class _Container = vector<_Ty>,
     
    
   

    

     

    
    

     
	class _Pr = less<typename _Container::value_type> >
     
    
   

    

     

    
    

     
	class priority_queue
     
    
   

    

     

    
    

     

      	{	// priority queue implemented with a _Container
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     

      	......
     
    
   

    

     

    
    

     

      	一堆函数
     
    
   

    

     

    
    

     

      	......
     
    
   

    

     

    
    

     

      protected:
     
    
   

    

     

    
    

     

      	_Container c;	// the underlying container
     
    
   

    

     

    
    

     

      	_Pr comp;	// the comparator functor
     
    
   

    

     

    
    

     

      	};
     
    
  
 

可以看出模板参数_Pr的默认值是less，也就是说默认排序函数是less函数。

priority_queue中包含一个排序的序列，堆顶是这个序列的最后一个元素，所以从小到大排序是大顶堆，从大到小排序是小顶堆。

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/104831555