智能指针用于C ++ 11中的图形表示（顶点邻居） [英] Smart pointers for graph representation (vertex neighbors) in C++11
问题描述
假设你有一个包含所有顶点向量的图结构。此外，你有一个结构/类的顶点。这个顶点包含所有邻居的向量（邻接列表）。
我的问题是：我应该使用哪种类型的指针/智能指针来表示这个图？ / p>
对于二叉树，我读过，对于父节点，您应该使用原始指针。因为一个节点不拥有它的父节点。二叉树的子节点可以用std :: unique_ptr表示，因为节点拥有子节点的所有权。
但是在一个图中，多个节点可能有共同的邻居。那么，我应该使用std :: shared_ptr来做这件事吗？或者我应该使用原始指针吗？
您必须先设计节点（或边缘）所有权策略。
>例如，在您的站点的二叉树示例中，父项拥有其子节点，但不包含其父节点。这种设计可确保树中的每个节点都由另一个节点拥有，但根节点除外，因此您可以创建一个特殊情况。因为在这个例子中，每个节点只有一个所有者（它的父节点），所以 unique_ptr 可以用来为这个关系建模。在这个例子中，从孩子到父母的链接是非拥有的链接，因此不能用自己的智能指针来建模。
在二进制树的例子，你拥有的图是非循环的，定向的，并且每个节点都被指向只有一次（通过拥有指针）。
复杂的例子，该图可能是非循环的，定向的，但是节点可以被多次指向 。这样的图可以使用 shared_ptr 来建模指向链接，因为这些链接共享指针对象的所有权。
但是一定要小心。只要您的图形变为循环，则不能再专门使用 shared_ptr 。任何时候你建立一个所有权周期：
A拥有拥有C的B，拥有A
然后设置内存泄漏。这些循环可以通过 shared_ptr 或 unique_ptr 创建。但实际上，循环往往会在使用 shared_ptr 时更频繁地发生，可能仅仅是因为所有权图本质上比 unique_ptr 。
shared_ptr 包含一个辅助类来打破循环所有权模式：的weak_ptr 。这可以用来设置这样的东西：
A拥有拥有C的拥有（非拥有）weak_ptr的B A
如果图形是不定向的，并且您使用以下形式为节点A和B建模：
A指向B和B指向A
然后你立即建立一个循环，所以这两个指针都不能拥有指针。在这种情况下，你将不得不设计什么拥有什么。也许完全独立的一段代码可以拥有所有的节点，并且所有的边都可以用非拥有的指针表示。也许图可以分成一组非循环有向边（代表拥有指针）和所有其他边（非拥有指针）。事实上，这正是我们对二叉树所做的 - 拥有子指针和非拥有父指针。
无论您的设计是什么，一旦完成，您的设计会引导您判断 shared_ptr 和/或 unique_ptr 是否是实现您设计的合适工具。如果某件事总是独一无二的， unique_ptr 是一个可行的选择。如果某些东西需要由其他实体拥有， shared_ptr 可能是正确的工具（并且绝对不是 unique_ptr ）。如果 shared_ptr 所有权图表包含循环，则可以通过用 weak_ptr 替换其中一些链接来打破它们。如果您未能在您的所有权图表中检测到并破坏周期，则这些周期将导致内存泄漏。
I was wondering how to use C++11 smart pointers correctly for graph representations.
Suppose, you have a graph structure which contains a vector of all its vertices. Furthermore, you have a structure/class of vertex. This vertex contains a vector of all its neighbors (adjacency list).
My question is: which types of pointers/smart pointers should I use, to represent this graph?
For binary trees, I read, for parent nodes you should use raw pointers. Because a node doesn't own its parent. The childs of a binary tree could be represented by std::unique_ptr because the node have the ownership of the childs.
But in a graph it is possible that multiple nodes have common neighbors. So, should I use a std::shared_ptr for this? Or should I use raw pointers, anyway?
You must first design a node (or edge) ownership strategy.
For example, in the binary tree example you site, a parent owns its child nodes, but not its parent node. This design ensures that every node in the tree is owned by exactly one other node, except for the root node, which you can make a special case out of. Since in this example, each node has exactly one owner (its parent), unique_ptr can be used to model this relationship. Also in this example, the link from the child to the parent is a non-owning link, and so can not be modeled with an owning smart pointer.
In the binary tree example, your owning graph is acyclic, directed, and every node is pointed to only once (by owning pointers).
In a more complicated example, the graph might be acyclic, directed, but nodes can be pointed to more than once. Such a graph could use shared_ptr to model the pointed-to links since such links share ownership of the pointee.
However one must be careful. As soon as your graph becomes cyclic, then shared_ptr can no longer be exclusively used. Any time you set up a cycle of ownership:
A owns B which owns C which owns A
then you set up a memory leak. Such cycles can be created with either shared_ptr or unique_ptr. But in practice, cycles tend to happen more often with the use of shared_ptr, probably just because the ownership diagram is inherently more complex than that of unique_ptr.
shared_ptr contains a helper class to break cyclic ownership patterns: weak_ptr. This can be used to set up something like:
A owns B which owns C which has a (non-owning) weak_ptr to A
If the graph is undirected, and you model nodes A and B with:
A points to B and B points to A
then you immediately set up a cycle, and so both of these pointers can not be owning pointers. In such a situation, you will have to design what owns what. Perhaps a completely separate piece of code could own all of the nodes, and all of the edges can be represented with non-owning pointers. Perhaps the graph can be partitioned into a set of acyclic directed edges (representing owning pointers), and all other edges (non-owning pointers). Indeed, this is exactly what we did with the binary tree -- owning child pointers and non-owning parent pointers.
Whatever your design, once it is done, your design will lead you to whether shared_ptr and/or unique_ptr are appropriate tools to implement your design. If something is always going to be uniquely owned, unique_ptr is a viable option. If something needs to be owned by several other entities, shared_ptr might be the correct tool (and definitely not unique_ptr). If the shared_ptr ownership graph contains cycles, they can be broken by replacing some of those links with weak_ptr. If you fail to detect and break cycles in your ownership graph, the cycles will result in memory leaks.
这篇关于智能指针用于C ++ 11中的图形表示（顶点邻居）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
