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

Question

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.

Galik · Accepted Answer · 2017-01-21 03:56:21Z

1

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

edited Jan 21, 2017 at 3:56

answered Jan 21, 2017 at 3:47

Galik

49k5 gold badges85 silver badges126 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user3813057 Over a year ago

This solution is nice. It inspires me that we can also use two iterators pointing to array.begin() as the member variables of the comparator. And the entry can be accessed by begin_iterator+index.

ivan_onys · Accepted Answer · 2017-01-21 04:11:46Z

0

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

answered Jan 21, 2017 at 4:11

ivan_onys

2,42319 silver badges23 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related