Skip to content

Latest commit

 

History

History
297 lines (217 loc) · 10.2 KB

cppCustomCompareTricks.md

File metadata and controls

297 lines (217 loc) · 10.2 KB
Raw

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

因为是“速记”，难免会有不完善的地方。这篇笔记咱日后应该还会进行补充。

关于sort的比较函数

void sort( RandomIt first, RandomIt last, Compare comp );

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

自定义sort比较函数

comp(a,b)函数的返回值是一个bool值，当返回值为true时不改变元素顺序，反之则需要调换元素。

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

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

也就是说如果a < b时有comp(a,b)=true成立，就是期待程序把小元素放在前面。

#include <iostream>
#include <algorithm>

using namespace std;

bool ascending(int a, int b) // 升序排序，让小元素放在前面
{
    // 把a看作序列中前一个元素，b看作后一个元素
    return a < b; // 如果返回true就说明a<b成立，a是较小的元素
};

bool descending(int a, int b) // 降序排序，让大元素放在前面
{
    // 把a看作序列中前一个元素，b看作后一个元素
    return a > b; // 如果返回true就说明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)
    {
        // a>b的时候才返回true, 期待a是较大的元素。
        // 把较大的元素放在前面，降序排序
        return data > obj.data; 
    }
};

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这些元素有序的容器都可以自定义比较规则，常用的有以下两种途径:

  1. 自定义比较器类(Comparator Class)

  2. 重载运算符(缺省比较器类)

自定义比较器类

在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就是后一个位置的元素:

  1. std::less中，lhs < rhs成立的时候返回true，期待lhs是较小的元素，也就是前一个元素是较小的，因此是升序排序。

  2. std::greater中，lhs > rhs成立的时候才返回true，期待lhs是较大的元素，也就是前一个元素是较大的，因此是降序排序。

很显然，和sort函数的默认比较函数一样，有序容器都是默认升序排序(std:less)的。

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

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int test[10] = {4, 1, 3, 7, 5, 8, 2, 9, 6, 10};
    // 注意这里创建了greater对象，sort函数调用greater对象的()运算符重载方法
    sort(test, test + 10, greater<int>()); 
    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 a.data > b.data; // 前一个元素 > 后一个元素时才返回true
    }
};

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的元素比较规则是略显“另类”的:

  1. 默认情况下(std::less类)，优先队列中的元素出队后是呈降序排列的，即大的元素在队头，是一个大根堆。

  2. 如果使用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模板类来进行比较：

  1. 默认升序排列。

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

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，期待前一个元素更大，即降序排列
    }
};

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;
}

总结

  1. 把比较函数的形参(a,b)中的a看作序列中前一个位置的元素，b看作序列中后一个位置的元素，方便理解。

  2. 无论是sort函数的比较函数comp(a,b)还是比较器类的重载方法operator()(a,b):

    • 返回true时，不会改变a和b的顺序；
    • 而返回false时，会改变a和b的顺序。

    比如在默认情况下实现升序排列，a在序列中的位置小于b且满足条件a<b时，返回true，不会改变a和b的顺序；而当a在序列中的位置大于b时则不满足条件，会改变a和b的顺序。

  3. 在缺省比较函数/比较器类的时候，可以活用待比较对象的运算符重载方法。具体重载哪个运算符需要根据具体的实现来确定。

    比如容器默认采用比较器类std::less，其内部调用待比较对象的<运算符。

  4. 优先队列容器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