前言

c++拥有强大的STL，在对复杂的数据结构排序时只需要自定义去比较函数，然后放到容器内调用api即可。

本该是很简单的东西，但我之前一直无法记住升序以及降序两种方向该分别怎么写，总是会搞混，每次都得现场Google。终于下定决心要在今天把它彻底搞定。

自定义排序的三种比较器形式

比较函数

STL中的sort函数已经为我们提供了排序算法的框架，我们唯一要做的决定就是对于两个元素a和b，谁在前、谁在后？

sort函数的一个原型

1
2

void sort(_RandomAccessIterator __first, _RandomAccessIterator __last);//无比较器， 升序排序， 会调用<进行元素比较, 小的会放前面
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp);//传入比较器， 前后顺序由比较强返回值决定

在sort函数中这即为第三个参数：比较器

比较函数的基本形式:

1	bool comp(const type& a, const type& b);

一般而言形参的形式为const、引用类型（当然不写也可以，只是这样更安全、效率更高）。

而返回值于a、b的前后关系是返回true时， a在前面; 返回false时, b在前面.

如

1
2
3

bool comp(const int &a, const int &b) {
    return a < b;
}

返回值为true时， a在前面，且a<b，所以会是升序排序。

所以更透彻的讲，比较函数的内容其实是a要想排在b前面所要满足的条件

简单小例子

若用pair<string, int> 存储着若干个学生的name和score信息，要对这些学生进行排序，

要求：

按分数从高到低
分数相等时按名字字典序排列

很容易的可以得到比较函数为

bool cmp(const pair<string, int> &a, const pair<string, int> &b) {
	if(a.second != b.second) {
		return a.second > b.second;
	}
	return a.first < b.first;
}

lambda表达式

比较函数在大多场景下可能仅需使用一次，因此我们可以用lambda表示式来简写

如

1
2
3

sort(data.begin(), data.end(), [](const type& a, const type& b) -> bool {
        //judge something
    });

重载<运算符

有时候我们会用结构体或类来定义较为复杂的数据结构，要对它进行自定义排序除了使用比较函数外，还可以用重载运算符的方式。

以上面的学生例子举例

struct stu {
    string name;
    int score;

    bool operator < (const stu& b) const {
        if(score != b.score) {
            return score > b.score;
        }
        return name < b.name;
    }
};

上述代码重载了stu类的<运算符，和比较函数不同的时只有一个参数，但其实只不过是a参数变成了当前的结构体。

由于sort函数默认为升序, 会把用<比较的两个函数中小的放前面，所以函数体编写思想和比较函数完全一致：写入要把a放到前面满足的条件。

函数对象比较器——重载()

其实就是定义一个结构体或类作为比较器，重载(), 这样类名+()就成为了比较函数。

struct stu {
    string name;
    int score;

};

struct cmp {
    bool operator() (const stu& a, const stu& b) {
        if(a.score != b.score) {
            return a.score > b.score;
        }
        return a.name < b.name;
    }
};

int main() {
    vector<stu> a{{"abc", 100}, {"acb", 100}};
    sort(a.begin(), a.end(), cmp());
    for(const auto& i : a) {
        cout << i.name << " " << i.score << endl;
    }
}

容器应用

STL用两种比较对象来指代排序的两种方向，分别是less和greater分别使用<和>，对应升序和降序。在众容器中都默认使用less，所以结构体要使用默认排序需要重载小于运算符。

也可以显示指出方向，如以下代码对数组进行了降序排序。

int main() {
    vector<int> a{3, 8, 3, 2, 4};
    sort(a.begin(), a.end(), greater<>());//重载了< / >运算符， 即可使用less<> / greater<>
}

要注意的是在set， priority_queue这样的容器不能用比较函数的方式，只能够使用重载的方式实现。

以及比较反人类的是当priority_queue使用less时其实是大根堆，使用greater<>才是小根堆。

struct stu {
    string name;
    int score;

    bool operator < (const stu & b) const {
        if(score != b.score) {
            return score > b.score;
        }
        return name < b.name;
    }
};

int main() {
    priority_queue<stu, vector<stu>> heap;
    heap.push({"a", 100});
    heap.push({"b", 100});
    heap.push({"c", 110});
    while(!heap.empty()) {
        cout << heap.top().name << " " << heap.top().score << endl;
        heap.pop();
    }
}

//输出结果
/*
b 100
a 100
c 110

*/

trudbot

一文搞定c++自定义排序

前言

自定义排序的三种比较器形式

比较函数

重载<运算符

函数对象比较器——重载()

容器应用