priority_queue 乱象

,

在 Leetcode 的 373.查找和最小的 K 对数字 题目中为了保证每次的迭代我们都能得到和最小的元素,我们需要借助 STL 中的优先队列按照比较标准(Compare)将优先级最高的元素总是放在队列首部的特点来取得和最小的 K 个元素.
在 STL 中 priority_queue 并不是一种容器,其是一种 container adapter.其通过将其他容器提供的接口和堆(heap)算法结合,将原有的接口改变为优先队列特有的接口.

在默认的实现中,通常优先队列的默认底层容器都是 vector,这一点可以通过 priority_queue 类的模板定义就能确定.
同时模板定义还指定了作为元素比较的方式 Compare.默认情况下,C++ 通过作用域运算符访问的名字看作是变量而不是一个类型,我们需要使用 typename 关键字显式的告诉编译器这是一个类型. 然后通过底层容器 Sequence 中定义的 value_type 得到容器中的元素类型

1
template <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> >

更多关于优先队列的源码可以在这里查看.

遇见的“乱象”

由于我们在优先队列中需要储存 nums1 和 nums2 的下标,所以我们需要将 模板参数 T 指定为 pair<int, int>.底层的数据结构依旧是vector,不过 vector 中存储的元素类型是pair<int, int>.对于比较函数 Compare,由于我们需要构建的是“最小堆”,所以我们需要指定更改 less 为 自定义的比较函数 cmp.我们选择使用 lambda 函数来完成任务,同时使用隐式引用捕获来让编译器根据函数体中的代码来推断需要捕获哪些变量.

1
2
3
auto cmp = [&](value_type &a, value_type &b){
	return nums1[a.first] + nums2[b.second] >  nums1[a.second] + nums2[a.first];
    };

这些并没有什么难以理解的,但是难以理解的是对优先队列的实例化方式.

1
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

decltype,在C++中,作为操作符,用于查询表达式的数据类型

这样的代码相当的“啰嗦”,但是如果你尝试删掉“多余的无效声明”时,你会发现这实际上十分的困难.每一个部分都是必可不少的,你甚至不能删除对于 cmp 的两次“重复”的使用(一处是 decltype(cmp), 一处是作为构造函数参数传入的 cmp).

priority_queue 解析

priority_queue 采用模板的方式进行定义,因此我们很容易使用内置的数据类型作为优先队列的元素类型.

1
2
3
4
5
priority_queue<int> pq1;
priority_queue<double> pq2;
priority_queue<string> pq3;
......
> 在声明优先队列时如果仅仅指定元素的类型,那么我们得到的默认底层实现为 vector 的“元素优先最小队列”

对于任何重写了’<’运算符的内置数据类型,我们可以以很简单的形式定义优先队列.对于用户自定义的数据类型,我们也仅仅需要给出元素之间的比较规则即可.例如你可以定义一个结构体然后重写运算符’<’来指出对于结构体元素的比较方法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct mytype
{
	int x, y;
	mytype(int x_, int y_):x(x_),y(y_) {}
	// 尾部的 const 是必须的
	bool operator<(const  mytype &a) const{
		return a.x + a.y < x + y;
	}
};

int main() {
	priority_queue<mytype> pq;
	pq.push(mytype(-1,0));
	pq.push(mytype(1,0));
	std::cout <<pq.top().x;
}

一切似乎都很完美,直到我们使用系统内置的数据类型但是需要单独指定的 Compare 函数时,一切就不是这么美好了.文章开头的例子就是这样,使用 pair<int, int> 作为优先队列中元素,我们需要的不是“最小堆”而是“最大堆”,我们需要按照下面的格式声明优先队列.

1
2
3
4
5
6
7
// STL 提供了如下的优先队列构造函数
explicit priority_queue(const Compare& x) :  c(), comp(x) {}
//我们指明优先队列元素类型,同时使用上面的构造函数形式来实例化优先队列
priority_queue<int> pq1(cmp);
priority_queue<int, vector<int>> pq2(cmp);
priority_queue<int, cmp> pq3;
priority_queue<int, vector<int>,decltype(cmp)> pq4;

让人吃惊的是,上面的几种实例化方式连编译环节也通不过.
让我们回忆一下 priority_queue 的声明:

1
2
3
4
5
6
7
8
9
10
11
template <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> >
priority_queue {
	//...
protected:
	Sequence c; // 底层容器
	Compare comp;
public:
	priority_queue() : c() {}
	explicit priority_queue(const Compare& x) :  c(), comp(x) {}
	//...
}

