c++ - 实现战场 3's std::vector swap trick to "删除/添加“一个元素

Question

我正在尝试实现一个算法，我偶然发现了 DICE 的“交换技巧”，如 here 所述(幻灯片 19)。

据我了解，我们首先创建一个包含所有元素的 vector ，然后当需要删除一个元素时，将它与最后一个元素交换，然后我们减小 vector 的“大小”。这个“大小”是一个外部变量，用于跟踪我们的“虚拟”大小(因为 vector doesn't support this internally )。

注意:排序/排序并不重要。另外，当我说“删除”时，没有任何东西被取消分配，它只是说元素被移动到“可用”范围之外。

现在，当需要将一个元素(从已删除的元素中)添加回 vector 的可用部分时，我们需要将其交换回某处。这就是我要阻止的地方。因为，当我们交换它时，我们可以将它与本次迭代中需要存在的元素进行交换，而这个相同的元素将需要交换回来，依此类推...

这是一个它应该如何工作的例子:

迭代 1:|1 2 3 4| (尺寸 4)

迭代 2:|1 3| 2 4(大小为 2，元素“2”和“4”仍在内存中，但未计入 vector 大小)

迭代 3:|2 1 3| 4(尺寸 3，元素“4”仍然存在)

我可能想得太多了，但如果有人知道如何正确使用该算法，那将会很有帮助。

感谢您的帮助。

Answer 1

用第一个不可用的元素交换它，然后增加你的虚拟大小。因此，例如，假设这是您的 vector :

  // usable         unusable
{ 0, 1, 2, 3,       4, 5, 6, 7, 8 } // virtual size = 4

现在假设您要将 7 从不可用部分移动到可用部分。您将它与 4 交换，因为这是第一个不可用的元素。然后你将你的虚拟大小增加 1。所以现在你的 vector 看起来像这样:

  // usable         // unusable
{ 0, 1, 2, 3, 7,    5, 6, 4, 8 } // virtual size = 5