C++ 11中图形表示(顶点邻居)的智能指针

Question

我想知道如何正确使用C++ 11智能指针进行图形表示.

假设您有一个图形结构,其中包含所有顶点的向量.此外,您有一个顶点的结构/类.该顶点包含其所有邻居(邻接列表)的向量.

我的问题是:我应该使用哪种类型的指针/智能指针来表示这个图形？

对于二进制树,我读到,对于父节点,您应该使用原始指针.因为节点不拥有其父节点.二叉树的子节点可以由std :: unique_ptr表示,因为该节点具有子节点的所有权.

但是在图中,多个节点可能具有共同的邻居.那么,我应该使用std :: shared_ptr吗？或者我应该使用原始指针吗？

Answer 1

您必须首先设计节点(或边缘)所有权策略.

例如,在您站点的二叉树示例中,父级拥有其子节点,但不拥有其父节点.这种设计确保树中的每个节点都由一个其他节点拥有,除了根节点,您可以从中创建一个特殊情况.由于在此示例中,每个节点只有一个所有者(其父级),unique_ptr因此可用于建模此关系.同样在这个例子中,从子节点到父节点的链接是非拥有链接,因此不能用拥有的智能指针建模.

在二叉树例子,你拥有图形是无环,导演,每一个节点指向到只有一次(通过拥有指针).

在一个更复杂的示例中,图形可能是非循环的,定向的,但节点可以多次指向.这样的图可以用于shared_ptr对指向链接建模,因为这样的链接共享指针对象的所有权.

但是必须要小心.一旦图形变为循环图形,shared_ptr就不能再单独使用.任何时候你建立一个所有权周期:

A owns B which owns C which owns A

然后你设置了内存泄漏.这样的周期可以与任一被创建shared_ptr或unique_ptr.但在实践中,循环往往更频繁地使用shared_ptr,可能只是因为所有权图本质上比那些更复杂unique_ptr.

shared_ptr包含一个帮助类来打破循环所有权模式: weak_ptr.这可用于设置如下内容:

A owns B which owns C which has a (non-owning) weak_ptr to A

如果图形是无向的,并且您使用以下方法为节点A和B建模:

A points to B and B points to A

然后你立即设置一个循环,所以这两个指针都不能拥有指针.在这种情况下,你将不得不设计什么拥有什么.也许完全独立的代码片段可以拥有所有节点,并且所有边缘都可以用非拥有指针来表示.也许图可以被划分为一组非循环有向边(表示拥有指针)和所有其他边(非拥有指针).实际上,这正是我们对二叉树所做的 - 拥有子指针和非拥有父指针.

无论您的设计是什么,一旦完成,您的设计将引导您确定是否shared_ptr和/或是unique_ptr实施设计的适当工具.如果某些东西总是独一无二,那么这unique_ptr是一个可行的选择.如果某些东西需要由其他几个实体拥有,shared_ptr那么可能是正确的工具(绝对不是unique_ptr).如果shared_ptr所有权图包含循环,则可以通过将这些链接替换为某些循环来打破它们weak_ptr.如果您未能检测并中断所有权图中的周期,则周期将导致内存泄漏.