c++ vector and pointers issue

Question

I have a problem with pointers within a struct losing their data when added to a vector.

Within a pathfinder function, I'm creating a vector<Node> and for each of those nodes I'm setting the Node.parent to an address of Node.

After the nodes have been set with their parent, I pop these nodes into another vector<Node>.

The problem I'm having is the nodes are losing their pointer to the parent after moving them into the new vector.

Essentially the code looks like this.

struct Node {
    int x,y;
    Node * parent;
}

vector<Node> queue;
queue.push_back(start)

while (queue.size() > 0) {
    Node item = queue.back(); //grab a item from queue last thing put in

    queue.pop_back(); //remove that item from the queue
    traveled.push_back(item); //add item to list of traveled items.
    std::vector<Node> neighbors = getNeighbors(item);
    setParent(neighbors, &item);

    //check each neighbor
    for (std::vector<Node>::iterator iter = neighbors.begin(); iter != neighbors.end(); iter++) {
        //check if a walkable Node and its not already traveled
        if (validNode(*iter) && !contains(traveled, *iter)) {
            queue.push_back(*iter);
        }
    }
}

Once I add the valid neighbor nodes back into the queue vector, they lose their pointer to the correct parent. They do retain the correct x,y values though.

Any help would be great!

This: `setParent(neighbors, &item);` looks suspiciously like you are storing the address of a local variable `item` which is not good. — uesp, Dec 16 '14 at 22:38
What about using [`std::queue`](http://en.cppreference.com/w/cpp/container/queue) instead of rolling your own? Also note for `Node`'s implementation you have to have a [Rule-of Three](http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) compliant implementation to use it with `std::vector` or `std::queue`. — πάντα ῥεῖ, Dec 16 '14 at 22:39
Your queue is not really a queue since you are calling `push_back` and `pop_back` which means you're popping from the same side that you are pushing, thus you really have a stack. — b4hand, Dec 17 '14 at 01:32

b4hand · Answer 1 · 2014-12-17T02:49:15.607

Since item is a local variable, it doesn't make sense to set other Nodes with item as a parent. You should probably change your queue to store pointers to Nodes instead of Nodes themselves:

std::vector<Node *> stack;
stack.push_back(&start);
while (!stack.empty()) {
    Node *item = stack.back();
    stack.pop_back();
    traveled.push_back(item);
    std::vector<Node *> neighbors = getNeighbors(item);
    // ...
}

The issue is that the pointer to which you are setting the parent is invalid later. It's not that the pointer is lost, it is that they are pointing to an item on the stack that will be overwritten later. For the same reasons, you probably want getNeighbors to return a vector of pointers as well, so that it returns the original Nodes and not copies of the Nodes.

Also, if you really do intend to get the "most recent" item pushed onto the "queue", then you really have a stack, and I would rename your variable as such.

thanks b4hand - i rebuilt everything as vectors of pointers and this worked. I don't think i quite have my hand wrapped around pointers, i guess i need to do some more experimenting — m l, Dec 17 '14 at 02:32

c++ vector and pointers issue

1 Answers1