weak_ptr VS shared_ptr in graph node parent list

Question

I have a directed acyclic graph implemented by Graph and Node classes. Each node has a list of pointers to childern and a list of pointers to parents. I added parents recently because some algorithms demanded fast access to parent list and the graph is small, just few connections per node, so there's no memory issue.

The Child list uses std::shared_ptr so that nodes are kept in memory at least as long as they have parents. But I don't want a node to own its parents, so I used weak_ptr for the pointers to parents.

But then there was a problem with the algorithms. An algorithm must create a new shared_ptr from the weak_ptr, so I can't directly use operator==, and using standard functions such as std::find() require writing a lambda function which called my_weak_ptr.lock() and then compares it to some shared_ptr.

If I switch to shared_ptr, any small bug in the code reponsible for node removal may lead to a memory leak. Or if I have a pointer to a node already removed, the code will be able to access a node not supposed to exist, so finding some bugs may become a lot harder. But working with shared_ptr is as safe as weak_ptr in terms of not dereferencing/deleting/etc. when not supposed to, (so it's better than raw C++ pointer) and std::find() can be used directly because shared_ptr can be dereferenced, unlike weak_ptr.

Is there a "better" design here, or it's an issue of this specific situation depending on e.g. how much does it matter if I do the extra operation of weak_ptr::lock() or take a risk of hard-to-find bugs?

Answer 1

As you said yourself, using shared_ptr in both directions will create circles that create mem leaks and are hard to find and to break - you will lose (nearly) all of the benefits shared_ptr provides. So weak_ptr it shall be.

You say your algorithms have to lock the weak_ptr - I beg to differ. The algorithms have to get a parent shared_ptr from the node. It's the node's task to lock the parent weak_ptr and give back the result, either set correctly to a parent node or to NULL.

It's an implementation detail wether the nodes store their parents as shared_ptr or weak_ptr. Encapsulate that detail by only providing shared_ptrs to any clients.

class Node
{
  /* ... */
  std::weak_ptr<Node> parent;
public:
  std::shared_ptr<Node> getParent()
  {
    return parent.lock();
  }
};

Edit: Of course conceptually the same applies if there's more than one parent.

Edit2: In the comments you mention algorithms iterating over your parents list, making it necessary to write lambdas for each algorithm. If you use those algorithms often, consider to write an iterator adapter that automatically locks the target weak_ptr and gives back a shared_ptr:

template <class WPIterator>
struct LockTheWeakIterator
{
  //static_assert that WPiterator's value_type is some weak_ptr
  //typedef all those iterator typedefs
  typedef typename WPIterator::value_type::element_type element_type;

  shared_ptr<element_type> operator*()
  { return iter->lock(); }

  //provide all the other operators - boost.operators might help with that...

  WPIterator iter;
};

template <class IT>
LockTheWeakIterator<It> lockTheWeak(It iter);


//somewhere...
auto theParentIter = std::find_if(lockTheWeak(parents.begin()), 
  lockTheWeak(parents.end()), 
  whatIAmLookingFor);

Answer 2

Most directed acyclic graphs should not need weak pointers to their parents at all, but work with plain pointers. In both cases it is each node's responsibility to delete themselves from each client's parent list once they get deleted. If you need to retrieve a shared pointer from some parent pointer in some special situation you can use std::shared_from_this in a similar way as you'd use lock() right now. This way you save the work to create and handle shared pointers all over the place, but only where you need them.