CODEWITHSUNDEEP
c++lambdaparameter-passingoverriding
user3813057
user3813057

Reputation: 911

How to implement a specific comparator without using the lambda expression?

I get the following code from 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;
  }
};

There is one line of the lambda expression to implement the comparator:

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 indexes the first array nums1 while pair.second indexes the second array nums2.

This comparator compares two pairs, where each pair contains the indices of two arrays(vector). The expression returns true if the first pair (array1[first_pair.first]+array2[first_pair.second]) has the corresponding array sum greater than the second pair.

My QUESTION is, can we use a struct to implement the same comparator? The difficult part is how to we pass the two arrays as the arguments to the comparator.

A struct that compare two pair (not the index of two arrays) can be implemented in this way:

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

But this is to compare the sum of the pair entries. Now we want to compare the sum of two array entries indexed by the pairs.

Upvotes: 1

Views: 102

Answers (2)

ivan_onys
ivan_onys

Reputation: 2372

Use comparator with constructor. See below. Note, we pass constructor and operator parameters by const reference.

struct MyCompare
{
    MyCompare(const vector<int>& arOne, const vector<int>& arTwo)
        : nums1(arOne), nums2(arTwo)
    {}

    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];
    }

    const vector<int>& nums1;
    const vector<int>& nums2;
};

// Define as follows

std::priority_queue<pair<int, int>, vector<pair<int, int> >, MyCompare> 
min_heap(MyCompare(arOne, arTwo));

Upvotes: 0

Galik
Galik

Reputation: 48615

You can pass the arrays in the comparator's constructor.

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;
};

Then use it like:

myCompare comp(nums1, nums2);

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

Upvotes: 1

Related Questions