图形数据结构内存管理

我想为我的项目实现一个自定义图形数据结构，我有一个关于适当的内存管理的问题。

本质上，数据结构将包含具有两个向量的节点:一个用于进入节点的边，另一个用于从节点出来的边(没有循环边)。这个图是连通的。该图还将包含一个"入口"节点，该节点没有任何边进入。边就是指向节点的指针。

我的问题是:为这种类型的数据结构清理内存的最佳方法是什么?如果只有一条入口边，我知道该怎么做(此时这个结构退化为n元树)，但我不确定在有多个节点的情况下该怎么做，这些节点的边都进入一个节点。我不能只是从任意的入口节点调用delete，因为这可能会导致之后的"双重自由"bug。

例如，假设我有这个子图:

C <-- B
^
|
A

如果我要从节点B调用delete，我将删除分配给C的内存，但A仍然有指向它的指针。所以如果我想清除所有与A有连接的节点，我就会得到双重错误。

当您删除组件时，您将需要执行搜索以确定哪个节点仍然连接到输入边。如果您最终有多个连接的组，您将需要找出其中哪一个包含入口节点并删除所有其他的。

对于这个不存在贪心(局部)算法，可以通过一个简单的思想实验来证明:

设A, B为仅通过节点n与相连的子图，取去该子图。我们剩下两个不连通的子图。没有办法知道(没有每个节点的一大堆状态)，如果我们只是删除了a或B的入口节点的唯一路径，并且，有必要弄清楚，以便可以做出适当的选择，删除a或B。

即使每个节点都存储了到入口节点的所有路由，这也意味着每当你删除一个节点时，你必须清除所有节点中的所有路由。

解决方案草图

让我们用图形表示一下我们需要做的事情:

首先，将要删除的节点涂成黑色。然后对遇到的每个节点执行以下操作:

对于未着色的节点:

对于彩色节点:

最后，我们将知道删除当前节点后哪些连接的组件将存在。所有不包含入口节点的连接组件(加上原始要删除的节点)必须删除(注意:如果要删除的节点是入口节点，则可能会删除所有单个节点…)

实施

你需要一个像下面这样的数据结构:

struct cleanup {
    vector<set<node*>> colors;
    node* to_be_deleted;
    size_t entry_component;
};

列表向量的索引将是你的"color"。"color black"用to_be_deleted表示。最后，entry_component将包含具有入口节点的颜色的索引。

现在，前面的算法可以实现了。有很多事情需要考虑，并且最终的实现可能会有所不同，这取决于您已经为其他操作保留了什么样的支持结构。

答案取决于图的复杂性:

如果图形是树状的，每个父节点都可以拥有它的子节点，并在析构函数中删除它们。
如果图是一个有向无环图，一个简单而高效的处理方法是在节点上做引用计数。
如果图形是循环的，你就不走运了。您需要跟踪图中的每个节点，然后进行垃圾收集。根据您的用例，您可以通过
进行收集。
- 在完成完整图形时清理所有内容，或通过
- 重复标记所有连接的节点，清理所有不可达的节点。

如果有任何可能摆脱选项1或2(可能调整问题以确保图满足约束)，你应该这样做;选项3意味着在代码复杂性和运行时方面有很大的开销。

有几种方法。一种方法是让节点知道其他节点有哪些边。因此，如果你从B中删除C, C将需要从A中删除与它相关的边。因此，稍后当你删除/删除A时，它不会尝试删除C。

std::shared_ptr或其他类型的引用计数也可以为您工作。

在实现图形时，有一个简单的方法可以避免内存问题:不要使用指针来表示边。

相反，给每个节点一个唯一的ID号(一个递增的整数计数器就足够了)。保持全局unordered_map<int, shared_ptr<Node> >，以便您可以通过其ID号快速查找任何节点。然后，每个节点可以将其边表示为一组整数节点id。

在你删除一个节点(即从节点的全局映射中删除它)之后，有可能其他一些节点现在会有"悬挂边"，但这很容易检测和处理，因为当你在全局映射中查找现在删除的节点的ID时，查找将失败。然后，您可以通过忽略该边或删除该边(即源节点)等方式优雅地响应。

这样做的优点:代码仍然非常简单，并且不需要担心引用循环、内存泄漏或双自由度。

缺点:遍历图形的效率有点低(因为做映射查找比简单的指针解引用需要更多的循环)，并且(取决于你在做什么)"悬空边"可能需要偶尔清理扫描(但这些很容易做到……只需遍历全局映射，对于每个节点，检查其边集中的每条边，并删除具有全局映射中不存在的id的边

更新:如果你不喜欢做大量的unordered_map查找，你可以通过使用weak_ptr代替表示你的边来获得非常类似的功能。当weak_ptr所指向的对象消失时，weak_ptr会自动变为NULL/无效。

相关内容