C++给常用数据结构传入排序算法

在刷leetcode347题时，遇到c++自定义操作的知识点，总结如下：

问题：

在类中定义了如下比较函数(函数对象)，但定义有序容器时编译不通过。

bool myComparison(const pair<int, int>& lhs, const pair<int, int>& rhs){
    return lhs.second > rhs.second;
}

// 注意：建堆时，左大于右是小顶堆，与写其它容器排序时相反；

priority_queue<pair<int, int>, vector<pair<int, int>>,
			  decltype(&myComparison)> pri_que(myComparison);
或
priority_queue<pair<int, int>, vector<pair<int, int>>,
			  decltype(myComparison)*> pri_que(myComparison);

编译报错如下：

error: reference to non-static member function must be called 即必须调用对非静态成员函数的引用

解决：

所以比较函数定义错误，正确解法如下：

1.定义为静态成员函数

static bool myComparison(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    return lhs.second > rhs.second;
}

2.将比较函数定义在类外面

注意函数声明在类前。

3.运用仿函数

class myComparison {
public:
	bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) const {
		return lhs.second > rhs.second;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int>>, myComparison> pri_que;

---

总结：

1.容器的操作自定义处

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(myComparison)*> pri_que(myComparison);

• 为了使用自己定义的操作，在定义容器时必须提供两个类型：关键字类型即pair<int, int>，比较操作类型即指向myComparison的指针decltype(myComparison)*；
• 此处使用decltype指出自定义操作的类型，但当使用decltype来获取一个函数指针类型时，须加上一个*号来表示使用一个给定函数类型的指针；
• 定义有序容器时，vector<pair<int, int>>表示基于vector构造优先队列；
• pri_que(myComparison)表示用myComparison来初始化pri_que对象，即向pri_que添加元素时，调用myComparison来排序；
• 用pri_que(myComparison)代替pri_que(&myComparison)因为使用函数名字会自动转化为指针；

2.比较函数自定义处

return lhs.second > rhs.second;

• >此比较符号表示在优先队列中左大于右就会建立小顶堆；

扩展：

1.向算法传递函数

即使用标准库的算法时，传入参数使用自己的操作，示例如下：

// 升序
bool isShorter(const string& s1, const string& s2){
    return s1.size() < s2.size();
}
sort(words.begin(), words.end(), isShorter);

2.在算法中使用lambda表达式

即编写与isShorter函数功能相同的lambda表达式，示例如下：

sort(words.begin(), words.end(),
    [](const string& s1, const string& s2)
     {return s1.size() < s2.size();});

参考：

• 代码随想录博客
• 《C++primer》第五版