RichardYi's Notebook

各种排序问题中比较器的写法

6 min read

排序实际上就是不停地交换元素，来达到我们想要的升序或降序结果，而比较器实际上就是我们自己在定义什么时候需要交换两个元素，当其返回为假时不交换，返回真时交换，即把后一个元素跟前一个元素交换位置

以此题中qsort的比较器为例：

服务器有一批任务需要处理。每个任务有 ID、优先级 (priority) 和 耗时 (cost)。 定义结构体 Task。规则：

  1. 优先级高的任务先执行（数值越大优先级越高）。
  2. 优先级相同，耗时短的先执行。
  3. 如果都相同，ID小的先执行。

其比较器可以写为：

typedef struct {
    int id;
    int priority;
    int cost;
}Task;
 
int cmp(const void *a,const void *b)
{
    Task*t1=(Task*)a;
    Task*t2=(Task*)b;
 
    if(t1->priority!=t2->priority)
    {
        return t1->priority<t2->priority;
    }
    if(t1->cost!=t2->cost)
    {
        return t1->cost>t2->cost;
    }
    return t1->id>t2->id;
}

当返回的值为真时，相当于把b放到a的前面（交换了a和b） 返回值为假时，不改变a，b顺序（不交换a和b）

比如1，5 想要它为降序，则要交换a和b，需要返回值为真

而当return a<b时，返回值为真，qsort（交换了a和b）把5放在1前面，就实现了降序

不妨再看看优先队列中比较器的写法：

struct compare{
    bool operator()(TreeNode*a,TreeNode*b)
    {
        return a->val>b->val;
    }
};

这里我想实现升序排列，思想与上述相同，确定什么时候需要交换两个元素，写出相关的返回值的表达式即可

问题又来了，为什么这里的compare比较器必须写成这种”operator()“的函数名呢，写成随便一个其他的函数名不行吗？

这是因为(from GPT 5.2) 我个人理解为，其主要是因为编译器只能识别operator这种关键字，才能把它当作一个比较器对象来处理

一、cmp 在这里“扮演的角色”是什么？

在这行代码里：

priority_queue<ListNode*, vector<ListNode*>, cmp> pq;

第三个模板参数 cmp 的语义要求是：

一个“比较器类型”，它的对象必须能被“调用” 即：给我两个 ListNode*，我能返回一个 bool

也就是说，priority_queue 内部会写类似这样的代码（伪代码）：

cmp comp;
if (comp(a, b)) {
    ...
}

👉 注意这里：comp(a, b) 这要求 comp 必须像函数一样被调用。

二、C++ 中：什么东西能“像函数一样调用”？

在 C++ 里，能写成：

x(a, b)

只有三种情况：

  1. 函数
  2. 函数指针
  3. 重载了 operator() 的对象

而这里传给 priority_queue 的是：

cmp   // 一个“类型”，不是函数指针

所以唯一合法的方式就是： 👉 让 cmp 成为“函数对象（functor）”

三、什么是函数对象（Functor）？

一个类 重载了 operator() 之后：

struct cmp {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

就可以这样用：

cmp c;
bool x = c(p1, p2);  // 看起来像函数，其实是对象

这正是 priority_queue 想要的东西。

四、为什么不能叫别的名字？比如 compare()？

如果你写成：

struct cmp {
    bool compare(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

那你只能这样调用：

cmp c;
c.compare(a, b);

❌ 但是 priority_queue 不会这么写，它只会写：

c(a, b);

👉 编译器根本不知道你有个 compare()。

五、operator() 是“语法层面的约定”，不是 STL 特有

这一点非常重要：

operator() 不是 priority_queue 发明的 它是 C++ 语言层面定义的“函数调用运算符”

只要你写了：

obj(args...)

编译器就会自动翻译为：

obj.operator()(args...)

六、类比（非常形象）

你可以这样理解：

  • operator+ → 让对象能写 a + b
  • operator[] → 让对象能写 a[i]
  • operator() → 让对象能写 a(x, y)

priority_queue 只认 a(x, y) 这种“函数式调用”。

七、那为什么 STL 不直接用函数指针？

可以，但有三个问题：

  1. 函数指针不能保存状态
  2. 性能略差（不能内联）
  3. 模板无法在编译期充分优化

而函数对象（带 operator()）：

  • 可以内联
  • 可以携带成员变量
  • 是 STL 的核心设计思想

八、总结一句话（考试 / 面试级答案）

priority_queue 要求比较器是一个可调用对象， 在 C++ 中，使一个对象可调用的唯一方式就是重载 operator()， 因此比较器类必须提供 operator()。

Graph View

Backlinks