3

我的代码的基本结构是：

using namespace std;
void recursiveFunction(list <int> &jobs,...){
list<int>::iterator i;
int ii;
//code missing
    for(i=jobs.begin(); i != jobs.end(); ++i){
        //more code missing
        list<int>::iterator tempi(i);
        ii=*i;
        jobs.erase(tempi);
        recursiveFunction(jobs,...);
        jobs.insert(i,ii);
    }
}

正如我所发现的，任何指向已擦除位置的指针都无效，因此 i 无效。有没有办法以这种方式重新插入工作编号？如果没有每次递归创建一个新列表的性能影响？

有没有办法使用列表迭代器以外的东西，也许？

4

2 回答 2

7

list::erase将迭代器返回到（最后一个）擦除元素之后的元素，并且由于list::insert将在您传递它的迭代器的元素之前插入，这非常适合您的需求：

using namespace std;
void recursiveFunction(list <int> &jobs,...){
  //...
  for(auto i = begin(jobs); i != end(jobs);){ 
    //...
    auto tmpElem = *i;
    i = jobs.erase(i);
    recursiveFunction(jobs,...);
    jobs.insert(i,tmpElem);
  }
}

笔记：

  • 与i=jobs.erase(i)您有效地增加i。所以将增量留在 for 循环中。或者i=jobs.insert(i,tmpElem)稍后使用，所以i再次指向相同的元素
  • 尽可能将变量（例如i, ）声明为局部变量，以保证良好的风格和可维护性tmpElem
  • 给变量起有意义的名字

根据功能的作用，可能还有其他可能性来实现您想要的。这样，您将处理列表元素的每个子集，并且多次处理其中的许多子集。考虑列表有内容{1,2,3}，这是将要发生的事情（在伪代码中）：

recursiveFunction({1,2,3},...)
  for-loop, i = &1
    erase(1)
    recursiveFunction({2,3},...)
      for-loop, i = &2
        erase(2)
        recursiveFunction({3},...)    //a
        insert(2)
      //...
    insert(1)
  for-looop, i = &2
    erase(2)
    recursiveFunction({1,3},...)
      for-loop, i = &1
        erase(1)
        recursiveFunction({3},...)    //b
        insert(1)
      //...
    insert(2)
  //...

a 和 b 行看起来一样，尽管附加参数可能不一样 - 我无法从您的代码中分辨出来。因此，请牢记这一点，并考虑这是否是您真正想要的。

于 2013-06-18T07:21:30.977 回答
0

递归似乎不是解决您的问题的正确工具。如果您有一个包含 { 1, 2, 3, 4 } 并且所有三个都符合条件的列表，看起来会发生这样的事情：

递归（{1,2,3,4}）；
  it.1 = (1)
  删除 1
  递归（{2,3,4}）；
    it.2 = (2)
    删除 2
    递归（{3,4}）；
      it.3 = (3)
      删除 3
      递归（{4}）；
        it.4 = (4)
        删除 4
        递归（{}）
        重新插入 4 ({4})
      重新插入 3 ({3,4})
      it.3 = (4)
      删除 4
      递归（{3}）；
        it.4 = (3)
        删除 3
        递归（{}）
        重新插入 3 ({3})
      重新插入 4 ({3,4})
    重新插入 2 ({2,3,4})
    it.2 = (3)
    删除 3 离开 ({2,4})
... ETC ...
于 2013-06-18T07:22:37.203 回答