关于priority_queue

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;
}