copy object behind shared pointer containing a list of shared pointers

Question

I have a shared_ptr<Tree> tree and a shared_ptr<TreeNode> node that contains a list of childrens as shared pointers.

class TreeNode
{
protected:
    std::weak_ptr<TreeNode> parent;

    /**
    A list containing the children of this node
    */
    std::shared_ptr<std::vector<std::shared_ptr<TreeEdge>>> children;

   ...

A Tree needs only to be given a TreeNode as its root.

Tree::Tree(const shared_ptr<TreeNode> root)
    : root(root)
{}

So to create that sub Tree I try to get a TreeNode and call the Tree constructor with it.

shared_ptr<TreeNode> treeNode = oldTree->getASpecialNode();
shared_ptr<Tree> newTree = make_shared<Tree>(treeNode);

Now the root of newTree is treeNode. But the problem is, every TreeNode is pointing to its parent. So does treeNode.

weak_ptr<TreeNode> TreeNode::getParent() const
{
    return parent;
}

When calculating the root by going through the parents of any TreeNode in newTree, we will reach a different root node than newTreeNode, because newTreeNode itself has a parent.

Deleting that parent is no solution, because the object is shared and we will need it in the original Tree. So the only solution I see is to copy the TreeNode and copy all it's members.

How can I do that?

Based on other answers on SO I tried this:

std::shared_ptr<TreeNode> TreeNode::clone() const
{
    auto clone = new TreeNode (*this );
    clone->setParent(weak_ptr<TreeNode>());
    return shared_ptr<TreeNode>(clone);
}

But still calculating the parents will lead to the original root node. So I wasn't able to create a sub tree.

I have the feeling that it's wrong to use shared_ptr for Tree and TreeNode, but it's not my code. I just need to add a feature.

Answer 1

The entire subtree has to be cloned, not just the sub-root. Since none of the pointers are copied, it is not useful to copy initialize the clone. Also, you should avoid bare pointers to allocated memory in order to guarantee strong exception safety.

Untested example:

std::shared_ptr<TreeNode> TreeNode::clone() const
{
    auto clone = std::make_shared<TreeNode>();
    clone->children->reserve(children->size());
    for(const auto& c : *children) {
        auto c_clone = c->clone();
        c_clone->setParent(clone);
        clone->children->push_back(c_clone);
    }
    return clone;
}

---

I have the feeling that it's wrong to use shared_ptr for Tree and TreeNode

I share your feeling. Certainly when the nodes have a parent pointer, it is unclear how the nodes could be sensibly shared across multiple trees.

std::shared_ptr<std::vector<std::shared_ptr<TreeEdge>>> also seems excessive indirection.