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

Question

假设我有一个点向量：

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 总是检查）。

相反，您可以将顶点标记为 dead。只需将一些错误的值放入点数组（在您的样本中 -1 就可以了）。每次删除只需要 O(1)。有时您可能想要物理移除死顶点。您可以使用两个完整通道（一个在顶点上，一个在三角形上），并在线性时间内压缩您的网格 O(V + T).

为了便于使用，我建议为您的网格创建一个 class。在网格对象中，保持对 class 用户透明的死条目数。当部分死条目在删除后变得相当大（例如超过一半）时，调用死顶点消除。您还可以制作三角形枚举方法，该方法将只迭代活动的三角形（只是为了方便）。

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

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

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

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

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

Updating stored indices after erasing an element from std::vector

c++

c++11

stdvector

notify

erase