🎈 原创📅 发表🕰️ 更新📁 学习记录⌛ 12 分钟读完 (大约1846个字)👀 0次访问

关于C++中的自定义排序

实际开发中经常会有需要对当前的数据结构进行排序的场景，最方便的情况是直接调用#include <algorithm>中的sort方法。但是大部分情况下使用的都不是默认的数据结构，直接在上面调用sort很难达到理想的效果。

同时最近刷题的时候也经常碰到需要在排好序的数据上做下一步算法的情况。所以针对C/C++中自定义排序的各种实用的方法在在这边进行一下简单的汇总。

给定一个场景：有一个类表示学生的信息，所有的学生信息用一个vecotr容器来存储，现在需要对容器中的数据排序。排序的规则是：

  • 成绩高的在前面
  • 成绩相同的名字字典序排序
  • 名字相同的按id从小到大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Student {
    public:
        long long id;
        std::string name;
        long long Chinese, Math, English, Total;

    public:
        Student(long long i, std::string n, long long c, long long m,
                long long e, long long t)
            : id(i),
              name(n),
              Chinese(c),
              Math(m),
              English(e) {
            Total = Chinese + Math + English;
        }
};

std::sort 函数解释

std::sort的第三个参数接受一个谓词(二元谓词)，也就是一个可调用的东西，同时接受两个参数，返回一个bool值。

也就是说可以传入一个函数对象/仿函数，或者直接是一个函数的名字。具体的解释在下面的方法中展开。

这个二元谓词接受的两个对象，假设s1和s2，排序的规则如下：

  • 如果返回true：s1在s2前面
  • 如果返回false：s1在s2后面

方法1: 使用规则函数。

另外编写一个规则的函数，在调用时将函数名作为第三个参数传入

一种符合直觉的写法

1
2
3
4
5
6
7
8
9
10
11
12
13

bool cmp_version0(const Student &s1, const Student &s2)
{
    if (s1.Total > s2.Total)
        return true;
    else if (s1.Total == s2.Total and s1.name < s2.name)
        return true;
    else if (s1.Total == s2.Total and s1.name == s2.name and s1.id < s2.id)
        return true;
    else
        return false;
}

更好的一种方式

1
2
3
4
5
6
7
8
9
10

bool cmp_version1(const Student &s1, const Student &s2) {
    if (s1.Total != s2.Total)
        return s1.Total > s2.Total;
    else if (s1.name != s2.name)
        return s1.name < s2.name;
    else
        return s1.id < s2.id;
}

也可以在比较函数中通过tuple的数据结构省略比较的逻辑，因为tuple内置了重载的运算符，比较的方式是按照声明的顺序，自动发生比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool cmp_version2(const Student &s1, const Student &s2) {
    // return std::make_tuple(s1.Total, s1.name, s1.id) <
    // std::make_tuple(s2.Total, s2.name, s2.id);  // s1.Total 和 s2.Total 的顺序会相反

    return std::make_tuple(s2.Total, s1.name, s1.id) <
           std::make_tuple(s1.Total, s2.name, s2.id); // 交换需要相反排序顺序的前后两个元素的顺序，因为决定排序的是返回
                                                      // true 还是 false

    // 可以使用另一种tie函数，效果与make_tuple是一样的
    return std::tie(s2.Total, s1.name, s1.id) <
           std::tie(s1.Total, s2.name,s2.id); 
    // tie里面只能变量不能常量，而make_tuple可以，要看情况使用
}

实际使用上就可以直接传入该规则：

std::sort(students.begin(), students.end(), cmp_version2);

方法2：重载小于运算符

排序中主要使用小于运算符发生比较逻辑

常用的重载小于运算符的方法：

  • 成员函数
  • 非成员函数

成员函数

重载成员函数的大概写法：

1
2
3
4
5
6
7
8
class T {

public:
    bool operator<(const T& t) const { // 传入参数常引用，避免拷贝。const 限定符保证函数内不会对传入的实参修改。以成员函数的形式重载运算符都要加上后面的const
        ...
    }
};

成员函数的形式中比较的另一个对象是用this指针表示的，是调用这个小于运算符的对象

所以代码的逻辑设计为：

this指针的对象是排序后在前面的，传入的是排序后在后面的

重载后的类: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Student {
    public:
        long long id;
        std::string name;
        long long Chinese, Math, English, Total;

    public:
        Student(long long i, std::string n, long long c, long long m,
                long long e, long long t)
            : id(i),
              name(n),
              Chinese(c),
              Math(m),
              English(e) {
            Total = Chinese + Math + English;
        }

        bool operator<(const Student &s) const {
            return std::tie(s.Total, this->name, this->id) <
                   std::tie(this->Total, s.name, s.id);
            // this 可以省略
            return std::tie(s.Total, name, id) < std::tie(Total, s.name, s.id);
        }
};

重载后可直接调用

std::sort(students.begin(), students.end());

非成员函数的方式

