【踩坑记录】priority_queue 第三个模板参数和sort 的第三个形参的区别；仿函数、自定义排序函数、lambda 函数分别传入；传入类型和对象的区别；_类成员变量 priority_queue

一、priority_queue

	priority_queue<int,vector<int>,greater<int>> q;

	auto cmp = [](const int & a, const int & b) {return a < b; };
	priority_queue<int, vector<int>, decltype(cmp)> que4(cmp);
	priority_queue<int, vector<int>, function<bool(const int&, const int&)>> que5(cmp);
1
2
3
4
5

• priority_queue<int,vector<int>,greater<int>> q;
• priority_queue<int, vector<int>, decltype(cmp)> que4(cmp);
• priority_queue<int, vector<int>, function<bool(const int&, const int&)>> que5(cmp);
• 以上三种，传入的都是类名，第一个调用的是无参的构造函数、第二、三种要带参数的构造函数（第二第三其实是一种，只不过用decltype 少写了代码；

• 也就是说：自己实现的函数，需要在模板中传入函数的类型，形参中还得传入函数实体，否则构造不出来；调用的是带参数的构造函数；
• 而greater 只需要传进去 类 的类型，构造过程调用的是默认构造；

• 至于为什么 greater 只需要调用默认构造；因为queue 库中有包含 less 、greater 的仿函数实现，直接构造即可；
• 而自己传入的，因为找不到实现，所以需要传入来构造；

• 如果用自己的函数，但又不传入函数实体；就会编译阶段报错无法构造；
• priority_queue<int, vector<int>, decltype(cmp)> que4;
  

二、sort

	auto cmp = [](const int & a, const int & b) {return a < b; };
	
	sort(nums.begin(), nums.end(), greater<int>());
	sort(nums.begin(), nums.end(), cmp);
1
2
3
4

• 首先知道的是，模板函数可以不用<> 声类型，因为可以根据传参推断；

• 而模板类，因为需要类型来构造成员变量，所以必须提前声明类型；否则就是先有鸡还是先有蛋了；

• 函数内传入对象实例；（自定函数传入，其实相当于function类传入）；都是构造了函数实体；

• greater<int>() 相当于 构造了greater类 的对象实例；内部用其重载的() 来实现了比较；
  

• 然后sort 内部根据传入的binary_function （二元函数对象类、二元谓词）进行快排、堆排、插入排序的；

• 所谓谓词：要求描述了返回可作为 bool 测试的值的可调用 (Callable) 体。

C++ 具名要求：谓词 (Predicate)

• 这个比较方式被用在了partition的过程中；通过仿函数，传入两个参数来作为对比；
  

三、总结：

• priority_queue 需要的是类型，根据类型，自己类内部定义对象来做；
• sort 需要的就直接是对象；根据传入对象来实现比较；（仿函数对象，自定义函数对象）

• 传入greater<int> 就是传入类型，因为这只是个类；
• 传入greater<int>() （带括号） 就是构造了一个这个类的对象，传入的是对象；
• 传入对象其实就像下图所示，直接构造个对象，然后内部用这个对象调用仿函数来实现；
• 而传入类型，前面有讲过，priority_queue 内部成员变量需要这个类型来定义对象；然后再调用；