C++ STL中std::greater、std::less与自定义比较器

在编程过程中，通常需要用到自定义排序，这时候可以用到STL中提供的std::greater和std::less，或者自定义比较器。

一、std::greater与 std::less

std::greater与std::less是定义在<functional>头文件中的函数对象，它们通过重载operator()来提供二元比较能力。这意味着它们既可以像类型一样用于模板参数，也可以像函数一样被调用。

以下是它们的基本模板结构：

// std::greater 定义
template <class T = void>
struct greater {
    constexpr bool operator()(const T& lhs, const T& rhs) const {
        return lhs > rhs;
    }
};

// std::less 定义
template <class T = void>
struct less {
    constexpr bool operator()(const T& lhs, const T& rhs) const {
        return lhs < rhs;
    }
};

从 C++14 开始，引入了"透明比较器"特性。标准库为模板参数为 void 的情况（即省略参数写作std::greater<>或std::less<>时）提供了专门的特化版本，从而支持异构类型的自动推导。

std::sort(vec.begin(), vec.end(), std::greater<>{});

对于排序：

• std::greater可作为降序比较器（从左到右遍历下标时，数组元素是从大到小）
• std::less可作为升序比较器（从左到右遍历下标时，数组元素是从小到大）

对于建堆：

• std::greater变为小顶堆（堆顶元素是最小值）
• std::less变为大顶堆（堆顶元素是最大值）

（因为C++的priority_queue默认把比较结果为true的元素往堆底放。greater意味着父节点大于子节点时返回true，导致大元素下沉，小元素浮到堆顶。）

从上文基本模板结构可以看出，本质上std::greater与std::less都是通过函数调用运算符operator()实现二元比较能力，进而实现排序、建堆。

典型应用场景

1. std::sort中的降序排序

#include <vector>
#include <algorithm>
#include <functional>

std::vector<int> scores = {85, 92, 78, 96, 88};

// 使用std::greater实现降序排列
std::sort(scores.begin(), scores.end(), std::greater<>{});
// 结果: 96, 92, 88, 85, 78

2. priority_queue构建最小堆

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

// 构建最小堆
std::priority_queue<int, std::vector<int>, std::greater<>> min_heap;

min_heap.push(3);
min_heap.push(1);
min_heap.push(4);

while (!min_heap.empty()) {
    std::cout << min_heap.top() << " "; // 输出: 1 3 4
    min_heap.pop();
}

3. set实现降序集合

#include <iostream>
#include <set>
#include <functional>

// 创建一个按降序排列的整数集合
std::set<int, std::greater<>> desc_set = {3, 1, 4};

for (int x : desc_set) {
    std::cout << x << " "; // 输出: 4 3 1
}

扩展：C++20的std::ranges::greater与std::ranges::less

扩展内容需C++20+标准支持

C++20在<functional>头文件中引入了std::ranges::greater和std::ranges::less。这两个比较器专为ranges算法设计，并非传统std::greater<>和std::less<>的简单复用。其底层基于C++20 Concepts机制，实现了更严格的类型约束。

核心特点是：只有当参与比较的类型满足std::totally_ordered_with概念时，相关算法才能顺利编译。这样不仅使错误信息更加直观易懂，而且自然而然支持ranges算法中的投影（Projection）功能。

使用示例：

1. 配合std::ranges::sort使用

#include <vector>
#include <algorithm>
#include <functional>

std::vector<int> nums = {3, 1, 4, 1, 5};

// C++20 Ranges + 预实例化比较器
std::ranges::sort(nums, std::ranges::greater{});
// 结果: 5, 4, 3, 1, 1

// 等价于传统写法
// std::ranges::sort(nums, std::greater<>{});

2. 配合 std::ranges::min_element 等算法

// 直接返回最小值的迭代器，无需写std::less<>{}
auto min_it = std::ranges::min_element(nums);

3. 与投影（Projection）结合

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}};

// 按age降序排序：比较器 + 投影
std::ranges::sort(people,
                  std::ranges::greater{},
                  &Person::age);  // 投影：提取age字段比较
// 结果: Alice(30), Bob(25)

二、自定义比较器

当面对复杂数据类型（如结构体）或多字段排序需求时，std::less 和 std::greater 就显得力不从心了。此时我们需要自定义比较函数。任何满足严格弱序（Strict Weak Ordering）的可调用对象都可以作为STL的比较器。

即比较规则要满足：

• 反自反性：comp(a,a)必须为false。
• 非对称性：若 comp(a,b)为true，则comp(b,a)必须为false。
• 传递性：若 comp(a,b)和comp(b,c)为true，则comp(a,c)必须为true。
• 传递的不可比性：如果!comp(a,b) && !comp(b,a)，且!comp(b,c) && !comp(c,b)，那么 !comp(a,c) && !comp(c,a)。

有下面几种方式可以自定义比较器：

1. 函数对象（仿函数）

struct CompareById {
    bool operator()(const Student& a, const Student& b) const {
        return a.id < b.id; // 按学号升序
    }
};
std::sort(students.begin(), students.end(), CompareById{});

2. 通过元素类型的运算符重载

struct Node {
    int chinese, math, english, sum;
    bool operator<(const Node& b) const {
        if (sum != b.sum) return sum < b.sum;
        if (chinese != b.chinese) return chinese < b.chinese;
        if (math != b.math) return math < b.math;
        return english < b.english;
    }
};
priority_queue<Node> s;
// 实现优先队列传递结构体变量

3. Lambda表达式

// 按成绩降序
std::sort(students.begin(), students.end(),
    [](const Student& a, const Student& b) {
        return a.score > b.score;
    });

4. 普通函数

// 按姓名升序
bool compareByName(const Student& a, const Student& b) {
    return a.name < b.name;
}
std::sort(students.begin(), students.end(), compareByName);