priority_queue(优先队列) – 清梦の知识小栈

本文最后更新于21 天前，其中的信息可能已经过时，如有错误请发送邮件到2350047859@qq.com

定义

C++的priority_queue模板定义为：

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

其中：

T：队列中元素的类型；
Container：存储元素的容器（需满足随机访问迭代器要求，默认是std::vector<T>）；
Compare：可调用对象类型（Callable Type），用于定义元素的排序规则（默认是std::less<>，即大顶堆）。。

我们简化一下这个模板，可以把他理解为这样

priority_queue<T, Container, Compare>;

T是要存放的数据类型

Container是实现底层堆的容器，必须是数组实现的容器，如vector、deque

Compare是比较方式/比较函数/优先级

重点理解：Compare（Function）必须是一个类型（而非对象），且该类型的实例必须是可调用的（即支持operator()，或为函数指针）,即这个类型的实例是一个可调用对象

priority_queue<Type>;

此时默认的容器是vector，默认的比较方式是大顶堆less<type>

//小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//大顶堆
priority_queue <int,vector<int>,less<int> >q;
//默认大顶堆
priority_queue<int> a;
//pair
priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty()) 
{
   cout << a.top().first << ' ' << a.top().second << '\n';
   a.pop();
}
//输出结果为：
2 5
1 3
1 2

常用函数

top()
pop()
push()
emplace()
empty()
size()

自定义比较方式

当数据类型并不是基本数据类型，而是自定义的数据类型时，就不能用greater或less的比较方式了，而是需要自定义比较方式

在此假设数据类型是自定义的水果：

struct fruit
{
    string name;
    int price;
};

手写过堆实现的应该清楚，堆逻辑上是一个二叉树，但是实际上是一个数组，堆顶就是最左边的元素，优先队列也是这样，堆的插入我们称为上滤，源代码中是当前节点和子节点比较，为TRUE的时候，子节点应该往上调整，传参的格式是 cmp(父节点，子节点) 。那么当父<子为T RUE 的时候，就会向上调整，即大顶堆。总结下来就是我们自定义的 cmp(a, b) 为 TRUE 时，子节点会向上调整，而a是父节点，b是子节点，当a<b为TRUE或者a>b为TRUE就会上虑，前者对应大顶堆，后者是小顶堆

自定义比较方式的方法有下面几种：

1.重载运算符

重载”<”

若希望水果价格高为优先级高，则

//大顶堆
struct fruit
{
string name;
int price;
friend bool operator < (fruit f1,fruit f2)
{
    return f1.peice < f2.price;
}
};

若希望水果价格低为优先级高

//小顶堆
struct fruit
{
string name;
int price;
friend bool operator < (fruit f1,fruit f2)
{
    return f1.peice > f2.price;  //此处是>
}
};

2.仿函数

若希望水果价格高为优先级高，则

//大顶堆
struct myComparison
{
    bool operator () (fruit f1,fruit f2)
    {
        return f1.price < f2.price;
    }
};

//此时优先队列的定义应该如下
priority_queue<fruit,vector<fruit>,myComparison> q;

3.lambda表达式

其实底层实现是一个匿名仿函数，是一个语法糖,后面也会提到

auto cmp = [](fruit a, fruit b){ return a.price < b.price; };
priority_queue<fruit,vector<fruit>,decltype(cmp)> q(cmp);

4.函数指针

bool cmp(fruit a, fruit b)
{
    return a.price < b.price;
}
// 定义一个函数指针类型，用于比较两个int
std::priority_queue<fruit, std::vector<fruit>, decltype(&cmp)> q(&cmp);

扩展与补充

1. 函数指针 vs 函数类型：为什么不能用`decltype(CMP)`代替`decltype(&CMP)`？

假设我们有一个自定义比较函数：

bool CMP(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.second > b.second; // 按第二个元素降序排列
}

