std::priority_queue + lambda表达式 + decltype

发表于 更新于 分类于 Valine： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

std::priority_queue

std::priority_queue 是C++标准库提供的优先队列（最大堆）实现，位于头文件

默认情况下要求元素有“小于”运算，取堆顶，返回最大值。

可以通过模板参数调整排序方式让其返回最小值，或者为自定义类型定义排序方式。

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

模板参数：

T是数据类型

Container是维护最大（小）堆使用的容器类型

Compare是一个function object的类型，定义了排序方式

什么是function object？

function object是一种对象，这个对象的类重载了括号运算符，也就是 operator() ，所以这个对象可以使用 obj(…)，看上去就像在调用一个function一样。

使用比较器类定义优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <queue>
#include <vector>
using namespace std;

struct Student { // 学生
    int id; // 学号
    int height; // 身高
};

int main()
{
    // 定义比较器
    struct Cmp {
        bool operator() (const Node& a, const Node& b) {
            return a.height < b.height;
        }
    };
    // 定义优先队列
    priority_queue<Student, vector<Student>, Cmp> PQ;
}

使用lamda表达式排序

1
2
3
4
5
6
7
vector<Student> students = {...};
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b){
	return a.height < b.height;
});

// 等价的
std::sort(students.begin(), students.end(), Cmp());

使用lambda表达式的好处是让“比较方法的描述”接近sort的调用，无论从编写还是阅读都是更好的。

使用lambda表达式的坏处是，不方便复用比较方法。

使用lamda表达式定义优先队列

实际上priority_queue有一个构造函数，可以传递一个比较对象，如果不传递就会用模板参数定义默认的比较对象。

1
explicit priority_queue (const Compare& comp = Compare(), Container&& ctnr = Container());

我们可以通过构造函数参数传递一个lambda表达式定义比较方式，我们期望的定义优先队列的方式是

1
2
3
priority_queue<Node> PQ([](const Node& a, const Node& b) {
    return a.height < b.height;
});

但是很遗憾，我们并不能这样定义，这会导致编译错误，原因是我们在模板参数仅传递了数据类型T，而没有传递Compare，因此Compare使用了默认的less，而我们传递的lambda表达式显然不是less类型，因此不符合构造函数的参数要求。

使用decltype获取lambda表达式类型

因此我们不得不传递Compare为我们定义的lambda表达式的类型，这里可以使用 decltype 关键字，这个关键字直到C++11才被引入。

1
2
3
4
5
// 通过lambda表达式定义序
auto cmp = [](const Node& a, const Node& b) {
    return a.height < b.height;
};
priority_queue<Node, vector<Node>, decltype(cmp)> PQ(cmp);

看上去和通过定义比较器定义优先队列似乎差不多，实际上lambda表达式的魅力在于可以访问当前上下文中的其他变量。

例如：假设我们有一个 vector<Student>存储着学生信息，我们想定义一个存储学号的优先队列priority_queue，依然按照身高对其中学号排序

1
2
3
4
5
6
7
8
9
10
11
vector<Student> students = {...};
unordered_map<int, Student> id2stu;
for(auto& stu: students) {
	id2stu[stu.id] = stu;
}

// 我们可以很方便地把id2stu绑定到lambda表达式中用来排序
auto cmp = [&](int a, int b) {
    return id2stu[a].height < id2stu[b].height;
};
priority_queue<int, vector<int>, decltype(cmp)> PQ(cmp);

如果用定义比较器类的方式则需要通过构造函数传递id2stu的引用，然后绑定给成员变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<Student> students = {...};
unordered_map<int, Student> id2stu;
for(auto& stu: students) {
	id2stu[stu.id] = stu;
}

struct Cmp {
    const unordered_map<int, Student>& id2stu;
	Cmp(const unordered_map<int, Student>& id2stu) : id2stu(id2stu) {}
    bool operator() (int a, int b) const {
	    return id2stu[a].height < id2stu[b].height;
    }
};
priority_queue<int, vector<int>, Cmp> PQ;

本质是一样的，但是写法有些累赘。