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