在递归函数中使用迭代器会导致分段错误

Question

我编写了一个程序，它接收 N 个代表学生技能水平的整数测试用例，并尝试找到可能的最小组的总数，前提是唯一的限制是不能有相同的技能水平在一个团队中，没有技能差距大于 1。所以下面的测试用例：

4 5 2 3 -4 -3 -5

会输出：

因为可能的团队是 {-4,-3,-5} 和 {4,5,2,3}，因为第一组只有三个成员，所以输出是 3。

我决定用链表和递归函数来解决这个问题。一个递归函数会在一个整数的左边和右边寻找一个比它大一个大小的整数，找到一个然后从列表中删除该元素并返回 1。另一个函数也是这样做的，它寻找一个小于 1 的整数。这应该会产生一个组的总和，我可以比较不同的总和以找到最小的总和。不幸的是，当我尝试实现这个时，我不仅遇到了分段错误，而且经过几次迭代后出现的数字甚至都不是列表的一部分，而且非常大。

#include <cmath>
#include <cstdio>
#include <list>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int findHigherSkillLevel(int skillLevel, list<int>::iterator *it, list<int> &list) {
  if (it == NULL) return 0;

  if (**it == (skillLevel + 1)) {
    //cout << "test3" << endl;
    skillLevel++;
    list.erase(*it); 
    *it = list.begin();   
    //cout << "Iterator in the higher skill level function if it finds a skill level higher by 1: " << **it << endl;
    //cout << "The skill level is: " << skillLevel << endl;
    return 1 + findHigherSkillLevel(skillLevel, it, list);
  } else {
    //cout << "Iterator in the higher skill level function if it doesn't find one: " << **it << endl;
    return findHigherSkillLevel(skillLevel, ++it, list);
  }

  return 0;
}

int findLowerSkillLevel(int skillLevel, list<int>::iterator *it, list<int> &list) {
  if (it == NULL) return 0;

  if (**it == (skillLevel - 1)) {
    skillLevel--;
    list.erase(*it);
    *it = list.begin();
    return 1 + findLowerSkillLevel(skillLevel, ++it, list);
  } else {
    //cout << "test2" << endl;
    return findLowerSkillLevel(skillLevel, ++it, list);
  }

  return 0;
}

int findGroupsSizes(list<int>::iterator *it, list<int> &list) {
  if (it == NULL) return 0;
  int groupSize = 1;
  int skillLevel = **it;
  *it = list.erase(*it);
  //cout << "Iterator value in the first function: " << **it << endl;
  groupSize += findHigherSkillLevel(skillLevel, it, list) + findLowerSkillLevel(skillLevel, it, list);

  return groupSize;
}

如果我要使用提到的测试用例，那么它将遍历 4、5、2，然后弹出一些奇怪的数字，最后出现段错误。如果在这些递归中从列表中弹出迭代器，就不可能在递归函数上使用迭代器吗？

main() 实际上接受了 t 个总测试用例，然后是 t 行 N 个分隔整数。我使用以下作为测试用例：

4  
7 4 5 2 3 -4 -3 -5  
1 -4  
4 3 2 3 1  
7 1 -2 -3 -4 2 0 -1

如果重要的话，这里是主要的：

int main() {
  int t; // the number of test cases
  cin >> t;
  vector<list<int> > skillLevels(t, list<int>());
  // input for each test case
  for (int i = 0; i < t; i++) {
    int n; // number of students for this test case
    cin >> n;

    // initialize the list for this test case
    for (int j = 0; j < n; j++) {
       int skillLevel;
       cin >> skillLevel;
       skillLevels[i].push_back(skillLevel);
    }
  }

  // recursively scan lists for smallest teams
  for (int i = 0; i < t; i++) {
    int minGroupNumber = skillLevels[i].size();
    list<int>::iterator iterator = skillLevels[i].begin();
    int skillLevel = skillLevels[i].front();

    while (!skillLevels[i].empty()) {
      iterator = skillLevels[i].begin();
      int currentGroupSize = findGroupsSizes(&iterator, skillLevels[i]);
      cout << currentGroupSize << endl; 
      if (currentGroupSize < minGroupNumber)
        minGroupNumber = currentGroupSize;
      //cout << minGroupNumber << endl;
      if (!skillLevels[i].empty()) skillLevels[i].pop_front();
    }
    cout << minGroupNumber << endl;
  }

  return 0;
}

Answer 1

++it 递增指针（这使其无效）而不是迭代器。你可能想要 ++*it。

但这也可能会让您超出列表的末尾。

在递归函数中使用迭代器会导致分段错误

Using an iterator in a recursive function results in a segmentation fault

c++

recursion

iterator

list

segmentation-fault