关于priority_queue

kmplayer

1,关于STL中的priority_queue:确定用top()查看顶部元素时,该元素是具有最高优先级的一个元素.
调用pop()删除之后,将促使下一个元素进入该位置.
2,如同stack和queue,priority_queue是一个基于基本序列容器进行构建的适配器,默认的序列器是vector.
先看一个示例:
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <functional>using namespace std;int main(){    srand(time(0));    priority_queue<int> prique_int;    for (int i = 0; i < 100; i++)        prique_int.push(rand() % 25);    while (!prique_int.empty())    {        cout << prique_int.top() <<' ';        prique_int.pop();    }    return 0;}
注:默认较大的值有较高的优先权.

下面这个示例,给予较小值较大的优先权.
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <functional>using namespace std;int main(){    srand(time(0));    //优先队列的完成构造.    priority_queue<int, vector<int>, greater<int> > prique_int;    for (int i = 0; i < 100; i++)        prique_int.push(rand() % 25);    while (!prique_int.empty())    {        cout << prique_int.top() <<' ';        prique_int.pop();    }    return 0;}
下面的示例重载了operator<,可以存在主次两个优先级.
#include <iostream>#include <queue>#include <string>using namespace std;class ToDoItem{    char primary;    int secondary;    string item;public:    ToDoItem(string td, char pri = 'A', int sec = 1)        : primary(pri), secondary(sec), item(td) {}    friend bool operator<(const ToDoItem& x, const ToDoItem& y)    {        if(x.primary > y.primary)            return true;        if(x.primary == y.primary)            if(x.secondary > y.secondary)                return true;        return false;    }    friend ostream& operator<<(ostream& os, const ToDoItem& td)    {        return os << td.primary << td.secondary << ": " << td.item;    }};int main(){    priority_queue<ToDoItem> toDoList;    toDoList.push(ToDoItem("Empty trash", 'C', 4));    toDoList.push(ToDoItem("Feed dog", 'A', 2));    toDoList.push(ToDoItem("Feed bird", 'B', 7));    toDoList.push(ToDoItem("Mow lawn", 'C', 3));    toDoList.push(ToDoItem("Water lawn", 'A', 1));    toDoList.push(ToDoItem("Feed cat", 'B', 1));    while(!toDoList.empty())    {        cout << toDoList.top() << endl;        toDoList.pop();    }    return 0;}
3,由于设计上的原因,不能在一个priority_queue上从头到尾进行迭代.
通过观察priority_queue的实现,它使用的函数有make_heap(),push_heap()以及pop_heap().
可以说优先级队列只是对堆的一个封装.

priority_queue使用的容器时protected的,标准c++规定其标识符为c,所以可以继承一个新类.
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <iterator>#include <algorithm>using namespace std;class PQI : public priority_queue<int>{public:    vector<int>& iml() //返回序列器    {        return c; //父类的protected成员    }};int main(){    srand(time(0));    PQI pqi;    for (int i = 0; i < 30; i++)        pqi.push(rand() % 20);    vector<int> iml = pqi.iml();    copy(iml.begin(), iml.end(), ostream_iterator<int>(cout, " "));    cout << endl;    while (!pqi.empty())    {        cout << pqi.top() <<' ';        pqi.pop();    }    return 0;}
4,下面的示例,用一个vector实现priority_queue.
//私有继承
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <iterator>#include <algorithm>using namespace std;template<class T, class Compare>class PQV : private vector<T>{public:    PQV(Compare cmp = Compare()) : comp(cmp)    {        make_heap(vector<T>::begin(), vector<T>::end(), comp);    }    const T& top()    {        return vector<T>::front();    }    //关键    void push(const T& x)    {        vector<T>::push_back(x);        push_heap(vector<T>::begin(), vector<T>::end(), comp);    }    //关键    void pop()    {        pop_heap(vector<T>::begin(), vector<T>::end(), comp);        vector<T>::pop_back();    }    bool empty() const    {        return vector<T>::empty();    }    bool size() const    {        return vector<T>::size();    }private:    Compare comp;};int main(){    srand(time(0));    PQV< int, less<int> > pqi;    for(int i = 0; i < 100; i++)    {        pqi.push(rand() % 50);    }    while(!pqi.empty())    {        cout << pqi.top() << ' ';        pqi.pop();    }    return 0;}
5,使用laying技术来实现
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <iterator>#include <algorithm>using namespace std;template<class T, class Compare>class PQV{public:    PQV(Compare cmp = Compare()) : comp(cmp)    {        make_heap(v.begin(), v.end(), comp);    }    const T& top()    {        return v.front();    }    //关键    void push(const T& x)    {        v.push_back(x);        push_heap(v.begin(), v.end(), comp);    }    //关键    void pop()    {        pop_heap(v.begin(), v.end(), comp);        v.pop_back();    }    bool empty() const    {        return v.empty();    }    bool size() const    {        return v.size();    }private:    Compare comp;    vector<T> v;};int main(){    srand(time(0));    PQV< int, less<int> > pqi;    for(int i = 0; i < 100; i++)    {        pqi.push(rand() % 50);    }    while(!pqi.empty())    {        cout << pqi.top() << ' ';        pqi.pop();    }    return 0;}