Returning shared pointer reference breaks outside of class methods

Question

I have a tree in C++ and a method in the Tree that returns a shared_ptr reference to a new leaf whenever that leaf is added to the tree. When I use this inside other methods of the Tree class it works fine, but when I try to call it from main, it crashes, despite the code seemingly doing the same thing.

Here's the Node and Tree classes:

#include <iostream>
#include <vector>
#include <memory>

class Node
{
public:
    int value;
    std::vector<std::shared_ptr<Node> > children; 
    Node(int value): value{value} {}
};

class Tree
{
public:
    std::shared_ptr<Node> root;
    Tree(): root {nullptr} {}

    std::shared_ptr<Node> CreateLeaf(int value)
    {
        return std::make_shared<Node>(value);
    }

    std::shared_ptr<Node>& AddLeaf(int value, std::shared_ptr<Node>& ptr)
    {
        if(ptr == nullptr)
        {
            ptr = std::move(CreateLeaf(value));
            return ptr;
        }
        else
        {
            std::shared_ptr<Node> newLeaf = CreateLeaf(value);
            ptr->children.push_back(std::move(newLeaf));
            return ptr->children.back();
        }
    }

    void otherMethod()
    {
        AddLeaf(1, root);
        std::shared_ptr<Node>& temporary = AddLeaf(2, root);
        std::cout << "temporary->value: " << temporary->value << std::endl;
    }

};

If the main function is:

int main()
{
    Tree t;
    t.otherMethod();
}

Then the program runs correctly.

However, if the main function is:

int main()
{
    Tree t;
    t.AddLeaf(1, t.root);
    std::shared_ptr<Node>& b = t.AddLeaf(2, t.root);
    std::cout << "b->value = " << b->value << std::endl; 

}

the program crashes, despite it doing pretty much the same thing. It seems like AddLeaf is just storing the nullptr in b, despite it being a reference to a persistent object, t.root->children[0]. Why is it doing that?

Answer 1

Having references to elements in a vector, or any self-resizing container, is dangerous. I've dealt with this when I created my first game in C++.

Essentially what happens is:

Your vector resizes when adding a new shared_ptr, which may cause an operation to allocate more memory. During that procedure the currently existing vector is destructed and allocated on possibly a different location in memory.
Meaning that all currently existing pointers or references to elements in the vector become invalidated and may crash your program at some point.

Passing out references to shared_ptr's in a vector basically promotes undefined behavior. A smarter move would be to just return a new shared_ptr and have the reference counter just increment.
That way, when the vector resizes, no reference in your program gets invalidated.

Removing the reference should help:

std::shared_ptr<Node> AddLeaf(int value, std::shared_ptr<Node>& ptr)
{
    if(ptr == nullptr)
    {
        ptr = std::move(CreateLeaf(value));
        return ptr;
    }
    else
    {
        std::shared_ptr<Node> newLeaf = CreateLeaf(value);
        ptr->children.push_back(std::move(newLeaf));
        return ptr->children.back();
    }
}

Anyway, as I see you're creating a tree, perhaps you would like to take a look at code I've written in an (abandoned) project: https://github.com/wvanbreukelen/LexMe/blob/feature-tree-node-vector-specialization/LexMe/TreeNode.h
It's a quite complete implementation for a generic tree with friendliness towards move semantics and iterators.