C++中lambda与priority_queue一起使用

发表于 分类于 标签 Disqus： 本文字数： 415 阅读时长 ≈ 2 分钟

想写这篇博客的原因是在刷力扣的 347. 前 K 个高频元素 一题时，需要使用到优先队列priority_queue，其定义如下：

1
2
3
4
5
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

第三个参数是一个可以自定义的比较类型，其必须满足二元谓词，通常可以使用如下两种方法：

  1. 使用自定义的函数对象
  2. lambda表达式
  3. 使用std::greater或std::less（这里就不介绍这种方法了）

以题 347. 前 K 个高频元素 为例，我们要建立一个小根堆，那么代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
// 方法一

using PII = pair<int, int>;

// 比较类，重载了括号运算符
struct Comp {
    bool operator()(PII& p1, PII& p2) {
        return p1.second > p2.second;
    }
};

priority_queue<PII, vector<PII>, Comp> pq;

当然，另一种方法就是使用lambda表达式，如下：

1
2
3
4
5
6
7
8
// 方法二

using PII = pair<int, int>;
auto comp = [](PII& p1, PII& p2) {
    return p1.second > p2.second;
};
// 注意这里需要使用decltype
priority_queue<PII, vector<PII>, decltype(comp)> pq;

但值得注意的是，方法二需要在C++20下才可使用。这是因为priority_queue的第三个模板形参需要的二元谓词要求可复制构造。

lambda表达式即构造闭包（能够捕获作用域中的变量的无名函数对象）。而在C20之前，闭包类型非可默认构造，闭包类型没有默认构造函数。C20及之后，如果没有指定捕获，那么闭包类型拥有预置的默认构造函数。

而在目前，力扣中C编译器使用的是clang17，支持C20，故使用lambda表达式是没有问题的。