本文将简单介绍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 欢迎访问

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