BGL:以不会使它们无效的方式存储顶点描述符 [英] BGL: storing vertex descriptors in a way that they won't invalidate

问题描述

问题是关于Boost Graph库.

The question is about the Boost Graph Library.

假设我们将对象与图的每个顶点一起存储，并且顶点和对象之间存在一一对应的关系.进一步假设我们维护一个std::map以允许查找与给定对象相对应的顶点描述符.

Suppose that we store an object with each vertex of the graph and there is a one-to-one correspondence between the vertices and the objects. Suppose further that we maintain an std::map to enable looking up a vertex descriptor that corresponds to a given object.

但是，在删除顶点的情况下，此解决方案似乎易于使顶点描述符无效.有办法解决这个问题吗?

However, this solution seems to be prone to invalidation of vertex descriptors in the case of a vertex being deleted. Is there a way to get around this problem?

在此问题中，出现以下句子:

In this question, the following sentence appears:

我想以不会删除顶点的方式使顶点描述符无效的方式存储顶点描述符，所以我使用boost :: listS

I want to store vertex descriptors in a way that they wont invalidate in case I remove a vertex, so I use boost::listS

该问题的作者似乎可以解决顶点无效问题，但我不知道这是什么.

It seems like the author of that question has a solution to the problem of vertex invalidation, but I do not understand what it is.

阐明维护地图的原因.在以下情况下，需要基于对象查找顶点.假设我们已经生成了一个对象.我们需要查找一个顶点，该顶点对应于一个对象(在operator==意义上)与我们刚刚生成的对象相等.

to clarify the reason for maintaining a map. The need to look up a vertex based on an object arises in the following scenario. Suppose that we have generated an object. We need to look up a vertex that corresponds to an object that's equal (in the sense of operator==) to an object that we've just generated.

推荐答案

为顶点容器选择器使用listS或setS可使失效保证等于相应的标准库容器(

Using a listS or setS for the vertex container selector makes the invalidation guarantees equal to the corresponding standard library container (Iterator invalidation rules).

通常，除非删除，基于节点的容器不会使任何迭代器无效.

In general, the node-based containers do not invalidate any iterators unless removed.

在这一点上，我也想建议捆绑属性，您根本不需要维护从对象到顶点描述符/索引的映射.

At this point I would like to suggest bundled properties too, where you don't have to maintain a mapping from object to vertex descriptor/index at all.

示例(即将发布: https://www.livecoding.tv/sehe/)

这篇关于BGL:以不会使它们无效的方式存储顶点描述符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！