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

Question

我有结构,让我们称他们为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; 

这复制了吗？更基本的问题当然是我不明白向量,指针和引用是如何真正深入工作的.

Answer 1

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

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

^{✝ _{有一些限制.请注意,在您的情况下,类型仅在定义(of sn)中不完整- 在您实际使用它时,它sn是完整的,因此您也可以删除它.}}

树

如果是树,每个孩子只有一个父母.因此,在删除结构时,您将从根目录开始,每个节点只需删除其所有子节点.这将递归地工作到没有孩子的叶子.

要有效地实现这一点,您可以将孩子存储在一个boost::ptr_vector<sn>.因此,您不必自己编写析构函数 - ptr_vector将删除其所有元素.

有向无环图(DAG)

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

循环图

在循环图中,节点也可以是它自己的父节点(如果它包含循环,则直接或通过循环间接地).因此,如果每个节点删除其所有子节点,那将导致无限循环的析构函数调用.A shared_ptr也可能在这里失败,因为当你有一个相互引用的循环时shared_ptr,它们的引用计数永远不会达到零.现在是时候考虑拥有一个对象和引用它之间的区别.每个节点应该只拥有一个拥有它的父节点,但可以有几个节点引用它.所有者和唯一所有者负责删除该节点.如优良答案我上面链接所解释的,这可以通过使用的组合来实现shared_ptr和weak_ptr.