c++ - 进入智能指针，如何处理代表所有权？

Question

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

删除节点将对其每个弧调用delete。
每个弧删除均从其连接的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的情况下，仍然必须显式删除其所有弧。这完全抵消了首先不使用原始指针的观点。

节点可以单独存在。每个弧均由两个节点拥有，并且只要这两个节点都存在，就只能存在。

我应该使用其他某种智能指针来处理此问题吗？
还是原始指针只是普通的简单方法？

Answer 1

Does each arc own 2 nodes, or do 2 nodes share an individual arc's ownership?

您自己回答了这个问题:

Nodes can exist alone; each arc is owned by two nodes and it can only exist as long as these two nodes both exist.

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

Is there some other kind of smart pointer i should use to handle this? Or is raw pointer just the plain simple way to go?

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

1:编写自己的智能指针

写一个可以封装必要的销毁逻辑的类。节点和/或弧类将使用您的新类，而不是标准智能指针(和原始指针)。花一些时间来确保您的设计决策是可靠的。我猜想您的新类将需要某种函数/可调用对象，以告诉它如何从其所在的列表中删除自身。或者也许将某些数据(如指向节点的指针)从arc类转移到新类类(class)。

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

2:标记无效弧

如果您的程序不能立即释放内存，则可以采用其他方法解决弧删除。无需立即从其节点列表中删除弧，只需将弧标记为不再有效即可。当节点需要访问其弧时，它(或更好的是，其列表)将检查其访问的每个弧–如果弧无效，则可以在那时将其从列表中删除。从两个列表中删除该节点后，将使用常规的 shared_ptr功能删除弧对象。

这种方法的用处越少，节点在其弧上进行迭代的频率就越少。因此，需要作出判断。

弧如何标记为无效？天真的方法是给它一个 bool 值标志。在构造函数中将标志设置为 false，在应将圆弧视为删除时将标志设置为 true。有效，但确实需要一个新 Realm 。可以做到而不会膨胀弧度类吗？好吧，大概每个弧都需要指向其节点的指针。由于弧不拥有其节点，因此它们可能是弱指针。因此，定义弧无效的一种方法是检查任一弱指针是否为 expired()。 (请注意，当直接删除弧时(而不是通过节点的删除)，可以将弱指针手动设置为 reset()。因此，过期的弱指针不必表示关联的节点已消失，而只是弧不再指向它。)

在arc类很大的情况下，您可能希望立即丢弃其大部分内存，仅留下一个存根。您可以添加一个间接级别来完成此操作。本质上，节点将共享一个指向唯一指针的指针，并且唯一指针将指向您当前称为的弧类。删除弧时，唯一指针为 reset()，释放弧的大部分内存。当此唯一指针为null时，弧无效。 (如果您可以接受将 shared_ptr自身存储的对象，则看来Davis Herring的答案是另一种以较少的内存开销获得此效果的方法。)

3:使用Boost.Bimap

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