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

Question

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.

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);
    }

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?

Answer 1

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.

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: Write your own smart pointer

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: Flag invalid arcs

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.

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.)

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: Use 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).

Answer 2

Since nodes can exist alone, they are owned by the graph (which might or might not be a single object), not the arcs (even as shared ownership). The ownership of an arc by its nodes is, as you observed, dual to the usual shared_ptr situation of either owner being sufficient to keep the object alive. You can nonetheless use shared_ptr and weak_ptr here (along with raw, non-owning pointers to the nodes):

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();
  }
};

Obviously other Node operations have to check for empty weak pointers and perhaps clean them out periodically.

Note that exception safety (including vs. bad_alloc in constructing the shared_ptr) requires more care in constructing an Arc.