std::sort、std::set、std::priority_queue的比较函数的不同写法

在 C++ 标准库中，std::sort、std::set 和 std::priority_queue 的比较函数写法有相似之处，但因各自用途不同（排序算法 vs. 有序容器 vs. 优先级队列），实现细节和注意事项存在差异。以下是三类组件的比较函数写法详解：

---

1. std::sort（排序算法）

用于对序列（如数组、vector）进行一次性排序。比较函数定义元素间的顺序，支持多种写法：

写法示例

• Lambda 表达式（最常用，简洁）：

std::vector<int> vec = {5, 2, 9, 1};
std::sort(vec.begin(), vec.end(), [](int a, int b) {
    return a > b; // 降序
});

• 函数对象（仿函数）（可复用逻辑）：

struct Compare {
    bool operator()(int a, int b) const {
        return a < b; // 升序
    }
};
std::sort(vec.begin(), vec.end(), Compare());

• 函数指针（兼容旧代码）：

bool compare(int a, int b) { return a < b; }
std::sort(vec.begin(), vec.end(), compare);

• 标准库预定义比较器（如 std::greater）：

#include <functional>
std::sort(vec.begin(), vec.end(), std::greater<int>());

sort第三个元素是标准库预定义比较器时，需要加()

注意事项

• 比较函数需满足严格弱序（Strict Weak Ordering）：
  • 非自反性：comp(a, a) == false
  • 传递性：若 comp(a, b) && comp(b, c)，则 comp(a, c)
• 默认行为：std::sort 默认使用 operator< 升序排列。

---

2. std::set（有序集合容器）

基于红黑树实现，自动维护元素有序性。比较函数需在声明容器时指定，决定元素的排序和唯一性规则。

写法示例

• 重载 < 运算符（内置排序）：

struct Person {
    std::string name;
    int age;
    bool operator<(const Person& other) const {
        return age < other.age; // 按年龄升序
    }
};
std::set<Person> people; // 自动按年龄排序

• 自定义函数对象（显式指定规则）：

struct CompareByHeight {
    bool operator()(const Person& a, const Person& b) const {
        return a.height > b.height; // 按身高降序
    }
};
std::set<Person, CompareByHeight> people;

• Lambda 表达式（需结合 decltype）：

auto cmp = [](const Person& a, const Person& b) { 
    return a.name < b.name; // 按名字字典序
};
std::set<Person, decltype(cmp)> people(cmp);

• 函数指针（需注意生命周期）：

bool compare(const Person& a, const Person& b) {
    return a.age > b.age;
}
std::set<Person, decltype(&compare)> people(compare);

注意函数指针类型的decltype需要加上&做推断

注意事项

• 比较函数需保证：相同元素返回 false（否则去重失效）。
  • 例：若 a.id == b.id，必须返回 false。
• 底层红黑树依赖比较函数维护有序性，复杂度为 O(log n)。

---

3. std::priority_queue（优先级队列）

基于堆实现，始终返回优先级最高的元素。比较函数定义“优先级高低”（默认大顶堆）。

写法示例

• 函数对象（推荐）：

struct Task {
    int priority;
    std::string name;
};
struct TaskComparator {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority; // 大顶堆（高优先级在前）
    }
};
std::priority_queue<Task, std::vector<Task>, TaskComparator> pq;

• Lambda 表达式（需显式指定类型）：

auto cmp = [](const Task& a, const Task& b) {
    return a.priority > b.priority; // 小顶堆（低优先级在前）
};
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq(cmp);

• 标准库比较器（如 std::greater）：

// 小顶堆（最小元素在顶部）
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

• 函数指针（需完整声明类型）：

bool compare(const Task& a, const Task& b) {
    return a.priority < b.priority;
}
std::priority_queue<Task, std::vector<Task>, decltype(&compare)> pq(compare);

注意函数指针类型的decltype需要加上&做推断

注意事项

• 比较逻辑反转：
  • 返回 true 表示 a 优先级低于 b（b 应更靠近堆顶）。
• 默认行为：std::priority_queue<T> 使用 std::less<T> 实现大顶堆。

---

🔍 三者的关键区别

特性	std::sort	std::set	std::priority_queue
用途	一次性排序	自动排序+去重	动态优先级管理
底层结构	无（算法）	红黑树	堆（默认 vector）
比较函数作用	定义排序规则	定义排序和唯一性	定义优先级高低
默认比较器	std::less（升序）	std::less（升序）	std::less（大顶堆）
时间复杂度	O(n log n)	插入/查找 O(log n)	插入/删除 O(log n)

通用注意事项

1. 严格弱序：所有比较函数必须满足数学上的严格弱序条件。

2. 参数类型：推荐使用 const T& 避免拷贝开销。

3. 自定义对象：若未重载 <，必须显式提供比较函数。

4. 比较函数为普通函数时，为什么需要声明为 static？

   当比较函数作为类的非静态成员函数时，必须声明为 static，否则会导致编译错误。原因如下：

   （1）非静态成员函数的依赖性

   非静态成员函数隐式依赖类的实例（通过 this指针），而标准库算法（如 std::sort）或容器（如 std::set）在调用比较函数时无法绑定对象实例。若直接传递非静态成员函数，编译器会报错：invalid use of non-static member function

   （2）静态成员函数的独立性

   static成员函数不依赖对象实例（无 this指针），可直接通过类名或函数指针调用，满足标准库对比较函数的调用要求

通过灵活组合上述写法，可高效实现各类排序和优先级逻辑。实际开发中，Lambda 表达式因简洁性最常用，而函数对象适合复杂或需复用的场景。

普通函数和类的static函数可以隐式转换为函数指针，不需要加&，不传类的对象进去。
类的成员函数不能隐式转换为函数指针，需要显示加&，且需要将类名传递