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++;
}

`0xfffffffd2b0` typically indicates a stack location – M.M Nov 02 '15 at 22:31 — M.M, Nov 02 '15 at 22:31

score 3 · Answer 1 · edited May 23 '17 at 12:14

3

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.

edited May 23 '17 at 12:14

Community

1
1

answered Sep 22 '15 at 18:28

NathanOliver

171,901
28
288
402

This sounds pretty spot on to what is occurring. That's what I figured with gdb, but i didn't know how to fix it. So, I basically need to make a New Node in every iteration of the loop? Will they persist in data, then? I really appreciate the help, can you go into a bit more detail? I've been looking at this bug for hours. – user2055216 Sep 22 '15 at 18:31
Yes a `Node` created with `new` will be placed on the heap and will stay in memory until the program ends or it is deleted. – NathanOliver Sep 22 '15 at 18:33
The reference to the pointer is still always in the same place as memory. I n all locations where I made a Node, I changed it to new. – user2055216 Sep 22 '15 at 19:29
@user2055216 Can you post your updated code to something like [coliru](http://coliru.stacked-crooked.com/) so I can see it? – NathanOliver Sep 22 '15 at 20:14
I eventually figured it out, it was pointer syntax stuff that was throwing me off. I'm just happy that I was able to make it compile and work. Much thanks to you by the way. However now, my iterative deepening DFS isn't returning an optimal solution! IDDFS is supposed to be optimal. So it goes. – user2055216 Sep 22 '15 at 20:43

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

1 Answers1