How to use a functor instead of lambda function

Question

I was trying to solve a problem from Leetcode.

Problem description:

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

I solved it like this:

class Solution { public: int kthSmallest(std::vector<std::vector<int>>& matrix, int k) { auto comp_gt = [&matrix](std::pair<int ,int> a, std::pair<int ,int> b) { return matrix[a.first][a.second] > matrix[b.first][b.second]; }; m = matrix.size(); if (m == 0) return 0; n = matrix[0].size(); if (n == 0) return 0; std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(comp_gt)> min_heap(comp_gt); for (int j = 0; j < n; ++j) { min_heap.emplace(0, j); } for (int i = 0; i < k-1; ++i) { int r = min_heap.top().first; int c = min_heap.top().second; min_heap.pop(); if (r != m - 1) { min_heap.emplace(r+1, c); } } return matrix[min_heap.top().first][min_heap.top().second]; } private: int m; int n; };

This code works. However, when I tried to replace the lambda function with a functor, I wrote the functor like this:

class comp_gt { bool operator () (std::pair<int, int> a, std::pair<int, int> b, std::vector<std::vector<int>>& matrix) { return matrix[a.first][a.second] > matrix[b.first][b.second]; } };

then I realized I didn't know how to pass the matrix to a functor like [&matrix] in a lambda function.

Can anyone help?

CuriouslyRecurringThoughts · Accepted Answer · 2019-08-11 14:45:20Z

You need to pass the reference in the constructor of the functor. Note that the below code is equivalent to your lambda, but with the mutable modifier.

class comp_gt { public: using Matrix = std::vector<std::vector<int>>; comp_gt(Matrix& matrix) : matrix{matrix}{} bool operator () (std::pair<int, int> a, std::pair<int, int> b, std::vector<std::vector<int>>& matrix) { return matrix[a.first][a.second] > matrix[b.first][b.second]; } private: Matrix& matrix; };

Then use it as:

comp_gt comp{matrix};

As far as I know, overloaded operator should take only two parameters for priority_queues. Why priority_queue does not create compilation/linking error with a function object as a custom comparator that has a overloaded function operator with an third additional parameter 'matrix' ?

Jesper Juhl · Accepted Answer · 2019-08-11 14:35:51Z

"How to use a functor instead of lambda function" - Create a class with operator() (that optionally captures variables). A lambda is nothing but syntactic sugar (an easier way) to write such a (functor) class.

Sam Varshavchik · Accepted Answer · 2019-08-11 14:38:25Z

This is done by passing it to the comparator's constructor:

class comp_gt { std::vector<std::vector<int>>& matrix; comp_gt(std::vector<std::vector<int>>& matrix) : matrix{matrix} {}

Now, your existing operator() can use it normally.

Then, when you actually go about constructing the comparator, you just construct it normally and pass the appropriate parameter to the constructor. Let's say you wanted to use your comparator with std::sort:

comp_gt comparator{some_matrix}; std::sort(something.begin(), something.end(), comparator);

Using this comparator with std::priority_queue is analogous.

Collectives™ on Stack Overflow

How to use a functor instead of lambda function

3 Answers 3

1 Comment

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Related