进入智能指针，如何处理表示所有权？

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

由于节点可以单独存在，因此它们属于图（可能是也可能不是单个对象），而不是弧（即使是共享所有权）。正如您所观察到的，弧的节点对弧的所有权与 任一个 所有者的通常 shared_ptr 情况是双重的，足以使对象保持活动状态。尽管如此，您仍然可以在此处使用 shared_ptr 和 weak_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 中）需要 .

Answer 2

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?

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

1:自己写智能指针

写一个class，可以封装必要的销毁逻辑。节点 and/or arc classes 将使用您的新 class 而不是标准智能指针（而不是原始指针）。花一些时间来确保您的设计决策是可靠的。我猜你的新 class 会想要某种 functional/callable 来告诉它如何从它所在的列表中删除自己。或者可能将一些数据（比如指向节点的指针）从弧线 class 到新的 class.

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

2：标记无效弧

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

节点在其弧上迭代的频率越低，这种方法的用处就越小。所以需要做出判断。

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

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

3：使用Boost.Bimap

如果您可以使用 Boost，他们有一个看起来可以解决您的问题的容器：Boost.Bimap. But, you ask, didn't I already discount using an adjacency list? Yes, but this Bimap is more than just a way to associate nodes to each other. This container supports having additional information 与每个关系关联。也就是说，Bimap 中的每个关系都代表一个弧并且它会有一个关联对象和弧的信息。似乎很适合您的情况，并且您可以让其他人担心内存管理（这总是一件好事，前提是您可以相信某人的能力）。

进入智能指针，如何处理表示所有权？

Getting into smart pointers, how to deal with representing ownership?

c++

pointers

smart-pointers

raw-pointer