如何使用向量通过指针引用递归结构 [英] How to refer to recursive structs through pointers using vectors
问题描述
我有一个结构，我们称它们为sn，看起来像:
I have structs, let's call them sn, that look like:
struct sn {
string name;
vector<sn*> connected_to;
};
现在，假设我已经从0-9声明了connected_to矢量；我正在将sn A连接到sn B:
Now, suppose I have the connected_to vector already declared from 0 - 9; and I'm connecting sn A, to sn B:
A.connected_to[0] = &B;
我有种错误的感觉.本质上，我想做的是在连接结构时避免复制结构...即:
I have a feeling that I'm going about this the wrong way. Essentially what I'm trying to do is avoid copying the struct when I'm connecting the structs... i.e:
struct sn {
string name;
vector<sn> connected_to;
};
// ...
A.connected_to[0] = B;
此副本有什么用吗?更根本的问题当然是我不了解向量，指针和引用是如何真正深入地工作的.
Does this copy anything? The more fundamental problem is of course I don't understand how vectors, pointers, and referencing really works deeply.
推荐答案
Your second approach is probably illegal. However, in some implementations of the standard library it might work. In those cases, the objects you add would get copied (including all their children - when a standard container is copied, all the elements it contains are copied too). Thus, such a data-structure would only be suitable for representing a tree.
另一方面，您的第一种方法很好，因为指向不完整类型的指针本身就是有效类型(第3.9.2.2/3节-[basic.compound])✝.由于仅存储指针，因此不会复制对象.但是，当您开始删除此图时，必须小心.根据要建模的图形类型，实现它们时会出现以下三种情况:
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:
✝ 有一些限制.请注意，在您的情况下，该类型仅在sn的定义内不完整-在您实际使用该类型时，sn是完整的，因此您也可以将其删除.
✝There are some restrictions. 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.
如果是一棵树，每个孩子只有一个父母.因此，在删除结构时，您将从根开始，并且每个节点仅需删除其所有子节点.这将对没有孩子的叶子进行递归工作.
In case of a tree, every child has exactly one parent. Thus, when deleting the structure, you would start from the the root, and each node would just have to delete all of its children. This would work recursively to the leaves, which have no children.
To implement this efficiently, you could store the children in a boost::ptr_vector<sn>. Thus, you will not have to write a destructor yourself - the ptr_vector will delete all its elements.
在DAG中，一个节点可以有多个父节点，因此您必须注意不要删除同一节点两次(如果每个节点仅删除其所有子节点，则会发生这种情况-因此，ptr_vector将不起作用这里).解决此问题的一种方法是使用引用计数-每个节点都会计数指向该节点的其他节点的数量，并且只有当引用计数达到零时，该节点才真正被删除.您可以通过将节点存储在std::vector<std::shared_ptr<sn> >(或 boost::shared_ptr (如果您使用的是C ++ 11之前的编译器). shared_ptr在内部管理引用计数，并且仅在不再有指向该对象的shared_ptr -instances(引用计数为零时)时才删除它指向的对象.
In a DAG a node can have multiple parents, thus you have to take care not to delete the same node twice (this would happen if each node just deletes all its children - for this reason, a ptr_vector will not work here). One way to handle this is to use reference-counting - each nodes counts how many other nodes point to it, and only when the reference-count reaches zero, the node is actually deleted. You can automate this by storing the nodes in a std::vector<std::shared_ptr<sn> > (or boost::shared_ptr if you use a pre-C++11 compiler). The shared_ptr manages the reference-counting internally, and will only delete the object it points to when there are no more shared_ptr-instances pointing to that object (when the reference-count is zero).
在循环图中，节点也可以是其自己的父节点(直接(如果它包含循环)或间接地通过一个循环).因此，如果每个节点删除其所有子节点，则将导致析构调用的无限循环. shared_ptr在这里也可能会失败，因为当您有 shared_ptr互相引用的周期时，它们的引用-计数永远不会达到零.现在该考虑拥有一个对象和引用之间的区别了.每个节点都应拥有一个恰好一个父节点，但可以有多个引用它的节点.所有者(只有所有者)负责删除该节点.如我上面链接的出色答案中所述，可以使用shared_ptr和weak_ptr的组合来实现.
In a cyclic graph, a node can also be its own parent (either directly, if it contains loops, or indirectly, through a cycle). Thus, if each node deletes all its children, that would result in an infinite loop of destructor-calls. A shared_ptr could also fail here, because when you have a cycle of shared_ptr referencing each other, their reference-count will never reach zero. Now it is time to think about the difference between owning an object and referencing it. Each node should have exactly one parent that owns it, but can have several that reference it. The owner, and only the owner, is responsible for deleting that node. As explained in the excellent answer I linked above, this can be implemented using a combination of shared_ptr and weak_ptr.
这篇关于如何使用向量通过指针引用递归结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
