c++ - C++中比较器的使用

Question

以下是合并 k 个排序列表的 c++ 代码。但是我在阅读前 4 行代码时感到困惑。我知道它的作用只是混淆了它是如何做到的。谁能给我解释一下这些台词？

为什么要使用结构体？“运算符”后面的“()”是什么？为什么使用“>”而不是“<”，因为包括结果列表在内的所有列表都是按升序排列的？

struct compare {
    bool operator() (ListNode* &left, ListNode* &right) {
        return left->val > right->val;
    }
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *, vector<ListNode *>, compare> heap;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i]) heap.push(lists[i]);
        }
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (!heap.empty()) {
            ListNode *min = heap.top();
            heap.pop();
            cur->next = min;
            cur = min;
            if (min->next) {
                heap.push(min->next);
            }
        }
        return dummy->next;
    }
};

Answer 1

您的struct compare 就是所谓的仿函数 或函数对象。

struct compare
{
  bool
  operator() (const ListNode& left, const ListNode& right) const
  {
    return left.val > right.val;
  }
};

void
example_usage(const ListNode& left, const ListNode& right, const compare cmp)
{
  if (cmp(left, right))
    std::cout << "left is greater" << std::endl;
  else
    std::cout << "right is greater" << std::endl;
}

(我更改了签名，因为使用对指针的引用并使这些非 const 打扰了我太多。)

在许多情况下，它是使用函数指针的一种方便的替代方法。最重要的是，当在模板中使用时(如在您的示例中)，编译器通常能够内联对运算符 () 的调用。使用函数指针这不是那么容易。

尚不清楚这是否与您的示例相关，但一般来说，仿函数的优点是可以在任何地方(也在函数体内)声明它，而函数只能在全局范围内或作为类成员声明。这允许使用仿函数更好地封装。从 C++11 开始，我们将 lambdas 作为另一种选择:

auto cmp = [](const ListNode& left, const ListNode& right)->bool{
    return left.val > right.val;
};

它可以像仿函数一样使用。 (在幕后，如果你给它一个 lambda 表达式，编译器很可能会创建一个仿函数。)