c++ - 如何使用仿函数代替 lambda 函数

Question

我正在尝试解决 Leetcode 中的问题。

问题描述:

给定一个 n x n 矩阵，其中每一行和每一列都按升序排序，找到矩阵中第 k 个最小的元素。

请注意，它是排序顺序中第 k 个最小的元素，而不是第 k 个不同的元素。

我是这样解决的:

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

此代码有效。然而，当我试图用仿函数替换 lambda 函数时，我写了这样的仿函数:

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

然后我意识到我不知道如何在 lambda 函数中将 matrix 传递给像 [&matrix] 这样的仿函数。

有人能帮忙吗？

Answer 1

您需要在仿函数的构造函数中传递引用。请注意，以下代码等效于您的 lambda，但带有 mutable 修饰符。

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;

};

然后将其用作:

comp_gt comp{matrix};