CMP本身是函数类型（bool(const std::pair<int,int>&, const std::pair<int,int>&)）；
&CMP是函数指针类型（bool(*)(const std::pair<int,int>&, const std::pair<int,int>&)）。

优先队列的Compare参数需要什么？ Compare需要是一个可调用对象类型，而函数类型本身不能作为可调用对象类型（函数类型无法实例化，必须通过指针或引用调用）。因此，必须用函数指针类型作为Compare参数。

所以decltype(&CMP)第三个模板参数需要填入的是一个函数指针(function pointer)，而不是一个函数类型(function type)，

尽管在某些地方函数名会退化为指针但是实际上还是不一样（可以用typeid()验证），所以decltype不能将&符号去掉。

decltype(CMP)推导的是函数类型（无法作为Compare参数）；
decltype(&CMP)推导的是函数指针类型（可以作为Compare参数）。

因此，正确的写法是：

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(&CMP)> q(&CMP);

第三个模板参数是decltype(&CMP)（函数指针类型）

2. Lambda表达式的特殊处理：为什么不需要取指针？

Lambda表达式的类型是匿名仿函数类（Unnamed Functor Class），该类自动生成operator()成员函数（可调用）。例如：

Cppauto CMP = [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.second > b.second;
};

CMP的类型是一个匿名类（比如__lambda_12345）
该匿名类有一个operator()(const std::pair<int,int>&, const std::pair<int,int>&) const成员函数（可调用）。

decltype的作用： decltype(CMP)推导的是Lambda的匿名类类型（可直接作为Compare参数），因为该类型是可调用的。因此，正确的写法是：

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(CMP)> q(CMP);

这里：

第三个模板参数是decltype(CMP)（Lambda的匿名类类型）；
构造函数传入CMP（Lambda实例，即可调用对象）。

3. 为什么构造函数参数不能省略？

优先队列的构造函数之一为：

explicit priority_queue(
  const Compare& comp = Compare(),  // 比较器实例（默认值为Compare类型的默认构造对象）
  const Container& cont = Container()  // 底层容器实例（默认值为Container类型的默认构造对象）
);

模板参数Compare是比较器的类型而构造函数中的comp参数是Compare类型的实例（即比较器的具体对象），用于定义优先队列的排序规则。

当我们写std::priority_queue<int> q;时，实际上是省略了构造函数的comp参数，此时comp会使用默认值Compare()（即std::less<int>()）。这之所以可行，是因为对于std::less<>这类仿函数类（Functor Class），它们有默认构造函数（即不需要传入实例，优先队列会自动构造一个）。例如：

std::priority_queue<int> q; // 等价于std::priority_queue<int, std::vector<int>, std::less<int>> q(std::less<int>());

优先队列初始化时，会在构造函数内部根据传入的比较器类型创建一个可调用对象，这需要调用可调用对象类型的构造函数，如果没有指定，将执行这个可调用对象类型默认构造函数，但对于函数指针或Lambda：

函数指针类型的默认构造是nullptr（无效的可调用对象）；
Lambda的匿名类没有默认构造函数（无法自动生成实例）。

因此，必须手动传入可调用对象的实例（函数指针或Lambda对象），否则优先队列无法初始化。

情况1：`Compare`是函数指针类型

函数指针的默认构造值是nullptr（无效的可调用对象）。例如：

// 定义一个函数指针类型，用于比较两个int
using CompareFunc = bool(*)(int, int);
//这里为了方便举例直接使用了 using 定义 CompareFunc 为函数指针类型
// 尝试省略comp参数：priority_queue的构造函数会用CompareFunc()作为默认值，即nullptr
std::priority_queue<int, std::vector<int>, CompareFunc> q;  // 错误！因为comp是nullptr，无法用于排序

问题：nullptr不是有效的比较器（无法调用），因此优先队列无法初始化。解决：必须手动传入一个有效的函数指针实例：