返回true的情况下 s1 表示排序后在前面的，s2是排序后在后面的

1
2
3
4
5
6

bool operator<(const Student &s1, const Student &s2) {
    return std::tie(s2.Total, s1.name, s1.id) <
           std::tie(s1.Total, s2.name, s2.id);
}

方法3：函数对象 / 仿函数

假设现在有这样一种需求：达到某种分数的排前面，没到的排后面

排序规则可以这样写：

1
2
3
4
5

bool cmp(const Student &s1, const Student &s2, long long score) {
    return s1.Math >= score and s2.Math < score;
}

但是std::sort只接受二元谓词，这样的函数无法作为参数传入。此时需要函数对象作为解决方法。

函数对象 / 仿函数 :

  • 重载了调用运算符的类
  • lambda表达式

函数对象类

对于重载调用运算符，常用的重载写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct T {
    int operator() (long long v) const
    {
        return v < 0 ? -v : v;
    }
};

int main() {
    T p;
    std::cout << p(-5) << ", " << p(0) << ", " << p(5) << std::endl;
    return 0;

    // 等价的lambda表达式
    auto p = [](long long v){return v < 0 ? -v: v};
    std::cout << p(-5) << ", " << p(0) << ", " << p(5) << std::endl;

}

相比于比较函数，仿函数，因为是类，可以有数据成员，所以可以把score作为成员，解决上述需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class cmp {
    public:
        long long score;
        cmp(long long s) : score(s) {}
        bool operator()(const Student &s1, const Student &s2) const {
            return s1.Math >= score and s2.Math < score;
        }
};

int main() {
    long long score;
    std::cin >> score;
    cmp c(score);
    sort(students.begin(), students.end(), c);
    sort(students.begin(), students.end(), cmp(score)); // 或者这样写
    // 传入的是类构造的一个对象

    return 0;
}

如果是原来的需求

1
2
3
4
5
6
7
8
9

struct cmp
{
        bool operator()(const Student &s1, const Student &s2) const {
            return std::tie(s2.Total, s1.name, s1.id) <
                   std::tie(s1.Total, s2.name, s2.id);
        }
};

Lambda 表达式

Lambda是一种匿名的函数

[捕获列表] (参数列表) -> 返回类型 {函数体}

返回类型可以自动推断，基本上不写
[捕获列表] (参数列表) -> {函数体}

1
2
3
4
5
6
7
8
9
10
11
12
13
auto cmp_lambda = [](const Student &s1, const Student &s2) {
    return std::tie(s2.Total, s1.name, s1.id) <
           std::tie(s1.Total, s2.name, s2.id);
};

std::sort(students.begin(), students.end(), cmp_lambda);

// 或者直接写在里面
std::sort(students.begin(), students.end(),
          [](const Student &s1, const Student &s2) {
              return std::tie(s2.Total, s1.name, s1.id) <
                     std::tie(s1.Total, s2.name, s2.id);
          });

如果是带有score的排序问题，可以使用值捕获

1
2
3
4
std::sort(students.begin(), students.end(),
          [score](const Student &s1, const Student &s2) {
              return s1.Math >= score and s2.Math < score;
          });

也可以同时引用捕获一个num计数调用了多少次

1
2
3
4
5
6
long long num = 0;
std::sort(students.begin(), students.end(),
          [score, &num](const Student &s1, const Student &s2) {
              ++num;
              return s1.Math >= score and s2.Math < score;
          });

对于简单的数据结构的逆转排序方法

可以使用一些内置的函数对象

1
2
3
4
5

std::vector<long long> v = {5, 4, 7, 9, 3, 2, 0, 1};
std::sort(v.begin(), v.end(), greater<long long>());
std::sort(v.begin(), v.end(), less<long long>());

利用反向迭代器

1
2
3
4
5

std::vector<long long> v = {5, 4, 7, 9, 3, 2, 0, 1};
std::sort(v.begin(), v.end());
std::sort(v.rbegin(), v.rend()); // 反向，结果从大到小

关于C++中的自定义排序

https://blog.counpy.me/2025/01/关于C-中的自定义排序/

作者

Jhuoer Yen

发布于

2025-01-11

更新于

2025-01-11

许可协议

🔖 #

喜欢这篇文章？打赏一下作者吧

评论

分类

标签

AVL1
Ajax2
BFS2
C++41
CSS5
DFS1
Express2
HTML3
JavaScript1
Javascript7
Linux7
Lua1
Markdown1
Nginx1
Node.js4
PTA1
PyTorch1
Python5
Qt3
React5
TOEFL2
TPO2
Vim3
Vuepress1
anikura2
git2
python3
pytorch2
tarjan1
二分2
二叉树2
二链树1
人工智能1
分治1
力扣1
动态规划4
哈夫曼1
搜索2
数学1
数论2
旅游1
机器学习1
栈1
洛谷21
贪心1
运算符重载1
链表1
高精度2

最新文章

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×