Created by potrace 1.14, written by Peter Selinger 2001-2017 Zorch's Blog

C++递归lambda出现的循环初始值捕获问题分析与解决

 
Category： C_C++
  • zorchp
  • 2022年 10月21日

问题

昨天开始刷回溯系列, 在用Python的时候一切良好, 但是到了C++这里, 我突然发现一模一样的代码竟然不出值了, 具体情况如下, 题目是全排列46. 全排列 - 力扣（LeetCode）,我的代码如下:

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int ns = nums.size(), i = 0;
        vector<int> path{};
        vector<bool> used(ns, false);
        vector<vector<int>> ans{};
        function<void(void)> f = [&](void) {
            if (path.size() == ns) {
                ans.emplace_back(path);
                return;
            }
            for (i = 0; i < ns; i++) {
                if (used[i]) continue;
                used[i]=true;
                path.emplace_back(nums[i]);
                f();
                path.pop_back();
                used[i] = false;
            }
        };
        f();
        return ans;
    }
};

我在本地调试加上了对一维和二维数组的输出操作符重载:

  #include <iostream>
  #include <vector>
  #include <cstring>
  #include <functional>
  
  using namespace std;
  
  ostream& operator<<(ostream& os, const vector<int>& v) {
      for (auto& i : v) os << i << " ";
      os << endl;
      return os;
  }
  
  ostream& operator<<(ostream& os, const vector<vector<int>>& v) {
      for (auto& ll : v) {
          for (auto& i : ll) os << i << " ";
          os << "\n";
      }
      os << endl;
      return os;
  }
  
  // 主函数
  int main(int argc, char const* argv[]) {
      Solution s;
      vector<int> v1 = {1, 2, 3};
      cout << s.permute(v1) << endl;
      return 0;
  }

乍一看完全没有问题, 代码逻辑也没出错, 但是运行结果就是不尽人意:

1 2 3

只出来了一个排列(就是其自身), 也就是说回溯的过程根本就没有进行, 这是因为什么呢?

我加上了几行输出, 与标准答案进行对比,才逐渐找到了问题所在:lambda的值捕获与循环的值初始化出了问题!

分析与调试

class Solution {
public:
    // void f(void) {}
    vector<vector<int>> permute(vector<int>& nums) {
        int ns = nums.size(), i = 0;
        cout << "func()  i=" << i << endl;
        vector<int> path{};
        vector<vector<int>> ans{};
        vector<bool> used(ns, false);
        function<void(void)> f = [&]() {
            cout << "lambda() first i=" << i << endl;
            if (path.size() == ns) {
                ans.emplace_back(path);
                return;
            }
            for (i = 0; i < ns; ++i) {
                cout << "loop first i=" << i << endl;
                if (used[i]) continue;
                path.emplace_back(nums[i]);
                used[i] = true;
                f();
                cout << "after recur, path=" << path;
                path.pop_back();
                used[i] = false;
                cout << "loop last i=" << i << endl;
            }
            cout << "lambda() last i=" << i << endl;
        };
        f();
        cout << "last func() i=" << i << endl;
        return ans;
    }
};

这次的输出如下:(为方便查看我用换行进行分割)

func()  i=0

lambda() first i=0
loop first i=0

lambda() first i=0
loop first i=0
loop first i=1

lambda() first i=1
loop first i=0
loop first i=1
loop first i=2

lambda() first i=2
after recur, path=1 2 3
loop last i=2

lambda() last i=3
after recur, path=1 2
loop last i=3

lambda() last i=4
after recur, path=1
loop last i=4

lambda() last i=5

last func() i=5
1 2 3

这也就找到了问题的所在, 剩下的部分还没有走到回溯的过程, 程序就被`return;`结束了..

为什么会有这样的问题呢? 可以看到最后i的值竟然超过了3, 直到递增到5才结束, 这虽然不会引起vector溢出, 但是循环之后的回溯过程只会进行一次, 就导致ans只有一个值了.

当递归深度到达3的时候, 也就是loop last i=2这块, 可以看到i此时已经是2了, 也就是在这里, for中的自增运算符++给i赋值为3, 不满足循环然后退出, 然后来到了递归深度为2的地方, 这里面由于i的值没进行更新, 所以还是不满足循环, 退出, i变成了4, 最后一次i加到了5, 这时候程序内存空间中已经没有了开辟出来的新栈帧了, 于是f()执行完毕, 最终ans只返回了一个值, 也就是自身.

不难发现, 对于递归函数来说, 特别是存在值共享的lambda函数中, 循环变量的初始化非常重要, 像这个程序中的i值, 由于其初始化发生在递归函数外部, 内部访问i的时候就只能通过lambda隐式捕获的方式获取, 即[&](){}形式, 这就导致了整个递归函数内部的同时共享一份变量i, 这才会出现上述程序的执行结果不正确的问题.

要解决这个问题其实非常简单, 只需要将for的循环变量初始化改为int i=0, 每一次循环都会重新开辟一份i, 这也就不会出现递归之后还是共享一份i导致递归终止的情况了.

小结

  • 使用lambda函数一定要注意值的传递和隐式捕获问题;
  • 循环变量作用域最好只在循环内部, 否则函数其他位置可能也会修改该变量, 导致意想不到的错误.
search search_off backspace