如何使用仿函数代替 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};

Answer 2

"How to use a functor instead of lambda function" - 使用 operator() 创建一个 class（可选择捕获变量）。 lambda 只不过是 语法糖（一种更简单的方法）来编写这样的（函子）class.

Answer 3

这是通过将其传递给比较器的构造函数:

来完成的

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

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

现在，您现有的operator()可以正常使用了。

然后，当您真正着手构造比较器时，您只需正常构造它并将适当的参数传递给构造函数即可。假设您想将比较器与 std::sort:

一起使用

comp_gt comparator{some_matrix};

std::sort(something.begin(), something.end(), comparator);

将此比较器与 std::priority_queue 一起使用是类似的。

如何使用仿函数代替 lambda 函数

How to use a functor instead of lambda function

c++

priority-queue

functor