c++ - 为什么使用vecS作为OutEdgeList模板参数的boost adjacency_list会使遍历的边无效？

Question

我正在阅读有关adjacency_list的文档，以及choosing the graph type对内存消耗，big-O运行时和描述符稳定性的影响。
引用第一个链接:

The following table summarizes which operations cause descriptors and iterators to become invalid. In the table, EL is an abbreviation for OutEdgeList and VL means VertexList. The Adj Iter category includes the out_edge_iterator, in_edge_iterator, and adjacency_iterator types.
A more detailed description of descriptor and iterator invalidation is given in the documentation for each operation.

我了解，如果将 vecS用作 VertexList，则在 remove_vertex()上将调整所有顶点描述符，以使它们仍然连续。
我不明白，为什么显然使用 vecS导致边缘迭代使边缘描述符无效。
我是否正确理解该表，因为它说:“如果您在 vecS的 adjacency_list图上将 directedS用作Edge List类型，则您无法稳定地对边缘进行迭代，因为对其进行迭代将使边缘迭代器和边缘描述符无效” ？
如果我确实理解正确，请解释为什么会这样。如果我误会了，请使用 vecS来说明边缘列表具有的实际效果。
谢谢。

Answer 1

您怀疑是您误读了它。
混淆之处在于“Edge Iter”，“Vertex Iter”和“Adj Iter”列是“Iterator”的缩写，而不是“iteration”。
仅仅进行迭代就不会更改adjacency_list，因此不会使描述符或迭代器无效。
在某些图模型中，描述符比迭代器(迭代器)更稳定。这实际上是描述符概念的关键原因。任何具有引用稳定性的容器选择器(即基于节点的容器)自然具有迭代器稳定性(仅使迭代器无效)已删除的节点)。
该表之所以有用，是因为通过选择连续存储(如vecS)可以大大提高“不变”(或很少更改，经常查询的)图的性能，并且它们自然会施加更多的限制失效规则(例如， vector 可能会重新分配，从而使失效)所有迭代器，但描述符可能在修改/插入的索引之前保持稳定)。
提示
为了获得基本失效问题的原始编译时检查，请考虑通过const引用获取图形。这将消除意外修改的机会。当然，在某些情况下，您确实想在性能方面走到想要对图形进行修改的边缘，并且必须仔细阅读文档，以了解确切的无效规则适用于该修改。