关于STL优先级队列的一些应用

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 expression comp(a,b), where comp is an object of this class and a and b are elements of the container, returns true if 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 to less<T>, which returns the same as applying the less-than operator (a<b).
The priority_queue object uses this expression when an element is inserted or removed from it (using push or pop, respectivelly) to grant that the element popped is always the greater in the priority queue. 

这里可以看到priority_queue的接口使用情况，priority_queue是容器适配器（也有书称之为容器配接器），默认使用适配容器为vector，当然也可以使用其他的适配容器，其默认的比较函数模板是less，即大顶堆。

priority_queue函数模板的成员函数如下：

Member functions
(constructor) Construct priority queue (public member function) 
empty Test whether container is empty (public member function) 
size     Return size (public member function) 
top      Access top element (public member function) 
push   Insert element (public member function) 
pop     Remove top element (public member function) 

下面我们先来看一个简单的应用。

sing namespace std ;

int main()
{
    priority_queue<float> q;

    // insert three elements into the priority queue
    q.push (53.4);
    q.push (23.4);
    q.push (33.4);

    // read and print two elements
    cout << q.top () << ' ';
    q.pop ();
    cout << q.top () << endl;
    q.pop ();

    // insert three more elements
    q.push (11.4);
    q.push (65.5);
    q.push (43.3);

    // skip one element
    q.pop ();

    // pop and print remaining elements
    while (!q.empty ()) {
        cout << q.top () << ' ';
        q.pop ();
    }
    cout << endl ;
}

输出：
53.4  33.4
43.3  23.4 11.4

上面的比较函数为默认less，元素大的优先级高，构造的是大顶堆，所以输出不难理解。

但是如果我们想让上述元素从小到大排列优先级怎么办？我们需要传入比较函数，使用functional.h中的函数对象作为比较函数。如下格式

priority_queue<float, vector<float>, greater<float> > Q;
此处注意一个问题：
表示最后的两> >中间必须隔一个空格，否则容易被编译器误认为输入操作符

如果我们想自定义自己的比较函数怎么办呢？比如说很多时候我们比较的并不是内嵌式数据类型，我们可能比较的是我们自定义的结构体关系，需要独立的比较函数。

则我们需要考察调用机制。在为优先级队列建立默认堆的时候我们需要使用一个比较函数模板，代码如下：

template<class _Ty>
    struct less
        : public binary_function<_Ty, _Ty, bool>
    {    // functor for operator<
    bool operator()(const _Ty& _Left, const _Ty& _Right) const
        {    // apply operator< to operands
        return (_Left < _Right);
        }
    };

问题就处在这行代码。我们使用了"<"操作符，内嵌式的类型编译器都定义好了这种操作符，而我们自定义的结构体或者类没有重载这个操作符，这样找不到函数调用，从而导致错误，

如何解决这个问题呢，我们只有自己动手丰衣足食，重载这个默认的操作符如下。

struct MyType
{
    friend bool operator< (MyType T1,MyType T2)
    {
        return T1.priority < T2.priority;
    }
    int priority;
    ElemType value;
};

但是有的童鞋可能要问，我不想用“<”操作符，我要实现的是">"操作符，定义大于关系，于是这位童鞋定义了这个

struct MyType
{
    friend bool operator> (MyType T1,MyType T2)
    {
        return T1.priority > T2.priority;
    }
    int priority;
    ElemType value;
};

问题来了，编译器还是找不到<操作符调用，为什么呢，呵呵？因为我们优先级队列定义的完整类型是这个

priority_queue<MyType, vector<MyType>, less<MyType> > Q;  priority_queue<MyType > Q的完整类型

这里使用的比较函数模板是less，里面只用到“<”操作符。当然你也可以如下声明

struct MyType
{
    friend bool operator< (MyType T1,MyType T2)
    {
        return T1.priority > T2.priority;
    }
    int priority;
    ElemType value;
};

但是不直观，STL为大于比较函数定义了greater模板，和less函数类模板一样，只不过使用的是">"操作符，因此，我们可以如下声明和使用priority_queue

struct MyType
{
    friend bool operator> (MyType T1,MyType T2)
    {
        return T1.priority > T2.priority;
    }
    int priority;
    ElemType value;
};

priority_queue<MyType, vector<MyType>, greater<MyType> >Q;

这样使用就没有什么问题了，很简单的东西，但是讲具体了发现自己还是能学到一些东西。谢谢大家阅览了。

关于优先级队列的应用，请参考上一篇文章

Dijkstra算法优先级队列版 算法基础篇（三）