C++ STL中的 priority_queue::push() 和 priority_queue::pop()

什么是priority_queue

在C++ STL(STandard Library)中，priority_queue是一个优先队列容器，是一种特殊的队列，其元素按优先级顺序进行排序。从名称上来看，可以理解为一个有特殊排序的队列，即按“优先级”来决定哪个元素应该在队列前面。

priority_queue的基本模板

在C++ STL中， priority_queue 基于 vector 实现，采用完全二叉树的数据结构，内部实现方式也类似于堆和堆排序，但是可以自定义“优先级”的比较函数。下面是 priority_queue 的基本模板：

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

其中：

T：参数类型，表示优先队列中保存元素的类型。
Container：具体实现容器，默认是 vector。
Compare：可选参数，自定义比较函数。如果省略，采用默认的 less<> 比较器。less<> 是 STL 中内置的一个仿函数，可用于比较数字和字符等基本数据类型。

priority_queue中的重要方法

在priority_queue中，有四个重要的方法：push、pop、top 和 size。

push

使用push方法将元素加入 priority_queue 中，此时 priority_queue 会自动对新元素进行排序。下面是示例代码：

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<int> q;
    q.push(3);
    q.push(1);
    q.push(4);
    q.push(1);
    q.push(5);

    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop(); // pop the top element
    }
    return 0;
}

输出结果为 5 4 3 1 1。由此可见，priority_queue 首先通过 push 方法将元素插入队列中，然后自动排序。这时通过输出 top 方法返回队列前端最高优先级的元素，接着通过 pop 方法将队列第一个元素删除。

pop

使用pop方法则是将 priority_queue 中最高优先级的元素弹出，这是 priority_queue 模板的一个方法。下面是示例代码：

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<int> q;

    for (int i=1; i<=5; i++) {
        q.push(i);
    }

    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    return 0;
}

输出结果为 5 4 3 2 1。首先，通过push方法将元素插入队列中，在此过程中，插入的元素实际上是按照优先级自动排序的。后来通过pop方法弹出队列中的最高优先级元素。

自定义priority_queue的比较器

前面提到过，如果用户省略了Compare参数，那么默认情况下 priority_queue 利用 STL 的less<>比较器，该比较器可以比较数字和字符等基本数据类型。如果我们需要使用其他类型的数据或者定义自己的比较方式，就需要自定义一个比较器。

接下来我们来看一下如何自定义比较器。下面我们用两个不同方法比较单词长度的长短。

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <functional> // std::greater<>

using namespace std;

class LengthSort {
public:
    bool operator()(const string &s1, const string &s2) const {
        return s1.size() > s2.size();
    }
};

int main() {
    priority_queue<string, vector<string>, LengthSort> myQueue;

    myQueue.push("longest");
    myQueue.push("longer");
    myQueue.push("long");
    myQueue.push("short");
    myQueue.push("shortest");

    while (!myQueue.empty()) {
        cout << myQueue.top() << " ";
        myQueue.pop();
    }
    return 0;
}

输出结果为 longest shortest longer long short。其中，LengthSort是我们自己定义的一个比较器，它是一个返回布尔类型的函数，好像返回true/false之类的。具体地，它含有两个字符串作为参数，这两个字符串要通过size来比大小，而不是使用 STL 内置的比较器。最后一条语句 operator() 的含义是判断条件是否满足，如果满足，则返回true而不是返回第一个字符串是否大于第二个字符串。

另外，我们可以使用STL的greater比较来实现同样的功能。修改方式如下：

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <functional> // std::greater<>

using namespace std;

int main(){
    priority_queue<int, vector<int>, greater<int>> q;

    q.push(3);
    q.push(1);
    q.push(4);
    q.push(1);
    q.push(5);

    while (!q.empty()) {
        cout << q.top() << ' ';
        q.pop();
    }
    return 0;
}

这里就不需要自己定义比较器，使用STL内置的greater即可，输出结果为1 1 3 4 5。

结论

通过上述的讲解，我们可以知道在使用 C++ STL 中的priority_queue的过程中，可以自定义比较器来决定元素之间的优先级，也可以使用STL内置的less<>和greater<>比较器来帮助我们快速地实现排序。同时，priority_queue还提供了push、pop、top 和 size等重要方法，可以方便地操作和管理队列中的元素。我们可以通过上面提到的示例代码来快速学习这些方法的用法，加深对其理解。