C++ Pointers and Data Locations: Data Always Being Placed at Same Memory Location

Question

I'm trying to implement an iterative deepening depth first search algorithm in C++. The search successfully finds the solution to the problem, but I am having trouble linking the child node back to the root node.

struct Node
{
    std::vector<int> config;
    int depth;
    int action; //0 up 1 down 2 left 3 right
    Node * parent;
    bool operator<(const Node& rhs) const
    {
        return depth < rhs.depth;
    }
};

As you can see in my structure, I have a pointer to the parent node. In my DFS code however, I am running into a problem updating the parent pointer for the nodes in each iteration of the loop. The parent pointer for all nodes always points to the same data location, 0xfffffffd2b0. In other words, the new node called Next is always created here.

I believe the Node I have in my code called Next always gets placed at this same data locataion, thus the reference location to each Next is always the same. How can I prevent it from always appearing at the same location? This means that the Child nodes are not being linked to their parent, but rather to themselves. I have marked the source of the bug with asterisks.

 //IDDFS Logic:
int Current_Max_Depth = 0;
while(Current_Max_Depth < 20) 
{
    struct Node initial = {orig_config, 0, 0, NULL}; //config, depth, action, parent.
    visited.clear();
    priority_queue<Node> frontier;
    frontier.push(initial);
    while(frontier.size()>0)
    {
        struct Node Next = frontier.top();
        visited.push_back(Next.config);
        frontier.pop();
        if(Next.depth < Current_Max_Depth)
        {
            int pos_of_hole = Find_Position_of_Hole(Next.config);
            if(pos_of_hole==0) 
            {
                 std::vector<int> Down_Child = Move_Down(Next.config);
                 struct Node Down_Node = {Down_Child,Next.depth+1,1,&Next};  //****
                 if(!(std::find(visited.begin(), visited.end(), Down_Child)!=visited.end()))
                 {
                      if(Goal_Test(Down_Child))
                      {
                           goal_node = Down_Node;
                           goal_reached = true;
                           break;
                      }
                 frontier.push(Down_Node);
                 }

                std::vector<int> Right_Child = Move_Right(Next.config);
                struct Node Right_Node = {Right_Child,Next.depth+1,3,&Next}; //*******Passing next by reference here is not working since Next is always at the same data location.  The nodes one layer up from the leaf nodes end up all pointing to themselves.
                if(!(std::find(visited.begin(), visited.end(), Right_Child)!=visited.end()))
                {
                    if(Goal_Test(Right_Child))
                    {
                        goal_node = Right_Node;
                        goal_reached = true;
                        break;
                    }
                 frontier.push(Right_Node);
                 }      
         }
    if(pos_of_hole==1)
    ... does very similar for pos 1 through 8, not related to bug ...
        } //End of if(Next.Depth < Max_Depth)
} //End of while(frontier.size()>0)
if(goal_reached)
{
    break;
} 
Current_Max_Depth++;
}

Answer 1

struct Node initial = {orig_config, 0, 0, NULL};

Creates a Node on the stack. When you create the next child

struct Node Down_Node = {Down_Child,Next.depth+1,1,&Next};

You are taking the address of that local stack object. When the loop ends Next is destroyed and then it is constructed again at the beginning of the next iteration of the while loop. If the nodes need to persist then you need to allocate them with new and then delete then when you are done.

On a side note the struct keyword is not required on variable declarations in C++. See Why does C need “struct” keyword and not C++? for more information.