c++ - 在 C++ 中实现列表位置定位器？

Question

我正在用 C++ 编写一个基本的图形 API(我知道库已经存在，但我这样做是为了练习/体验)。该结构基本上是邻接表表示的结构。于是就有了Vertex对象和Edge对象，Graph类包含:

list<Vertex *> vertexList
list<Edge *> edgeList

每个 Edge 对象都有两个 Vertex* 成员表示其端点，每个 Vertex 对象都有一个 Edge* 成员列表，表示入射到 Vertex 的边。

这一切都很标准，但这是我的问题。我希望能够在恒定时间内实现边和顶点的删除，因此例如每个 Vertex 对象都应该有一个 Locator 成员，该成员指向其 Vertex* 在 vertexList 中的位置。我最初实现它的方式是保存一个 list::iterator，如下所示:

vertexList.push_back(v);
v->locator = --vertexList.end();

然后如果我以后需要删除这个顶点，那么我可以调用:

vertexList.erase(v->locator);

一开始它工作正常，但似乎如果对列表进行了足够多的更改(删除)，迭代器将变得过时并且我在运行时遇到各种迭代器错误。这对于链表来说似乎很奇怪，因为您似乎不需要在删除后重新分配列表的剩余成员，但也许 STL 这样做是为了通过保持内存的连续性来优化？

无论如何，如果有人对发生这种情况的原因有任何见解，我将不胜感激。 C++ 中是否有一种标准方法来实现定位器，该定位器将跟踪元素在列表中的位置而不会过时？

非常感谢，杰夫

Answer 1

(我假设你是单线程的，显然 list 不是线程安全的)

but maybe the STL does this to optimize by keeping memory somewhat contiguous?

不正确 - list::insert、list::push_front 和 list::push_back 不影响 list::iterators 的有效性。如果您只调用列表中的这些修改器，那么它将保持有效。

In any case, I would appreciate it if anyone has any insight as to why this happens. Is there a standard way in C++ to implement a locator that will keep track of an element's position in a list without becoming obsolete?

您的方法应该有效，请发布一些代码来证明它无效。同时这里有两种替代表示:

为什么不使用:

struct Graph
{
    typedef unique_ptr<Vertex> PVertex;
    typedef unique_ptr<Edge> PEdge;

    unordered_set<PVertex> verticies;
    unordered_set<PEdge> edges;
};

这样你就可以随心所欲地在恒定时间内删除它们。 unordered_set 通常使用哈希表实现，因此其平均 O(1) 访问时间。

而且 unique_ptr 意味着你可以让 unordred_sets“拥有”它们

如果顶点是可数的并且有一个固定的最大上限(N)，另一种表示是:

struct Graph
{
    typedef unique_ptr<Vertex> PVertex;
    typedef unique_ptr<Edge> PEdge;

    array<PVertex, N> verticies;
    array<array<PEdge, N>, N> edges;
};

其中 edges[i][j] 保存了 verticies[i] 和 verticies[j] 之间的边

如果 verticies[x] 或 edges[x][y] 为 nullptr in 表示对应的顶点或边不存在。

旧的 C++ 版本:

1. unordered_set 是在 TR1 中引入的。如果你没有这个，你可以使用 boost。如果你不想使用 boost，你可以使用一个普通的旧集合，它会提供登录访问时间，或者你可以实现你自己的哈希表。

2. 对于旧版本，unique_ptr 可以替换为 auto_ptr。

3. 数组可以替换为常规数组或 vector 。