【速记】C++ STL自定义排序

这篇笔记咱日后应该还会进行补充。

关于sort的比较函数

STL的algorithm库中的sort函数，可以接受一个cmp函数作为第三个参数，用来指定排序的规则。

自定义sort比较函数

cmp(a,b)函数的返回值是一个bool值，当返回值为true时不改变元素顺序。

可以把其中的a看作序列中前一个元素，b看作后一个元素:

如果a < b的时候cmp(a,b)=true，那么a就会被放在b前面，排序呈升序。
如果a < b的时候cmp(a,b)=false，那么b就会被放在a前面，排序呈降序。

也就是说cmp(a,b)=true的时候，有a < b成立，期望程序把a放在b前面。

#include <iostream>
#include <algorithm>
using namespace std;
bool ascending(int a, int b) // 升序排序，让a先于b
{
    // 把a看作序列中前一个元素，b看作后一个元素
    return a < b; // 如果返回true就说明a<b成立，期望程序把a放在b前面
};
bool descending(int a, int b) // 降序排序，让b先于a
{
    // 把a看作序列中前一个元素，b看作后一个元素
    return b < a; // 如果返回true就说明b<a成立，期望程序把b放在a前面
};
int main()
{
    int test[10] = {9, 4, 2, 5, 1, 7, 3, 6, 8, 10};
    sort(test, test + 10, ascending);
    for (int i = 0; i < 10; i++)
        cout << test[i] << " ";
    // Ouput: 1 2 3 4 5 6 7 8 9 10
    cout << "\n";
    sort(test, test + 10, descending);
    for (int i = 0; i < 10; i++)
        cout << test[i] << " ";
    // Ouput: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

缺省sort比较函数

默认情况下，sort函数会使用<运算符作比较。(也就是默认升序排序)

这个时候如果要自定义排序规则，可以重载<运算符。

#include <iostream>
#include <algorithm>
using namespace std;
struct Node
{
    int data;
    bool operator<(const Node &obj)
    {
        return data > obj.data; // a>b的时候返回true, 相当于cmp(b,a)=true, 期望b排在a前面
    }
};
int main()
{
    Node test[10] = {{1}, {4}, {2}, {5}, {9}, {7}, {3}, {6}, {8}, {10}};
    sort(test, test + 10);
    for (int i = 0; i < 10; i++)
        cout << test[i].data << " ";
    // Output: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

自定义容器内元素排序

priority_queue、map、set这些常见容器都可以自定义比较规则，常用的有以下两种途径:

自定义比较类
重载运算符

自定义比较类

在cppreference页面可以看到，这类元素有序的容器都有个默认的Compare比较类。比如priority_queue的声明:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

多观察几个容器的声明，能发现默认的Compare比较类都是std::less，定义大概是这样:

template<class T> struct less
{
    // 这里其实是重载了()运算符，因此在使用的时候可以像函数一样调用
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs < rhs;
    }
};

标准库中还有另一个比较类std::greater，定义如下:

template<class T> struct greater
{
    // 这里其实是重载了()运算符，因此在使用的时候可以像函数一样调用
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs > rhs;
    }
};

从数组排序的角度看，lhs就是前一个元素，rhs就是后一个元素:

std::less中，lhs < rhs成立的时候返回true，期望程序把lhs放在rhs前面，因此是升序排序。
std::greater中，lhs > rhs成立的时候才返回true，期望程序把rhs放在lhs前面，因此是降序排序。

很显然，这里和sort函数的默认比较函数一样都是默认升序排序的。

因为重载了运算符()，我实际上可以把【比较类】的对象作为比较函数传入sort方法:

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int test[10] = {4, 1, 3, 7, 5, 8, 2, 9, 6, 10};
    sort(test, test + 10, greater<int>()); // 注意这里调用的是greater对象的()运算符重载方法
    for (int i = 0; i < 10; i++)
        cout << test[i] << " ";
    // Output: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

值得注意的是，这里首先调用的是greater类的默认构造方法，返回一个对象并传递给sort函数。sort函数内部调用对象(a,b)时调用的是运算符()重载方法来进行比较。

