c++ - 从 std::vector 中删除元素后更新存储的索引

Question

假设我有一个点 vector :

vector<int> points;

三角形存储构成它们的点的索引:

struct Triangle {
    int p0, p1, p2;
};

Triangle tri0;
tri0.p0 = 3;
tri0.p1 = 6;
tri0.p2 = 7;

Triangle tri1;
tri1.p0 = 4;
tri1.p1 = 6;
tri1.p2 = 7;

现在我决定删除 point[3]。但是，如果我删除 point[3]，索引 3 之后的点的索引将移回，因此我需要通知所有三角形它们存储的索引可能会更改。什么是通知三角形的合理方式？

Answer 1

在我看来，最合理的方法是不删除顶点。因为如果你真的删除它们，那么你必须将所有顶点向右移动(平均 V/2 个元素)，然后你必须遍历所有三角形(T 总是检查)。

相反，您可以将顶点标记为死亡。只需将一些错误的值放入点数组(在您的示例 -1 中就可以了)。每次删除只需 O(1) 做标记。有时您可能想要物理移除死顶点。您可以通过两次完整的传递(一次遍历顶点，一次遍历三角形)来完成，并在线性时间内压缩您的网格 O(V + T)。

为了使事情易于使用，我建议为您的网格创建一个类。在网格对象中，对类用户透明地维护死条目的数量。当部分死条目在删除后变得相当大(例如超过一半)时，调用死顶点消除。您还可以制作三角形枚举方法，它只会迭代事件的三角形(只是为了方便)。

如果花在压缩上的时间量不大于删除数乘以常量，这种方法可确保O(1) 每次删除的摊销时间。鉴于 T <= c V 在任何时刻(对于某个常数 c)，它是正确的。事实上，不太可能看到三角形数量远大于顶点数量的网格，所以你没问题。

一个非常不同的解决方案是使用链表而不是数组来存储顶点和三角形(带有指向彼此的指针)。在这种情况下，您可以在 O(Sv) 时间内删除顶点 v，其中 Sv 是它所属的三角形数。但是这种数据结构的底层性能可能很差。

编辑 我想到了另一个问题。对用户透明地调用死顶点消除，但此时用户可能陷入三角形或顶点枚举的中间。显然这种情况会造成很大的麻烦。

为了避免危险，请将lock/unlock 方法添加到您的网格中。然后您可以确保只要网格被锁定，它的顶点就可以保证按索引保留在适当的位置。在这种情况下，您可以安全地执行顶点过滤等操作。