c++ - 迭代正在变化的 std::list 的有效方法？

Question

我正在尝试迭代 astd::list但有一个问题 - 迭代期间执行的操作可能最终会从列表中添加或删除元素。在这种情况下，添加不是问题，但删除最终可能会使列表中的任何迭代器失效，包括序列中的当前项或下一项。

决定修改列表的点与迭代循环相去甚远——调试器在两者之间的调用堆栈中显示了 40 个函数调用。因此，无法根据删除来修改迭代器。

我唯一能想到的就是在开始时制作一个列表副本并对其进行迭代，测试每个元素以确保它仍在主列表中。这是一个 O(n^2) 命题，如果可能的话，我想避免。

score 2 · Accepted Answer

You have three options:

Like you said make a local copy of the list
when the iterators are invalidated start over again (and maybe skip n iterations? [with continue])
Edit: Like Pubby said, mark removed elements expired, and when you add elements use the skipping n iterations stuff :)

Iterators don't allow access by index so this makes it a bit harder to come up with a elegant solution for your problem.

score 1 · Accepted Answer

这里还有一些选择。

1.拼接

“修改”代码可以使用拼接方法将其移动到某个临时列表，而不是删除元素。拼接单个元素是一个恒定时间的操作。并且它不会使任何迭代器或引用无效（即使对于移动的元素）。

在移动元素之前，“修改”代码应该推进列表迭代器的主副本（属于“迭代”代码）。

“迭代”代码应该在每次迭代后清除这个临时列表。

优点：不需要向包含的元素添加任何标志。

缺点：由于需要清空临时列表，有些性能下降；需要外部接口来推进属于“迭代”代码的迭代器；如果“迭代”和“修改”代码之间的某些代码需要检查相对于“已删除”元素的下一个/上一个元素，它只会看到其他“已删除”元素而不是列表的其余部分。

如果您为迭代器当前指向的元素设置“锁定”标志，“修改”代码可能只对这个单个元素使用拼接，并以通常的方式删除其他元素。

“迭代”代码应该在每次迭代后清除临时列表。

优点：几乎没有性能损失。

缺点：需要修改list的元素；需要外部接口来推进属于“迭代”代码的迭代器；如果“迭代”和“修改”代码之间的某些代码需要检查相对于“已删除”元素的下一个/上一个元素，它不会找到任何东西。

如果您为迭代器当前指向的元素设置“锁定”标志，“修改”代码可能只是为该单个元素设置“已删除”标志并以通常的方式删除其他元素。

“迭代”代码应该（在每次迭代之后）只删除一个标记为要删除的元素。

优点：几乎没有性能损失；如果“迭代”和“修改”代码之间的某些代码需要检查相对于“已删除”元素的下一个/上一个元素，它会按预期工作。

缺点：需要修改列表的元素。

score 1 · Accepted Answer

最终可能使列表中的任何迭代器无效

没有。

看描述std::list::erase：_

迭代器有效性

擦除的结论：只有被删除的元素变得无效。所有其他逗留有效。而且，在这种情况下，您有机会在大多数情况下实现 O(n)。

score 0 · Accepted Answer

想到了两种可能的方法（除了制作列表的副本）：

1）不要立即从列表中删除内容。相反，一旦你完成了完整的迭代，构建另一个迭代器容器来擦除。这确实改变了行为（“已删除”元素可能仍会被执行）所以我不知道它是否对你有帮助。

2）让您的列表包含指针或带有项目/有效性标志的一对，并简单地清除有效性。然后，一旦您完成第一次迭代，再进行一次迭代以清理已退休的节点。