「STL::queue」标准库适配器：priority_queue（优先队列）介绍|自定义比较运算（C++）

admin管理员组

文章数量:1623789

目录

概述

创建销毁

内部理解

构造析构

自定义比较

赋值重构

数据访问

内存管理

数据控制

Tips

---

概述

priority_queue 是一种C++标准模板库STL中定义的一种序列容器，它允许你在运行时动态地进行堆操作。

priority_queue 可以自动管理内存，这意味着你可以添加任意多的元素在其中，并且你不需要手动分配和释放内存。

其虽名为优先队列，它实际上是一个堆空间。

优先队列即是容器，也是适配器，它同时具有容器和适配器的特性：

动态大小：内存空间可以根据需要自动增长和缩小。

堆行为：优先队列默认执行大顶堆操作，即优先弹出队内最大的元素，可以通过设置来更改比较关系。

元素容器：可以存储任何类型的元素，包括基本类型、对象、指针等。

接下来，我们介绍priority_queue类型定义的成员函数。

*注意*:本文不涉及allocator空间配置器和C++23新增的range类函数。

---

创建销毁

内部理解

默认的优先队列的内部实际就是一个时刻进行动态堆排序的堆化数组。

关于堆排序与堆化数组：「数组」堆排序 / 大根堆优化（C++）

为了理解构造函数中less<T>产生大根堆的原因，我们了解一下优先队列的内部关系比较：

优先队列内部有一个成员Compare comp;

这是一个重载了()运算符的仿函数类,comp(参数1,参数2)就会调用comp内部的比较函数。

优先队列内部使用这个类执行父子比较，即如果comp(父，子)返回true，则父子交换。

STL内置了std::less和std::greater两种仿函数类型。

默认优先队列的Compare是一个less类型，使用less(父,子)等同于{父<子}。

例如，一个储存int的优先队列内部维护的堆化操作实际上是这样的：

//以下是less的实现
template<typename T>
class less{
public:
     bool operator () (const T& a,const T&b){
         return a<b;   
     }
}
//以下是优先队列维护大根的交换逻辑
less<int> comp;
if(comp(father,child))
   swap(father,child);
//如果父<子，那么交换父子，使大的元素成为父

STL中有序容器默认以less比较，这就是为何priority_queue使用less作为比较规则却得到大根堆的原因。 

构造析构

STL库提供了以下方式创建一个priority_queue。

以T表示任意类型。

无参构造	priority_queue<T>pq();	生成一个存储T类型的priority_queue，默认以vector为底层，less比较。
拷贝构造	priority_queue<T>que(const priority_queue& another);	将another整体赋值给新priority_queue。
移动构造	priority_queue<T>que(priority_queue&& another);	窃取另一个priority_queue容器，即直接获取它维护的底层指针地址，再将它的指针置空。
指示底层容器和比较规则的构造	priority_queue<T,vector<T>,Compare<T>>pq (const Compare& compare,const vector& vec) priority_queue<T,list<T>,Compare<T>>pq (const Compare& compare); priority_queue<T,deque<T>,Compare<T>>pq (const Compare& compare); （多么疯狂的模版实例和参数列表）	指示优先队列以列出的三种容器作为底层，以给定的compare作为比较规则。 仅有当以vector作底层使可以使用现有vector数据传值（也可以不传）。 不推荐使用list和deque。 在模版参数中的Compare若已定义，可以在参数列表中不传值。 （更多用法如lambda表达式，详见表格后示例）
提供源数据地址的构造	priority_queue<T,vector<T>,Compare<T>>pq (const T* begin,const T* end,const Compare& compare)	从定长数组（初末指针）或另一容器（初末迭代器）中获取数据进行构造。 在模版参数中的Compare若已定义，可以在参数列表中不传值。 需要注意的是，迭代器指向的容器需是一个提供随机访问迭代器的容器。
析构函数	~priority_queuequeue();	无须手动调用。程序自动在代码块结束时调用，清理掉priority_queuequeue。

 （用C++的都是什么模版受虐狂）

自定义比较

#include <queue>
#include <list>
#include <vector>
#include <deque>
#include <functional>
template<typename T>
struct comp {
    bool operator () (const T& a, const T& b) {
        return a <= b;
    }
};
bool fun(const int& a, const int& b) {
    return a <= b;
}
int main(){
    priority_queue<int>pq0;//默认vector,less大根堆
    priority_queue<int>pq0c(pq0);
    priority_queue<int, vector<int>, greater<int>>pq1;//vector小根堆

    priority_queue<int, list<int>, greater<int>>pq2();//list 不推荐
    priority_queue<int, deque<int>, less<int>>pq3();//deque 不推荐

    //以下仅vector可用
    int a[3] = { 1,2,3 };
    vector<int>v = { 1,2,3 };
    priority_queue<int, vector<int>, greater<int>>pq4(greater<int>(), v);
            //↑提供数据源vector容器，在这种情况下，由于参数列表的设计，需要传入一个无名比较函数
    priority_queue<int, vector<int>, greater<int>>pq5(a,a+3);//提供源数据指针
    priority_queue<int, vector<int>, greater<int>>pq6(v.begin(),v.end());//提供源数据vector迭代器

    //以下是自定义比较方法
    priority_queue<int, vector<int>, comp<int>>pq7();//以类形式使用自定义比较规则(strcut和class都是可以的)
    priority_queue<int, vector<int>, decltype(&fun)>pq7(fun);//以函数形式使用自定义比较规则，decltype自推断
    auto lambda = [](const int& a, const int& b) {return a <= b; };
    priority_queue<int, vector<int>, decltype(lambda)>pq7(lambda);//以lambda表达式使用自定义比较规则，decltype自推断
    priority_queue<int, vector<int>, function<bool(const int&, const int&)>>pq7(lambda);//以lambda表达式使用自定义比较规则，显式声明
}

---

赋值重构

在必要时我们会对priority_queue进行重新初始化。

重载拷贝赋值=	priority_queue& (const priority_queue& another);	作用同拷贝构造。不仅可以在初始构造时使用。返回自身。
重载移动赋值=	priority_queue& (priority_queue&& another);	作用同移动构造。不仅可以在初始构造时使用。返回自身。

---

数据访问

访问堆顶元素

front();

返回堆顶元素。即按比较关系取得的最值元素。默认是最大元素。

---

内存管理

priority_queue仅有两个内存相关函数。

获取实际长度	size();	返回queue中的元素个数。
判断是否为空	empty();	size==0时返回true，否则返回false。

---

数据控制

priority_queue按堆执行操作。

压入	push(T elem);	压入元素。
堆顶弹出	pop_back();	弹出堆顶元素。即按比较关系取得的最值元素。默认是最大元素。
交换 （C++11）	swap(priority_queue& another);	交换两个容器的元素。
安置（C++11）	emplace(T elem);	C++11后可用，原地构造一个元素，作用与push()相同，但没有赋值过程而是原地生成新元素，所以效率更高。

---

Tips

通常不会使用list和deque作为优先队列的底层，这是由于他们的性能会远远差于vector底层。

vector能够以线性表的结构映射一颗完全二叉树从而实现堆，因此vector的时间和空间性能都是极好的。

本文标签： 队列自定义适配器标准stl