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;

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

Answer 1

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

相反，您可以将顶点标记为死。只需将一些错误值放入点数组(在您的示例中 -1 就可以了)。每次删除时进行标记只需O(1)。有时您可能想要物理删除死顶点。您可以使用两次完整 channel (一次在顶点上，一次在三角形上)来完成此操作，并在线性时间内压缩网格O(V + T)。

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

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

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

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

为了避免危险，请向网格添加lock/unlock方法。然后，您可以确保只要网格被锁定，其顶点就保证按索引保持在原位。在这种情况下，您可以安全地执行诸如顶点过滤之类的操作。