模仿greater和less模板类的定义，我们也可以自己定义比较类:

#include <iostream>
#include <algorithm>
using namespace std;
struct Node
{
    int data;
};
struct MyGreater
{
    // a是序列中前一个元素，b则是后一个元素
    bool operator()(const Node &a, const Node &b) const
    {
        return b.data < a.data; // a<b时返回false，期待程序把b排在a前面
    }
};
int main()
{
    Node test[10] = {{4}, {1}, {3}, {7}, {5}, {8}, {2}, {9}, {6}, {10}};
    sort(test, test + 10, MyGreater());
    for (int i = 0; i < 10; i++)
        cout << test[i].data << " ";
    // Output: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

优先队列的比较类

在这几种STL容器中，优先队列priority_queue的元素比较规则是略显“另类”的:

默认情况下(std::less类)，优先队列中的元素是降序排列的，即大的元素在队头，是一个大根堆。
如果使用std::greater类，则优先队列中的元素是升序排列的，即小的元素在队头，是一个小根堆。

这里和之前的排序不同的地方就在于：比较方法形参的意义不同。

拿std::greater举例:

template<class T> struct greater
{
    // 这里其实是重载了()运算符，因此在使用的时候可以像函数一样调用
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs > rhs;
    }
};

在sort函数、map、set容器中，lhs代表序列中前一个元素，rhs代表序列中后一个元素。
而在priority_queue中，lhs代表新插入的节点，rhs代表这个节点的父节点。

lhs>rhs时就是期望父节点小于子节点，即构成小根堆，因此堆顶元素总是堆中最小的，所以从优先队列中取出的元素也是从小到大的，即升序排列。

往堆中插入新节点时是插入在最后一个叶子节点的位置的。

重载运算符

sort函数中可以缺省排序函数。在创建容器对象时，我们也可以缺省比较函数。

在缺省比较函数的情况下，STL容器默认采用std::less模板类来进行比较：

默认升序排列。
对于优先队列来说，出队元素呈降序排列。

std::less类的重载方法中一样也是调用了对象的<运算符进行比较，因此我们也可以重载<运算符来实现自定义的比较规则。

#include <iostream>
#include <algorithm>
using namespace std;
struct Node
{
    int data;
    // std::less中调用了这里的<运算符重载方法
    bool operator<(const Node &b) const
    {
        return data > b.data; // a>b时返回true，期待b放在a前面
    }
};
int main()
{
    Node test[10] = {{4}, {1}, {3}, {7}, {5}, {8}, {2}, {9}, {6}, {10}};
    sort(test, test + 10);
    for (int i = 0; i < 10; i++)
        cout << test[i].data << " ";
    // Output: 10 9 8 7 6 5 4 3 2 1
    return 0;
}

总结

把比较函数的形参(a,b)中的a看作序列中前一个元素，b看作序列中后一个元素，方便理解。
无论是sort函数的比较函数cmp(a,b)还是比较类的重载方法operator()(a,b):
- 返回true时，不会改变a和b的顺序；
- 而返回false时，会改变a和b的顺序。
比如在默认情况下，a在序列中的位置小于b时，满足条件a<b，返回true，不会改变a和b的顺序；而当a在序列中的位置大于b时，不满足条件，会改变a和b的顺序。借此实现升序排列。
在缺省比较函数/比较类的时候，可以活用待比较对象的运算符重载方法。具体重载哪个运算符需要根据具体的实现来确定。

比如容器默认采用比较类std::less，其内部调用待比较对象的<运算符。
优先队列容器priority_queue的比较元素的含义是不同的，重载方法operator()(a,b)中前一个元素a指的是新插入的元素，而后一个元素b指的是这个元素的父节点。
- 这里仍然是比较方法返回true时不会改变元素顺序。
比如在默认情况下，新插入的元素a的值小于父节点b的值，满足条件a<b，返回true，不会改变a和b的位置；而当新插入的元素a的值大于父节点b的值，不满足条件，会改变a和b的位置。借此维持大根堆的堆序性。

参考文章

https://blog.csdn.net/sandalphon4869/article/details/105419706

标签定义, 排序, 自定义