进入智能指针，如何处理代表所有权? [英] Getting into smart pointers, how to deal with representing ownership?

问题描述

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

i've made a dynamic graph structure where both nodes and arcs are classes (i mean arcs are an actual instance in memory, they are not implied by an adjacency list of nodes to nodes). Each node has a list of pointers to the arcs it's connected to. Each arc has 2 pointers to the 2 nodes it's connecting.

删除节点将对其每个弧调用删除. 每个弧删除均会从其连接的2个节点的弧列表中删除其指针. 简化:

Deleting a node calls delete for each of its arcs. Each arc delete removes its pointer from the arcs lists in the 2 nodes it connects. Simplified:

~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的情况下，仍然必须显式删除其所有弧.完全克服了首先不使用原始指针的问题.

If i want to start using smart pointers here, how do i proceed? Does each arc own 2 nodes, or do 2 nodes share an individual arc's ownership? I was thinking about a shared_ptr, but shared pointer would only delete the arc when both nodes are deleted. If i delete only one node i would still have to explicitly delete all its arcs if i used shared_ptr. And that totally defeats the point of not using raw pointers in the first place.

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

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

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

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?

推荐答案

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

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

您自己回答了这个问题:

You answered this question yourself:

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

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.在您的情况下，两个节点共享弧的所有权.

When object A owns object B, then object A can exist after destroying B, but destroying A implies destroying B. Applied to your case, the two nodes share ownership of the arc.

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

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?

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

Ah, yes. That is the real question. There is no pre-made smart pointer for this situation. However, I would not go with raw pointers in your node and/or arc classes. That would mean those classes would need to implement memory management on top of their primary purpose. (Much better to let each class do one thing well, then try to do many things and fail.) I see a few viable options.

1:编写自己的智能指针

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

Write a class that can encapsulate the necessary destruction logic. The node and/or arc classes would use your new class instead of standard smart pointers (and instead of raw pointers). Take some time to make sure your design decisions are solid. I'm guessing your new class would want a functional/callable of some sort to tell it how to remove itself from the lists it is in. Or maybe shift some data (like the pointers to the nodes) from the arc class to the new class.

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

I haven't worked out the details, but this would be a reasonable approach since the situation does not fit any of the standard smart pointers. The key point is to not put this logic directly in your node and arc classes.

2:标记无效弧

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

If your program can stand not immediately releasing memory, you may be able to take a different approach to resolving an arc deletion. Instead of immediately removing an arc from its nodes' lists, simply flag the arc as no longer valid. When a node needs to access its arcs, it (or better yet, its list) would check each arc it accesses – if the arc is invalid, it can be removed from the list at that time. Once the node has been removed from both lists, the normal shared_ptr functionality will kick in to delete the arc object.

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

The usefulness of this approach decreases the less frequently a node iterates over its arcs. So there is a judgement call to be made.

如何将弧标记为无效?天真的方法是给它一个布尔标志.在构造函数中将标志设置为false，在应将圆弧视为删除时将标志设置为true.有效，但确实需要一个新领域.可以在不使弧度等级膨胀的情况下完成此操作吗?好吧，大概每个弧都需要指向其节点的指针.由于弧不拥有其节点，因此它们可能是弱指针.因此，定义弧无效的一种方法是检查任一弱指针是否为expired(). (请注意，当直接删除弧时(而不是通过节点的删除)可以手动reset()弱指针.因此，过期的弱指针不必表示关联的节点已消失，仅是弧不再指向它. )

How would an arc be flagged invalid? The naive approach would be to give it a boolean flag. Set the flag to false in the constructors, and to true when the arc should be considered deleted. Effective, but does require a new field. Can this be done without bloating the arc class? Well, presumably, each arc needs pointers to its nodes. Since the arc does not own its nodes, these are probably weak pointers. So one way to define an arc being invalid is to check if either weak pointer is expired(). (Note that the weak pointers could be manually reset() when the arc is being deleted directly, not via a node's deletion. So an expired weak pointer need not mean the associated node is gone, only that the arc no longer points to it.)

在arc类相当大的情况下，您可能希望立即丢弃其大部分内存，仅留下一个存根.您可以添加一个间接级别来完成此操作.本质上，节点将共享一个指向唯一指针的指针，并且该唯一指针将指向您当前称为的弧类.删除弧时，唯一指针为reset()，从而释放了弧的大部分内存.当此唯一指针为null时，弧无效. (如果您可以接受将shared_ptr本身存储的对象，则看起来戴维斯·赫林(Davis Herring)的答案是获得这种效果的另一种方式.)

In the case where the arc class is sizeable, you might want to discard most of its memory immediately, leaving just a stub behind. You could add a level of indirection to accomplish this. Essentially, the nodes would share a pointer to a unique pointer, and the unique pointer would point to what you currently call your arc class. When the arc is deleted, the unique pointer is reset(), freeing most of the arc's memory. An arc is invalid when this unique pointer is null. (It looks like Davis Herring's answer is another way to get this effect with less memory overhead, if you can accept an object storing a shared_ptr to itself.)

3:使用Boost.Bimap

如果您可以使用Boost，则它们的容器看起来可以解决您的问题:其他信息与每个关系相关联.也就是说，Bimap中的每个关系将代表一个弧，并且将具有与该弧的信息相关联的对象.似乎很适合您的情况，并且您可以让其他人担心内存管理(如果您可以相信某人的能力，那就总是一件好事.)

If you can use Boost, they have a container that looks like it would solve your problem: 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 associated with each relation. That is, each relation in the Bimap would represent an arc and it would have an associated object with the arc's information. Seems to fit your situation well, and you would be able to let someone else worry about memory management (always a nice thing, provided you can trust that someone's abilities).

这篇关于进入智能指针，如何处理代表所有权?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！