iterator - 在 Boost Graph Library 中，为什么添加边会使边迭代器失效(以及其他问题)？

Question

关于BGL documentation中图表的几个问题标记为“描述符和迭代器失效总结”:

1. 为什么添加边会使边和邻接迭代器失效？为什么 add_edge() 行的每一列不是“OK”？难道不是简单地附加入/出边缘列表吗？
2. 如果图是有向的，为什么删除边只会使边迭代器失效？为什么第二行倒数第二列不只是“EL=vecS”？在无向图的情况下，不会删除一条边，将其从两个边列表(一个用于源顶点，一个用于目标顶点)中删除，这会使这两个列表中的迭代器无效？

谢谢!

Answer 1

所有这些效果都来自通常的 Iterator invalidation rules

1. Why does adding an edge invalidate the edge and adjacency iterators; why isn't every column of the add_edge() row "OK"? Wouldn't the in/out edge lists simply be appended?

是的，它们将被附加。而且，看到他们可能会重新分配这样做，他们就使迭代器无效。

2. Why does removing an edge only invalidate an edge iterator if the graph is directed

矩阵中的符号有点令人困惑。

文档:“此操作会导致任何指向边缘 (u,v) 的未完成边缘描述符或迭代器变得无效。此外，如果 OutEdgeList 选择器是 vecS 那么此操作将使指向顶点 u 以及无向中的顶点 v 的边列表的任何迭代器无效和双向情况。此外，对于有向图，这会使任何 edge_iterator 无效。”

所以你误读了:它不仅使“如果图形是有向的”无效。在无向和双向情况下，它还使指向目标顶点 (v) 的边列表的任何迭代器无效。如果您了解后刃是如何存储的，这是有道理的。