c++ - 如何使用 vector 通过指针引用递归结构

Question

我有一些结构，我们称它们为 sn，它看起来像:

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

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

A.connected_to[0] = &B; 

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

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

// ... 

A.connected_to[0] = B; 

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

Answer 1

您的第二种方法是 probably illegal .但是，在标准库的某些实现中，它可能会起作用。在这些情况下，您添加的对象将被复制(包括它们的所有子对象 - 当复制标准容器时，它包含的所有元素也会被复制)。因此，这样的数据结构仅适用于表示树。

另一方面，您的第一种方法很好，因为指向不完整类型的指针本身就是有效类型 (§3.9.2/3 - [basic.compound])^✝。由于您只存储一个指针，因此不会复制该对象。不过，当您开始删除此图表时，您必须小心。根据您要建模的图类型，实现它们时存在三种情况:

^{✝ _{There are some restrictions .请注意，在您的情况下，类型仅在定义( sn )内不完整 - 在您实际使用它时， sn已完成，因此您也可以删除它。}}

Trees

对于一棵树，每个 child 都有一个 parent 。因此，在删除结构时，您将从根开始，每个节点只需要删除其所有子节点即可。这将递归地作用于没有 child 的叶子。

为了有效地实现这一点，您可以将 child 存储在 boost::ptr_vector<sn> 中.因此，您不必自己编写析构函数 - ptr_vector将删除其所有元素。

Directed Acyclic Graphs (DAG)

在 DAG 中，一个节点可以有多个父节点，因此您必须注意不要删除同一个节点两次(如果每个节点只删除其所有子节点，就会发生这种情况 - 因此，ptr_vector 将不起作用这里)。处理这个问题的一种方法是使用引用计数——每个节点计算有多少其他节点指向它，只有当引用计数达到零时，该节点才真正被删除。您可以通过将节点存储在 std::vector<std::shared_ptr<sn> > 中来自动执行此操作(或 boost::shared_ptr 如果您使用 C++11 之前的编译器)。 shared_ptr在内部管理引用计数，并且只会在不再有 shared_ptr 时删除它指向的对象- 指向该对象的实例(当引用计数为零时)。

Cyclic Graphs

在循环图中，一个节点也可以是它自己的父节点(如果它包含循环，则可以是直接的，也可以是通过循环间接的)。因此，如果每个节点都删除其所有子节点，则会导致析构函数调用的无限循环。 shared_ptr也可能在这里失败，因为当你有一个 cycle of shared_ptr referencing each other ，它们的引用计数永远不会达到零。现在是时候考虑拥有一个对象和引用它之间的区别了。每个节点应该恰好有一个拥有它的父节点，但可以有多个引用它的父节点。所有者，并且只有所有者，负责删除该节点。正如我在上面链接的优秀答案中所解释的，这可以使用 shared_ptr 的组合来实现。和 weak_ptr .