Question

我试图在 c++ 中写一个小小的< a href="http://en.wikipedia.org/wiki/Quad-sedge" rel=“nofollow” >quaddge c++ (把它看作是某种图表) 。每个节点都应该跟踪他的邻居。我只能跟踪即将流出的弧。

第一个想法是使用指针来做到这一点:

struct Node {
         //....
         Node * n1,n2,... nk;
};

然而,当您必须执行复制构建器 ^{(首先复制所有节点,然后将旧节点的每个指针绘制到新节点的相对指针上) 时,这个方法会令人心痛。}

我认为,在这种情况下,使用整数指数而不是指针是更好的办法。

 struct Node {
        //....
        int n1,n2,...nk;
 };

Is this approach common and correct? If it is, which is the proper container to map indices to nodes?

std:::vector<Node> 可能是最有效的方法,我只需使用矢量中的索引来指一个节点,但从图形中删除一个节点会非常复杂(需要重新标定图表中的每个引用)。

使用 std:: Unorded_map<int,Node> 将稍好一点,但还需要跟踪自由名称(如果我插入节点1,2,3,然后删除2,我需要跟踪名称2的存在情况)。

想想一个池式分配器,它用其基底的偏移作为指针类型。

是否有这种热门的集装箱(在Boost或其他任何热门图书馆)?

Answer 1

在容器中永久使用 int 索引是脆弱的,因为您不能在容器中间删除或插入项目而不重新修改所有索引。在复制或序列操作中临时使用索引会更好:在不依赖节点标识的操作中,使用第一个方法描述的指针,并只在操作期间按需要设定节点(例如,其索引)的临时身份。

例如,在您在复制构建器中开始复制操作之前, 创建一个 < code> victor< nodegt; 和一个 unordered_ map< node*,int> 。执行两次复制 : 首先, 添加节点的复制件而不引用矢量, 并将旧节点的地址添加到地图上。然后再次通过您的节点, 并通过使用未排序地图中的索引查找矢量中新节点的地址来解决引用。

Answer 2

我认为引入这个新的节点识别概念只会让你的生活更加艰难

如果您需要为每个节点设定一个独特的代号以进行序列化,请在那个时间创建代号,或者将节点地址投到一整点上。

如果您想要复制您的图表, 您可以做一个临时 std:: 未排序的图, 将旧节点映射为新节点, 以跟踪已经复制的节点。

深重复制节点的函数将是递归的; 它会在地图中添加旧节点和新节点, 然后深重复制尚未在地图中的任何相邻节点。

友情链接