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?

Why aren't you removing the references from the children when the parent is destroyed? — Yochai Timmer
When a node has no parents and is a candidate for automatic deletion, by that time its parent list should be empty and of course no node points to it. But if by mistake something doesn't happen right, if there's any kind of bug there - it would be hard to find. What I'm saying is, children lists and parent lists have to be synchronized perfectly. — cfa45ca55111016ee9269f0a52e771
But with weak_ptr you care less because the only bugs there are visible in the GUI representation of the graph, are there's no memory issues to worry about. With shared_ptr parent list, either you trust the lists to be correct, which is risky, or you have to test the lists, then e.g. throw exceptions. Which means slower algorithms.... it's a tradeoff, that's why I'm asking this question — cfa45ca55111016ee9269f0a52e771
With std::find_if() taking a lambda, when you search through a parent list, each weak_ptr has to be lock()ed and then the resulting shared_ptr compared to the other function parameter. As long as it's not too slow, it's fine, but it's easier and faster to compare shared_ptrs directly using operator== automatically called by std::find() (for other opeations too, with lambda or withour - you have to lock() every time) — cfa45ca55111016ee9269f0a52e771

Arne Mertz Arne Mertz · Accepted Answer · 2013-01-28T13:41:16

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

weak_ptr VS shared_ptr in graph node parent list

2 Answers