Simple tree but pointers changing themselves

[Duncan]

Hello all. Strange thing happening and I am at my wit's end. Sorry for the lump of code but it's meant to generate a simple tree. As you can see from the output, somewhere the parent pointers get messed up. And yet, I can't seem to find where, and if I output them in the constructor (only time they get modified) they all look OK. When I run output_path_to_root() on any grandchildren of the root I get a segmentation fault. Any ideas on how the parents are getting messed up? I was wondering if my vectors changing size is causing pointers to shift around but I'm not sure that makes sense or how I would fix it. Thanks.

//tree.cpp

#include <iostream>
#include <vector>
using namespace std;

struct A
{
  int n;
  vector<A> get_children()
  {
    //Children are n/2 and n/3 if they are integers
    vector<A> c;
    if (n%2 == 0)
    {
      A div2 = {n/2};
      c.push_back(div2);
    }
    if (n%3 == 0)
    {
      A div3 = {n/3};
      c.push_back(div3);
    }

    return c;
  }
};

class ANode
{
  private:
    A node; //the "actual value" of the node
    ANode * parent;
    vector<ANode> children;
  public:
    
    ANode(const A & a, ANode * p)
    {
      node = a;
      parent = p;

      //Wrap the children into nodes
      vector<A> rawchildren = node.get_children();
      for (int i=0; i < rawchildren.size(); i++)
      {
        ANode c(rawchildren[i], this);
        children.push_back(c);
      }
    }

    void output_tree_dfs() const
    {
      //should output "me (my parent's value)" and then do the same for children
      cout << node.n << " ( ";
      if (parent != NULL)
	cout << "parent->node.n: " << parent->node.n;
      cout << ")" << endl;
      
      //descend in depth recursively
      for (int i=0; i < children.size(); i++)
        children[i].output_tree_dfs();
    }
    
    void output_path_to_root() const
    {
      cout << node.n << ' ';
      if (parent != NULL)  {parent->output_path_to_root();}
    }
};

int main()
{
  A start = {2*3*2}; //12
  ANode root(start, NULL);
  root.output_tree_dfs();

  return 0;
}

12 ( )
6 ( parent->node.n: 12)
3 ( parent->node.n: -1487162336)
1 ( parent->node.n: -1429198496)
2 ( parent->node.n: -1487162336)
1 ( parent->node.n: -1429198496)
4 ( parent->node.n: 12)
2 ( parent->node.n: -1487162336)
1 ( parent->node.n: -1429198496)

[Duncan]

Figured it out. The short answer is the children vector should be of pointers to dynamically allocated instances instead of a vector of objects because otherwise they go out of scope.

The long answer is that actually the objects don't go out of scope because they are all copied around into new vectors. That's actually the problem, though. When I push an object into a vector, it gets copied to a new address in memory. That means all its children don't know where their parent is anymore because its address changed and the old one (that they were pointed towards) went out of scope. Hence the parent pointers being nonsense.

I'm glad I figured it out because that is a really tough bug to work out... Hopefully this will help someone else.