STL priority_queue使用

Priority queues are a type of container adaptors,specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering condition.



This context is similar to aheapwhere only themax heapelement can be retrieved (the one at the top in thepriority queue) and elements can be inserted indefinitely.



Priority queues are implemented ascontainer adaptors, which are classes that use an encapsulated object of a specific container class as itsunderlying container, providing a specific set of member functions to access its elements. Elements arepoppedfrom the"back"of the specific container, which is known as thetopof the priority queue.



The underlying container may be any of the standard container class templates or some other specifically designed container class.The only requirement is that it must be accessible through random access iterators and it must support the following operations:

• front()
• push_back()
• pop_back()

Therefore, the standard container class templatesvectoranddequecan be used. By default, if no container class is specified for a particularpriority_queueclass, the standard container class templatevectoris used.



Support for random access iterators is required to keep a heap structure internally at all times. This is done automatically by the container adaptor by calling the algorithmsmake_heap,push_heapandpop_heapwhen appropriate.



In their implementation in the C++ Standard Template Library, priority queues take three template parameters:

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

Where the template parameters have the following meanings:

• T: Type of the elements.
• Container: Type of the underlying container object used to store and access the elements.
• Compare: Comparison class:A class such that the expressioncomp(a,b),where comp is an object of this class and a and b are elements of the container, returnstrueif a is to be placed earlier than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function.This defaults toless, which returns the same as applying the less-than operator (a<b).
  
  Thepriority_queueobject uses this expression when an element is inserted or removed from it (using push orpop, respectively) to grant that the element popped is always the greatest in the priority queue.

In the reference for thepriority_queuemember functions, these same names (T,ContainerandCompare) are assumed for the template parameters.

top默认是返回顶端的元素（比较高的元素）。
Access top element
Returns a constant reference to the top element in thepriority_queue. The top element is the element that compares higher in thepriority_queue, and the next that is removed from the container whenpriority_queue::popis called.

注意：stack方法顶端元素是s.top()方法，没有front（）和back（）方法，而deque是d.front()方法。

而priority_queue则是top()方法。

// priority_queue::push/pop
#include <iostream>
#include <queue>
using namespace std;

int main ()
{
  priority_queue<int> mypq;

  mypq.push(30);
  mypq.push(100);
  mypq.push(25);
  mypq.push(40);

  cout << "Popping out elements...";
  while (!mypq.empty())
  {
     cout << " " << mypq.top();
     mypq.pop();
  }
  cout << endl;

  return 0;
}

Popping out elements... 100 40 30 25

构造函数几种不同的方式：

// constructing priority queues
#include <iostream>
#include <queue>
using namespace std;

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return (lhs<rhs);
  }
};

int main ()
{
  int myints[]= {10,60,50,20};

  priority_queue<int> first;
  priority_queue<int> second (myints,myints+4);
  priority_queue< int, vector<int>, greater<int> > third (myints,myints+4);

  // using mycomparison:
  priority_queue< int, vector<int>, mycomparison > fourth;

  typedef priority_queue<int,vector<int>,mycomparison> mypq_type;
  mypq_type fifth (mycomparison());
  mypq_type sixth (mycomparison(true));

  return 0;
}

The example does not produce any output, but it constructs differentpriority_queueobjects:

First is empty.

Second contains the four ints defined formyints, with60(the highest) at its top.

Third has the same four ints,but because it usesgreaterinstead of the default (which isless), it has 10 as its top element.

Fourth, fifth and sixth are very similar to first: they are all empty, except that these usemycomparisonfor comparisons, which is a special comparison function that behaves differently depending on a flag set on construction.

如果执行：

for(int i=0;i<4;i++)
        fifth.push(*(myints+i));

    for(int j=0;j<4;j++)
    {
        cout<<fifth.top()<<endl;
        fifth.pop();
    }

输出 60 50 20 10

若是sixth，输出相反。
原文链接: https://www.cnblogs.com/youxin/archive/2012/10/02/2710310.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