C++比较函数cmp

本文将简单介绍C++比较函数 cmp.

排序函数sort()

sort函数是我们常用的库函数，它的参数如下：

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare cmp);

通过传入容器的迭代器（或指针），我们可以对指定位置进行排序：

vector<int> nums = { 1,3,2,4,5 };
sort(nums.begin(), nums.end()); //排序得到nums = { 1,2,3,4,5 }

可见，sort 函数的比较函数 cmp 默认参数为升序排列，当然也可以自定义函数来实现不同的排序方法。

比较函数cmp()

自定义比较函数

首先编写一个示例用以解释：

struct MyStruct {
    int weigth;
    string str;
};
bool cmp(const MyStruct& ms1, const MyStruct& ms2) {
    return ms1.weight < ms2.weight;
}
int main(){
    vector<MyStruct> msVector;
    sort(msVector.begin(), msVector.end(), cmp);
}

一般来说，cmp 函数具有以下规范：

1. 返回值为 bool 类型，用来表示当前的排序是否正确。
2. 参数为两个相同类型的变量，且类型与要排序的容器模板类型相同。

关于 cmp 作为比较函数实现排序的原理，可以这样来进行理解：在示例中，ms1 和 ms2 是两个参数，即 msVector 容器中的元素，且此时 ms1 位于 ms2 之前，此时函数的返回值其实就是给出此时排序的正确性。若正确则返回 true，反之返回 false。例如在示例中，该比较函数想要实现 MyStruct 结构体元素按照其 weight 值从小到大进行排列，因此返回值为 ms1.weight < ms2.weight。ms1 位于 ms2 之前，若 ms1.weight < ms2.weight，则返回 true，反之返回 false，与我们的预期相同。

标准库比较函数

如果只是想实现简单的容器的升序或者降序排列，可以直接使用 C++ 标准库中的比较函数：greater() 和 less()，顾名思义，它们分别实现的是降序和升序排列。以下为使用示例：

vector<int> nums = { 1,3,2,4,5 };
sort(nums.begin(), nums.end(), greater<int>()); //排序得到nums = { 5,4,3,2,1 }
sort(nums.begin(), nums.end(), less<int>()); //排序得到nums = { 1,2,3,4,5 }

由此不难发现，sort 函数中 cmp 的默认参数就是 less<Type>().

简化比较函数

对于一个简单的比较函数，我们可以使用 lambda 表达式来对代码进行简化。（有关 lambda 表达式的内容，可以参考C++ 11 Lambda表达式）

使用 lambda 表达式，我们可以将“自定义比较函数”处的示例简化。

sort(msVector.begin(), msVector.end(), [](const MyStruct& ms1, const MyStruct& ms2){
    return ms1.weight < ms2.weight;
});

例题

题目链接：最大单词长度乘积

对于本题，比较容易想到的是暴力解法，但是直接进行暴力求解将会进行大量的无效计算。因此考虑将数组 words 按其元素的 string 长度从大到小进行排序，并依次两两判断是否是有效解，将有效解保存，在之后的遍历中若当前两 string 长度乘积不大于已保存的解，则立即终止当前循环。

而将数组 words 按其元素的 string 长度从大到小进行排序这一过程，就用到了 sort 函数以及自定义比较函数。

以下为解题代码：

class Solution {
public:
    bool isLegal(const string& s1, const string& s2) {
        for (const auto& ch1 : s1) {
            for (const auto& ch2 : s2) {
                if (ch1 == ch2)
                    return false;
            }
        }
        return true;
    }
    int maxProduct(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& x, const string& y) { return x.size() > y.size(); });
        int maxRes = 0;
        for (size_t i = 0; i < words.size(); i++) {
            for (size_t j = i + 1; j < words.size(); j++) {
                if (maxRes >= words[i].size() * words[j].size())
                    break;
                if (isLegal(words[i], words[j]))
                    maxRes = words[i].size() * words[j].size();
            }
        }
        return maxRes;
    }
};

本文同步发布在我的个人博客：C++比较函数cmp 欢迎访问