C++ priority_queue如何自定义比较函数？和sort里面自定义比较函数有何区别？

1. C++ priority_queue如何自定义比较函数以及和sort里面自定义比较函数的区别

首先看C++ 官方文档对priority_queue的模板定义：

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

注意：

1. 后面两个参数可以不写，因为有默认值，但是如果写了，就必须两个都写，而且要按照顺序填写！
2. Compare是类名！不是对象名！
   在algorithm里面一样也有很多函数会用到自定义比较函数，比如sort：

template <class RandomAccessIterator, class Compare>  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1

这里需要传入的就不仅仅是类名，而是对象名！
可以注意一下C++里面的其他内部有序的数据结构，如map，set，可以看到，这些Compare都是类名，而不是类的对象！这是非常容易犯的错误。
map：

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;
1
2
3
4
5
6

set：

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;
1
2
3
4
5

总结：最主要的就是sort里面比较函数必须是对象，而priority_queue等则是类名！

2. 比较函数有以下几种：

注意：结构体最好在函数后面加上const限定符，否则构造priority_queue等对象的时候可能会报错！
如可能出现以下错误：

Visual Studio编译器错误 C3848 具有类型“type”的表达式会丢失一些 const-volatile
限定符以调用“function”

解决办法就是像下面的第一种里面的代码一样，重载函数调用运算符的时候加上const限定符。

vector<pair<int, int>> vec;
1

第一种：采用函数对象，关于什么是函数对象可以参考C++ 函数对象（Function Object）是什么？

结构体
struct compare {
	bool operator () (const pair<int, int>& A. const pair<int, int>& B) const {
		return A.second < B.second;
    }
}
sort(vec.begin(), vec.end(), compare{});
sort(vec.begin(), vec.end(), compare());
1
2
3
4
5
6
7
8

第二种：采用全局函数，这里应该会进行转换，cmp是一个函数指针，实际用的是一个函数对象
由于这里调用的就是一个实际的函数对象，所以可以直接传入（不用额外构造函数对象）。

函数
bool cmp(const pair<int, int>& A. const pair<int, int>& B) {
	return A.second < B.second;
}
sort(vec.begin(), vec.end(), cmp);
// 不用加()
1
2
3
4
5
6
7

第三种：采用标准库自带的less或者greater，注意这种也必须传入一个具体的对象，下面两种方法都可以

less或者greater
sort(vec.begin(), vec.end(), less<pair<int, int>>()); 
sort(vec.begin(), vec.end(), less<pair<int, int>>{}); 

1
2
3
4

在官方文档里面也可以看到，其实less是重载了运算符()的

std::less::operator()
bool operator()( const T& lhs, const T& rhs ) const;
1
2

因此我觉得，less>{}这种方式是构造一个类的对象，而less>()调用的应该是直接调用less>重载的()方法，只不过前者也是调用重载的()方法。
可以通过对结构体（即第一种方法进行验证）
验证方法如下：

结构体
struct compare {
	bool operator () (const pair<int, int>& A. const pair<int, int>& B) const {
		cout <<  "()" << endl;
		return A.second < B.second;
    }
}
sort(vec.begin(), vec.end(), compare{});
sort(vec.begin(), vec.end(), compare());
1
2
3
4
5
6
7
8
9

可以发现两种方法都会输出()，说明在比较的过程中都是调用了重载的()函数的。

参考资料：

cppreference