weak_ptr VS shared_ptr in graph node parent list
c++, c++11, directed-acyclic-graphs, shared-ptr
Solution
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_ptr`s 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);
Problem
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?