c++ - 如何在不使用 lambda 表达式的情况下实现特定的比较器？

Question

我从 here 得到以下代码.

class Solution {
public:
  vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<pair<int,int>> result;
    if (nums1.empty() || nums2.empty() || k <= 0)
        return result;
    auto comp = [&nums1, &nums2](pair<int, int> a, pair<int, int> b) {
        return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];};
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> min_heap(comp);
    min_heap.emplace(0, 0);
    while(k-- > 0 && min_heap.size())
    {
        auto idx_pair = min_heap.top(); min_heap.pop();
        result.emplace_back(nums1[idx_pair.first], nums2[idx_pair.second]);
        if (idx_pair.first + 1 < nums1.size())
            min_heap.emplace(idx_pair.first + 1, idx_pair.second);
        if (idx_pair.first == 0 && idx_pair.second + 1 < nums2.size())
            min_heap.emplace(idx_pair.first, idx_pair.second + 1);
    }
    return result;
  }
};

有一行lambda表达式来实现比较器:

auto comp = [&nums1, &nums2](pair<int, int> a, pair<int, int> b) {
        return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];};

pair.first 索引第一个数组 nums1 而 pair.second 索引第二个数组 nums2。

这个比较器比较两对，每对包含两个数组( vector )的索引。如果第一对 (array1[first_pair.first]+array2[first_pair.second]) 的对应数组总和大于第二对，则表达式返回 true。

我的问题是，我们可以使用结构来实现相同的比较器吗？困难的部分是我们如何将这两个数组作为参数传递给比较器。

比较两个对(不是两个数组的索引)的结构可以用这种方式实现:

struct myCompare {
  bool operator() (const pair<int,int> lhs, const pair<int,int> rhs) const
  { return (lhs.first+lhs.second < rhs.first+rhs.second); }
};

但这是比较pair条目的总和。现在我们要比较由对索引的两个数组条目的总和。

Answer 1

您可以在比较器的构造函数中传递数组。

struct myCompare {

  // pass capture variables using constructor
  myCompare(const std::vector<int>& nums1, std::vector<int>& nums2)
  : nums1(nums1), nums2(nums2) {}

  bool operator() (const pair<int,int> lhs, const pair<int,int> rhs) const
  { return (nums1[lhs.first] + nums2[lhs.second] < nums1[rhs.first] + nums2[rhs.second]); }

private:
  const std::vector<int>& nums1;
  const std::vector<int>& nums2;
};

然后像这样使用它:

myCompare comp(nums1, nums2);

priority_queue<pair<int, int>, vector<pair<int, int>>, myCompare> min_heap(comp);