如何使用向量通过指针引用递归结构

2024-02-19

我有结构，我们称它们为 sn，看起来像：

struct sn {
    string name;
    vector<sn*> connected_to;
};

现在，假设我已经从 0 - 9 声明了connected_to 向量；我将 sn A 连接到 sn B：

A.connected_to[0] = &B;

我有一种感觉，我正在以错误的方式处理这件事。本质上我想做的是在连接结构时避免复制结构......即：

struct sn {
    string name;
    vector<sn> connected_to;
};

// ... 

A.connected_to[0] = B;

这会复制任何东西吗？更根本的问题当然是我不明白向量、指针和引用是如何真正深入工作的。

你的第二种方法是可能非法 https://stackoverflow.com/questions/8329826/can-standard-container-templates-be-instantiated-with-incomplete-types。但是，在标准库的某些实现中它可能会起作用。在这些情况下，您添加的对象将被复制（包括它们的所有子对象 - 当复制标准容器时，它包含的所有元素也会被复制）。因此，这样的数据结构只适合表示树。

Your first approach, on the other hand, is fine, because a pointer to an incomplete type is itself a valid type (§3.9.2/3 - [basic.compound])^✝. Since you only store a pointer, the object will not get copied. You have to take care though when you start deleting this graph. Depending on what type of graph you are modeling, there are three scenarios when implementing them:

^✝_{^{There are some restrictions https://stackoverflow.com/a/2517455/160206. Note that in your case the type is only incomplete inside the definition (of sn) - at the point you actually use it, sn is complete, hence you can also delete it then.}}

Trees http://en.wikipedia.org/wiki/Tree_%28data_structure%29

对于一棵树来说，每个孩子只有一个父母。因此，在删除结构时，您将从根开始，每个节点只需删除其所有子节点。这将递归地作用于没有子节点的叶子。

为了有效地实现这一点，您可以将子项存储在boost::ptr_vector<sn> http://www.boost.org/doc/libs/release/libs/ptr_container/doc/ptr_vector.html。因此，您不必自己编写析构函数 -ptr_vector将删除其所有元素。

有向无环图 (DAG) http://en.wikipedia.org/wiki/Directed_acyclic_graph

在 DAG 中，一个节点可以有多个父节点，因此您必须注意不要两次删除同一个节点（如果每个节点只删除其所有子节点，就会发生这种情况 - 因此，ptr_vector在这里不起作用）。处理此问题的一种方法是使用引用计数 - 每个节点都会计算有多少其他节点指向它，只有当引用计数达到零时，该节点才会被实际删除。您可以通过将节点存储在std::vector<std::shared_ptr<sn> > (or boost::shared_ptr http://www.boost.org/doc/libs/release/libs/smart_ptr/shared_ptr.htm如果您使用 C++11 之前的编译器）。这shared_ptr内部管理引用计数，只有当没有更多的对象时才会删除它指向的对象shared_ptr- 指向该对象的实例（当引用计数为零时）。

循环图 http://en.wikipedia.org/wiki/Cycle_graph

在循环图中，节点也可以是其自己的父节点（如果它包含循环，则可以直接作为其父节点，如果包含循环，则可以间接作为其父节点）。因此，如果每个节点删除其所有子节点，则会导致析构函数调用的无限循环。 Ashared_ptr也可能在这里失败，因为当你有一个的周期shared_ptr互相引用 https://stackoverflow.com/a/701711/160206，它们的引用计数永远不会达到零。现在是时候考虑一下两者之间的区别了owning一个物体和参考它。每个节点应该有正好一个拥有它的父级，但可以有多个引用它。所有者，并且只有所有者，负责删除该节点。正如我上面链接的优秀答案中所解释的，这可以使用以下组合来实现shared_ptr and weak_ptr.

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)