4

我已经制作了一个动态图结构，其中节点和弧都是类（我的意思是弧是内存中的实际实例，它们不是由节点到节点的邻接列表暗示的）。每个节点都有一个指向它所连接的弧的指针列表。每条弧都有 2 个指向它所连接的 2 个节点的指针。

删除一个节点调用它的每个弧的删除。每个弧删除从它连接的 2 个节点的弧列表中删除其指针。简化：

~node()
    {
    while(arcs_list.size())
        {
        delete arcs_list[arcs_list.size()-1];
        }
    }

~arc()
    {
    node_from.remove_arc(this);
    node_to.remove_arc(this);
    }

如果我想在这里开始使用智能指针，我该如何进行？每个弧是否拥有 2 个节点，或者 2 个节点是否共享单个弧的所有权？我在考虑一个 shared_ptr，但共享指针只会在删除两个节点时删除弧。如果我只删除一个节点，如果我使用 shared_ptr，我仍然必须明确删除它的所有弧。这完全违背了首先不使用原始指针的观点。

节点可以单独存在；每条弧由两个节点拥有，并且只有这两个节点都存在，它才能存在。

我应该使用其他类型的智能指针来处理这个问题吗？还是原始指针只是简单的方法？

4

2 回答 2

4

每个弧是否拥有 2 个节点，或者 2 个节点是否共享单个弧的所有权？

你自己回答了这个问题：

节点可以单独存在；每条弧由两个节点拥有，并且只有这两个节点都存在，它才能存在。

当对象 A 拥有对象 B 时，对象 A 可以在销毁 B 后存在，但销毁 A 意味着销毁 B。应用于您的情况，两个节点共享弧的所有权。

我应该使用其他类型的智能指针来处理这个问题吗？还是原始指针只是简单的方法？

是的。这是真正的问题。没有针对这种情况的预制智能指针。但是，我不会在您的节点和/或弧类中使用原始指针。这意味着这些类需要在其主要目的之上实现内存管理。（最好让每个班级做好一件事，然后尝试做很多事情并失败。）我看到了一些可行的选择。

1：编写自己的智能指针

编写一个可以封装必要的销毁逻辑的类。节点和/或弧类将使用您的新类而不是标准智能指针（而不是原始指针）。花一些时间来确保您的设计决策是可靠的。我猜你的新类需要某种功能/可调用来告诉它如何从它所在的列表中删除自己。或者可能将一些数据（如指向节点的指针）从 arc 类转移到新的班级。

我还没有弄清楚细节，但这将是一种合理的方法，因为这种情况不适合任何标准的智能指针。关键是不要将此逻辑直接放在您的节点和弧类中。

2：标记无效弧

如果您的程序不能立即释放内存，您可以采取不同的方法来解决弧删除问题。不要立即从其节点列表中删除弧，只需将弧标记为不再有效。当一个节点需要访问它的弧时，它（或者更好的是，它的列表）会检查它访问的每个弧——如果弧是无效的，它可以在那个时候从列表中删除。从两个列表中删除节点后，shared_ptr将启动正常功能以删除弧对象。

这种方法的有用性会降低节点在其弧上迭代的频率越低。因此，需要做出判断。

如何将弧标记为无效？天真的方法是给它一个布尔标志。将标志设置为false在构造函数中，以及true何时应该考虑删除弧。有效，但确实需要一个新的领域。这可以在不使 arc 类膨胀的情况下完成吗？好吧，大概每个弧都需要指向其节点的指针。由于弧不拥有它的节点，这些可能是弱指针。因此，定义弧无效的一种方法是检查任一弱指针是否为expired(). （请注意，当弧被直接删除时，弱指针可以手动reset()删除，而不是通过节点的删除。因此，过期的弱指针不一定意味着关联的节点已经消失，只是弧不再指向它。）

在 arc 类相当大的情况下，您可能希望立即丢弃它的大部分内存，只留下一个存根。您可以添加一个间接级别来完成此操作。本质上，节点将共享一个指向唯一指针的指针，而唯一指针将指向您当前调用的弧类。当弧被删除时，唯一指针是reset()，释放弧的大部分内存。当此唯一指针为空时，弧无效。（看起来戴维斯鲱鱼的答案是另一种以更少的内存开销获得这种效果的方法，如果您可以接受一个将 a 存储shared_ptr到自身的对象。）

3：使用Boost.Bimap

如果您可以使用 Boost，他们有一个看起来可以解决您的问题的容器：Boost.Bimap。但是，你问，我不是已经使用邻接列表打折了吗？是的，但是这个 Bimap 不仅仅是一种将节点相互关联的方式。此容器支持具有与每个关系相关联的附加信息。也就是说，Bimap 中的每个关系都将表示一个弧，并且它将具有一个与弧信息相关联的对象。似乎很适合您的情况，并且您可以让其他人担心内存管理（如果您可以信任某人的能力，这总是一件好事）。

于 2019-04-19T07:40:02.133 回答
2

由于节点可以单独存在，它们属于图（可能是也可能不是单个对象），而不是弧（即使作为共享所有权）。正如您所观察到的，弧的节点对弧的所有权与任何所有者都足以使对象保持活动状态的通常shared_ptr情况是双重的。尽管如此，您仍然可以在此处使用和（以及指向节点的原始、非拥有指针）：shared_ptrweak_ptr

struct Node;
struct Arc {
  Node *a,*b;
private:
  std::shared_ptr<Arc> skyhook{this};
public:
  void free() {skyhook.reset();}
};
struct Node {
  std::vector<std::weak_ptr<Arc>> arcs;
  ~Node() {
    for(const auto &w : arcs)
      if(const auto a=w.lock()) a->free();
  }
};

显然，其他Node操作必须检查空的弱指针，并可能定期清除它们。

请注意，异常安全（包括与 bad_alloc构造 . 的对比shared_ptr）在构造Arc.

于 2019-04-19T05:37:48.013 回答