对于第一种实例化形式,我们通过传递自定义的lambda cmp 给 priority_queue 的构造函数,通过初始化列表的方式进行初始化(其中底层容器 c 使用默认构造函数,而 comp 调用复制构造函数进行构造.这一切似乎都合情合理,但是这里有一个麻烦的地方 —— comp 的类型是什么?
第二种实例化形式指明模板参数 T 为 int、 Sequence 为 vector,但是并没有明确的指出 Compare 的类型. 我们试图通过调用构造函数来改变 模板参数中对于Compare 的默认实现,并“猜测”编译器会根据构造函数自行推导出模板声明中 Compare 的数据类型.遗憾的是这样想法只能是幻想.
priority_queue 的构造函数中行参 x 的类型是 Compare, 然而 Compare 的数据类型是由模板参数指定的,然而我们在实例化优先队列 pq2 时没有指明 Compare 的类型,编译器并不会根据复制构造函数的类型推导出 Compare 的类型.

如果你不想使用模板参数中默认的数据类型,唯一的做法是在实例化时明确的指出每一个模板参数的数据类型.因此更改 Compare 类型的唯一做法是在实例化变量时指明 Compare 的类型.

pq3 的实例化方式也是错误的, C++ 也并未为我们提供单独指定模板参数列表中某一个参数的方式,因此我们如果要指定 Compare,就一定要指出 Sequence 的数据类型.

总结了上面三种实例化参数“失败”的原因,在 pq4 的实例化中我们使用了 decltype 说明符检查 cmp 的声明类型.终于直接或间接的指明了优先队列所有模板参数,但这行代码依旧不能通过顺利的运行.

乱象的根源

上面第四个实例化示例失败的缘由是: 缺少对应的默认构造函数.
此时 pq 的类别是 std::priority_queue<int, std::vector<int, std::allocator>, lambda []bool (const int &a, const int &b)->bool>,
因此某一个构造函数才能正确的完成实例化.

如果我们不使用 lambda 表达式,而是将 cmp 定义为 struct ,那么代码就能顺利的运行,而此时调用的是 priority_queue 的默认构造函数.

1
2
3
4
5
6
7
template <typename T>
struct cmp {
	bool operator()(const T &a, const T &b) {
		return a < b;
	}
};
priority_queue<int, vector<int>, cmp<int> > pq; //调用默认构造函数完成实例化

使用 decltype 说明符指定 Compare 与使用模板 struct 指定 Compare 是有区别的. 使用 decltype 时, Compare 的类型是: lambda []bool (const int &a, const int &b,而使用模板结构体时 Compare 的类型是: cmp (构体名称)
最重要的是, lambda没有默认构造函数和析构函数. 但是结构体有默认的构造函数和析构函数. 因此使用 delctype得到 lambda 类型来定义 Compare 类型的优先队列不能调用默认的构造函数完成实例化.而使用结构体模板方式实例化优先队列可以调用默认的构造函数.

在 《Effective C++》一书中指出: 如果你没有声明，C++ 会为你声明(编译器版本)一个cop构造函数、copy assignment 操作符、和一个析构函数.如果你没有声明任何的构造函数，编译器也会为你声明一个 default 构造函数。

对于 lambda 而言,虽然没有默认的构造函数,但是却规定了 operator= 运算符.因此我们借助 delctype 说明符直接或者间接的指明模板参数类型之后,调用另一个 copy 构造函数完成对象的构造.

更多关于 lambda 的信息可以在这里查看.

C++ 确实提供了类模板参数推导的机制,但是假定类模板参数的推导是“万能的”是不现实的,很显然参数的推导需要遵守一定的规则 —— 1.类模板参数推导,2.模板形参与模板实参

1
2
3
4
5
6
7
8
9
10
template <class T1, class T2>
struct pair {
	typedef T1 first_type;
	typedef T2 second_type;
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2()) {}
	pair(const T1& a, const T2& b) : first(a), second(b) {}
	//...
}

对于 pair 我们并不陌生, pair 同样被实现为模板,下面的代码能够顺利的运行.

1
std::pair p(2, 4.5);

然而下面的代码不能通过编译,因为 k 和 nums.size() 的类型并不相同.

1
2
3
4
vector<int> nums  {0, 1, 2, 3};
int k = 10;
// min 的 模板声明为 template<typename T> ,因此 min 的两个实参的类型要相同.
int res = min(k, nums.size());

有趣的是,对于指定模板参数默认值的情况,如果我们不指出模板参数类型模板推导更倾向于默认的实现(double类型 2.1 可以转型为 int 类型)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T1, typename T2 = int>
class Mytype
{
public:
	T1 x;
	T2 y;
	Mytype(T1 x_, T2 y_):x(x_),y(y_) {}
};
int main() {
	Mytype<int> m(1, 2.1);
	// 结果是 2 和 int,而 m.x 编译器推导出类型为 int
	std::cout << m.y << std::endl; 
	std::cout << typeid(m.y).name() << std::endl;
}

结尾

对于 priority_queue ,如果我们想避免出现文章开头“冗余”的实例化代码,最好的办法是使用 struct. 但这样我们就放弃了 lambda 的便利性。为了使用 lambda ,我们又必须指出要使用 copy 构造函数。 lambda 和 模板结构体有着完全不一样的特点.使用 lambda 和 decltype 说明符的组合与使用 struct 是有区别的. 同时,在实例化模板类时,指出所有的模板参数类型是至关重要的.指明类模板参数在一定情况下是必须的,比如上面的 min 函数,编译器可以推导出两个参数的类型,却可能在两个类型的犹豫不决. 最后,我要指出的是类模板参数推导并不是万能的,只有特定情况才能完成类的参数类型推导.事实上,只有在 C++17 起编译器才会从初始化器的类型推导缺失的模板实参. 除此之外,编译器更倾向于指定的默认的参数声明,并不能通过构造函数的方式促使它重新推导模板参数.