关于C++中排序和建堆的比较规则：std::greater()、std::less()、自定义比较规则-Toy模板网

这篇具有很好参考价值的文章主要介绍了关于C++中排序和建堆的比较规则：std::greater()、std::less()、自定义比较规则。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

排序和建堆的使用方式（自定义为例）

在C++中，排序和建堆的比较规则是通过比较函数或者比较对象来定义的。这通常涉及到使用函数对象（Functor）或者函数指针，以决定元素之间的大小关系。
举例： 利用函数排序

#include <iostream>
#include <vector>
#include <algorithm>

// 自定义比较函数
bool myComparator(int a, int b) {
    return a > b; // 降序排序
}

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 6};

    // 使用自定义比较函数进行降序排序
    std::sort(vec.begin(), vec.end(), myComparator);

    // 输出排序后的结果
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

举例： 利用对象排序，注意sort第三个实参中有括号，是建立临时对象

#include <iostream>
#include <vector>
#include <algorithm>

// 自定义比较对象
struct MyComparator {
    bool operator()(int a, int b) {
        return a > b; // 降序排序
    }
};

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 6};

    // 使用自定义比较对象进行降序排序
    std::sort(vec.begin(), vec.end(), MyComparator());

    // 输出排序后的结果
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

举例： 利用对象建堆，注意优先级队列（本例中为小顶堆）第三个模板参数不带括号

#include <iostream>
#include <queue>

// 自定义比较对象
struct MyComparator {
    bool operator()(int a, int b) {
        return a > b; // 小顶堆，小的元素排在前面
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, MyComparator> minHeap;

    // 插入元素
    minHeap.push(5);
    minHeap.push(2);
    minHeap.push(8);
    minHeap.push(1);
    minHeap.push(6);

    // 弹出并输出元素
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}

结论

如果是排序，less<T>是升序，（从左到右遍历下标，数组元素从小到大）；greater<T>是降序（从左到右遍历下标，元素从大到小）。
如果是建堆，less<T>是大顶堆，greater<T>是小顶堆。

less()、greater()原理

假设比较规则就是comp(a, b)，对于排序来说，左边元素就是前一个a，右边元素就是后一个b；对于建堆，新插入一个元素时，插入到最后一个叶子，这时要整理堆内元素满足大/小顶堆，a代表新插入的结点，b代表它的父节点。
我们写自定义比较规则就可以依照这个规则。
而标准库中的less<T>就是让a比b小，对应排序就是左边比右边小，就是升序；对于建堆就是让新插入节点比它的父结点小，就是大顶堆。
greater<T>相反。

默认都是用less<T>。

自定义规则

这部分参考里的例子写的很好，直接贴过来了。

符合两个条件：
bool：返回值bool
return x<y;：重载<之类的操作符，并且要决定比较什么元素。
PS：建议还要常引用，保险，禁止发生修改要比较的元素可能。

举例：数组
函数：使用时不加括号，加了报错

类的对象：注意，排序时的类必须使用类的对象才对，直接使用类报错。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 重写排序函数
bool cmpfunc(const int &a, const int &b)
{
    return a < b;
    // < 升序; > 降序
}

// 模仿less、greater构建类
struct cmpClass
{
    bool operator()(const int &i, const int &j)
    {
        return (i < j);
    }
}cmpClassObject;		// 注意，排序时的类必须使用类的对象才对，使用类报错。

int main()
{
	// 使用函数
    vector<int> v1 = {2, 3, 1, 6, 2, 5, 4};
    // 使用时不加括号，加了报错
    sort(v1.begin(), v1.end(), cmpfunc);
    for (int i = 0; i < v1.size(); i++)
    {
        cout << v1[i] << " ";
    }
    cout << endl;
    // 1 2 2 3 4 5 6
    
    // 使用类的对象
    vector<int> v2 = {2, 3, 1, 6, 2, 5, 4};
    sort(v2.begin(), v2.end(), cmpClassObject);
    for (int i = 0; i < v2.size(); i++)
    {
        cout << v2[i] << " ";
    }
    cout << endl;
    // 1 2 2 3 4 5 6
    return 0;
}

举例：优先级队列
定义类时同时定义操作符重载函数：操作符重载函数，必须是具体的操作符<之类的，写()报错

自定义类，自定义比较函数：操作符重载函数，必须是具体的操作符<之类的，写()报错

自定义类，自定义包含比较函数的结构体：操作符重载函数，必须是写()

#include <iostream>
#include <queue>
using namespace std;

/******** 定义类时同时定义操作符重载函数 ********/
struct Node1
{
    // 要比较的元素
    int x;
    // 构造函数
    Node1(int x) { this->x = x; }
    // 操作符重载函数，必须是具体的操作符<之类的，写()报错
    bool operator<(const Node1 &b) const
    {
        // 实现less中需要的<,大顶堆
        return x < b.x;
    }
};

/******** 自定义类，自定义比较函数 ********/
struct Node2
{
    // 要比较的元素
    int x;
    // 构造函数
    Node2(int x) { this->x = x; }
};

// 操作符重载函数，必须是具体的操作符<之类的，写()报错
bool operator<(const Node2 &a, const Node2 &b)
{
    // less,大顶堆
    return a.x < b.x;
}

/******** 自定义类，自定义包含比较函数的结构体 ********/
struct Node3
{
    // 要比较的元素
    int x;
    // 构造函数
    Node3(int x) { this->x = x; }
};

struct cmpClass
{
    // 操作符重载函数，必须是写()
    bool operator()(const Node3 &a, const Node3 &b)
    {
        // less,大顶堆
        return a.x < b.x;
    }
};

int main()
{
    /******** 初始化优先级队列的对象p ********/
    // Node1类型，默认使用vector，小顶堆，同 priority_queue<Node1, vector<Node1>, less<Node1> > p;
    priority_queue<Node1> p;

    // 乱序入队
    p.emplace(1);
    p.emplace(3);
    p.emplace(2);

    // 弹出队首
    while (!p.empty())
    {
        cout << p.top().x << " ";
        p.pop();
    }
    cout << endl;
    // 3 2 1

    /******** 初始化优先级队列的对象q ********/
    // 同 priority_queue<Node2> q;
    priority_queue<Node2, vector<Node2>, less<Node2>> q;

    // 乱序入队
    q.emplace(1);
    q.emplace(3);
    q.emplace(2);

    // 弹出队首
    while (!q.empty())
    {
        cout << q.top().x << " ";
        q.pop();
    }
    cout << endl;
    // 3 2 1

    /******** 初始化优先级队列的对象r ********/
    priority_queue<Node3, vector<Node3>, cmpClass> r;

    // 乱序入队
    r.emplace(1);
    r.emplace(3);
    r.emplace(2);

    // 弹出队首
    while (!r.empty())
    {
        cout << r.top().x << " ";
        r.pop();
    }
    cout << endl;
    // 3 2 1
    return 0;
}