3

我正在尝试用 c++ 编写一个小四边形类（将其视为某种图）。每个节点都应该跟踪他的邻居。我必须只跟踪传出的弧线。

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

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

但是，当您必须实现复制构造函数*（首先复制所有节点，然后将每个指向旧节点的指针映射到指向新节点的相对指针）时，这种方法特别痛苦。

我认为在这种情况下使用整数索引而不是指针会是一个更好的主意。

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

这种方法常见且正确吗？如果是，哪个是将索引映射到节点的正确容器？

std::vector<Node>可能是最有效的方法，我可以只使用向量中的索引来引用节点，但不幸的是，从图中删除节点会非常复杂（需要重新调整图中的每个引用）。

使用std::unordered_map<int,Node>会好一点，但它仍然需要跟踪空闲名称（如果我插入节点 1、2、3 然后删除 2，我需要跟踪名称 2 可用的事实）。

我需要的和堆的实现很相似。想想一个池分配器，它使用从其基址的偏移量作为指针类型。

有没有像这样的流行容器（在 Boost 或任何其他流行的库中）？

*它的用处不限于复制构造函数，例如考虑序列化

4

2 回答 2

1

在容器中永久使用int索引是脆弱的，因为如果不重新排列所有索引，您就无法在容器中间删除或插入项目。在复制或序列化操作期间临时使用索引要好得多：使用您在第一种方法中描述的指针用于不依赖节点标识的操作，并创建节点的临时标识（例如，它的索引）仅用于需要的操作的持续时间。

例如，在复制构造函数中开始复制操作之前，创建一个vector<Node*>和一个unordered_map<Node*,int>。分两遍执行复制：首先，将不带向量引用的节点的副本添加到映射中，并将旧节点的地址添加到映射中。然后再次遍历您的节点，并通过使用无序映射中的索引在向量中查找新节点的地址来解析引用。

于 2012-05-24T15:19:46.047 回答
0

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

如果您需要每个节点的唯一 id 用于序列化，请在那时创建 id 或将节点地址转换为 int。

如果要复制图形，可以制作一个临时的 std::unordered_map ，将旧节点映射到新节点，以跟踪哪些节点已被复制。

用于深度复制节点的函数将是递归的；它会将旧节点和新节点添加到地图中，然后深度复制尚未在地图中的任何相邻节点。

于 2012-05-24T15:18:17.873 回答