bool myCompare(int a, int b) { return a > b; }  // 自定义比较函数（大顶堆）
std::priority_queue<int, std::vector<int>, CompareFunc> q(&myCompare);  // 正确，传入有效的函数指针
//这里相当于用 &myCompare 初始化了刚才声明的那个函数指针类型(CompareFunc)

情况2：`Compare`是Lambda的匿名类类型

Lambda表达式会被编译器转换为匿名类的实例（称为“闭包对象”）。这个匿名类没有默认构造函数（C++11及以后的标准规定），因此无法自动生成实例。例如：

// 定义一个Lambda作为比较器（大顶堆）
auto cmp = [](int a, int b) { return a > b; };

// 尝试省略comp参数：priority_queue的构造函数需要用decltype(comp)()作为默认值，但decltype(comp)（匿名类）没有默认构造函数
std::priority_queue<int, std::vector<int>, decltype(cmp)> q;  // 错误！无法生成默认的comp实例

问题：匿名类没有默认构造函数，无法通过decltype(comp)()生成实例，因此必须手动传入comp参数。解决：手动传入Lambda实例：

std::priority_queue<int, std::vector<int>, decltype(cmp)> q(cmp);  // 正确，传入有效的Lambda实例

而当Compare类型是仿函数类（如std::less<int>或自定义的MyGreater）时，构造函数的comp参数默认值是Compare()（即仿函数类的默认构造实例），由于仿函数类的默认构造实例是有效的可调用对象（可以正常调用operator()），因此不需要手动传入comp参数，优先队列会自动使用这个默认实例来进行排序。

4. 为什么要用decltype？

decltype的核心作用是自动推导可调用对象的类型，避免手动编写复杂的类型声明，提高代码的正确性和简洁性。

1. 避免手动写复杂类型

例如，函数指针类型bool(*)(const std::pair<int,int>&, const std::pair<int,int>&)非常冗长，而decltype(&CMP)可以自动推导该类型，无需手动编写。

2. 处理Lambda的匿名类型

Lambda的类型是匿名的（无法手动命名），只能通过decltype推导。例如，decltype(CMP)是Lambda的匿名类类型，无法用其他方式获取。

3. 保持代码一致性

无论是函数指针、Lambda还是仿函数类，decltype都能统一推导其类型，使代码风格一致。

总结

优先队列的Compare参数要求：必须是可调用对象类型（函数指针类型、仿函数类类型、Lambda匿名类类型）。
函数的处理方式：需用decltype(&函数名)推导函数指针类型，并传入函数指针实例。
Lambda的处理方式：需用decltype(Lambda变量)推导匿名类类型，并传入Lambda实例。
decltype的作用：自动推导可调用对象的类型，避免手动编写复杂类型，处理Lambda的匿名类型。

例子验证

举两个常用的例子

1. 函数指针的情况

\#include <queue>
#include <vector>
#include <utility>

bool CMP(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.second > b.second;
}

int main() {
    // 正确：用decltype(&CMP)推导函数指针类型，传入&CM P实例
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(&CMP)> q(&CMP);
    q.push({1, 10});
    q.push({2, 5});
    q.push({3, 20});
    // 输出：(3,20), (1,10), (2,5)（按second降序）
    while (!q.empty()) {
        std::cout << "(" << q.top().first << "," << q.top().second << ") ";
        q.pop();
    }
    return 0;
}

2. Lambda的情况

\#include <queue>
#include <vector>
#include <utility>

int main() {
    auto CMP = [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.second > b.second;
    };
    // 正确：用decltype(CMP)推导Lambda匿名类类型，传入CMP实例
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(CMP)> q(CMP);
    q.push({1, 10});
    q.push({2, 5});
    q.push({3, 20});
    // 输出：(3,20), (1,10), (2,5)（按second降序）
    while (!q.empty()) {
        std::cout << "(" << q.top().first << "," << q.top().second << ") ";
        q.pop();
    }
    return 0;
}

一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

定义