c++ - 避免在向量迭代期间迭代器失效

Question

在遍历向量时，推荐的避免错误的方法是什么；向量中的任意数量的元素可能（直接或间接）导致元素的插入或删除 - 使迭代器无效？

具体来说，我问的是游戏编程，向量中的元素是游戏对象；其中一些可以生成其他对象，其中一些将在更新时被杀死并需要删除。正因为如此，在迭代之前保留大容量也是不可能的，因为完全不知道可以添加多少元素。

Answer 1

一般不能说。迭代器失效的部分原因是没有办法读懂你的想法来知道你希望失效的迭代器引用什么元素。

例如，我有一个指向元素 3 of 5 的迭代器。我删除元素 2。迭代器应该指向新元素 2（因为它是“相同的值向下移动”），还是应该指向新元素 3（因为它是“向量的相同元素，具有不同的值向下移动”）？

实际上，您的选择是：

1. 不要在其他人有迭代器时插入/删除元素。这意味着更改您的代码以在其他时间进行更改。
2. 使用索引而不是迭代器。这导致上面的第二个选项（“索引引用具有新值的相同元素”）。请注意，如果您删除了足够多的元素以致索引结束，索引也可能变得无效。
3. 使用具有不同迭代器失效规则的不同数据结构。例如 astd::list会给你上面的第一个选项（“迭代器引用新位置的相同元素”）

您用于迭代的迭代器永远不会因在该位置插入/擦除单个元素而有害地无效。它已失效，但两个函数都返回一个新的迭代器，您可以使用该迭代器继续迭代。有关新迭代器引用的元素，请参阅他们的文档。这就是为什么只有在同一个容器上使用多个迭代器时才会出现问题。

Answer 2

Vector 可能不是支持密集插入/删除的最佳容器（尤其是当大小很大时）。但是，如果您必须使用向量，恕我直言，最安全的方法不是使用迭代器，而是使用索引，并跟踪（并调整索引）在当前位置之前插入/删除的项目。这样，您至少可以避免重新分配的问题。

并在每次迭代后重新计算 v.size()/v.end()。

Answer 3

这里有一些想法：

1. 使用整数索引迭代向量。这不会失效，但您需要在插入/删除元素时注意调整当前索引。
2. 迭代向量的副本。
3. 不要在进行过程中对向量进行更改，而是跟踪需要插入/删除的内容，并在完成迭代后应用更改。
4. 使用不同的容器，例如链表。

Answer 4

使用单独的向量和std::move未删除的元素以及任何创建的新元素。然后删除旧向量。

这样，您不必从原始向量中删除/插入任何内容，并且迭代器不会失效。

Answer 5

当然，您可以通过使用不会在插入和删除时使迭代器无效的容器来解决此问题。

我想推荐一种不同的方法。本质上，您是在迭代向量以在游戏世界中创建一个新状态。不要在遍历向量时更改世界的状态，而是将需要更改的内容存储在新向量中。然后，在您完全检查了旧状态之后，应用您存储在新向量中的更改。

这种方法有一个概念优势：每个对象的新状态仅依赖于旧状态。如果您在遍历旧状态时应用更改，并且关于一个对象的决定可能取决于其他对象，则遍历顺序会影响结果，这可能会给“较早”或“较晚”的对象带来不公平的优势。