C++ vector of pointers problem

Question

I'm currently trying to implement the A* pathfinding algorithm using C++.

I'm having some problems with pointers... I usually find a way to avoid using them but now I guess I have to use them.

So let's say I have a "node" class(not related to A*) implemented like this:

class Node
{
public:
    int x;
    Node *parent;

    Node(int _x, Node *_parent)
        : x(_x), parent(_parent)
    { }

    bool operator==(const Node &rhs)
    {
        return x == rhs.x && parent == rhs.parent;
    }
};

It has a value (in this case, int x) and a parent (a pointer to another node) used to navigate through nodes with the parent pointers.

Now, I want to have a list of nodes which contains all the nodes that have been or are being considered. It would look like this:

std::vector<Node> nodes;

I want a list that contains pointers pointing to nodes inside the nodes list. Declared like this:

std::vector<Node*> list;

However, I'm definitely not understanding pointers properly because my code won't work. Here's the code I'm talking about:

std::vector<Node> nodes;//nodes that have been considered
std::vector<Node*> list;//pointers to nodes insided the nodes list.

Node node1(1, NULL);//create a node with a x value of 1 and no parent
Node node2(2, &node1);//create a node with a x value of 2 and node1 being its parent

nodes.push_back(node1);
list.push_back(&nodes[0]);

//so far it works

//as soon as I add node2 to nodes, the pointer in "list" points to an object with
//strange data, with a x value of -17891602 and a parent 0xfeeefeee
nodes.push_back(node2);
list.push_back(&nodes[1]);

There is clearly undefined behaviour going on, but I can't manage to see where. Could somebody please show me where my lack of understanding of pointers breaks this code and why?

Answer 1

One problem is that push_back can force a reallocation of the vector, i.e. it creates a larger block of memory, copies all existing elements to that larger block, and then deletes the old block. That invalidates any pointers you have to elements in the vector.

Answer 2

So, the first issue that you have here is that you are using the address of individual Nodes of one of your vectors. But, over time, as you add more Node objects to your vector, those pointers may become invalid, because the vector may move the Nodes.

(The vector starts out at a certain pre-allocated size, and when you fill it up, it allocates a new, larger storage area and moves all of the elements to the new location. I'm betting that in your case, as soon as you add the second Node to nodes, it is doing this move.)

Is there a reason why you can't store the indices instead of the raw pointers?

Answer 3

Your code looks fine to me, but remember that when nodes goes out of scope, list becomes invalid.

Answer 4

just adding to the existing answers; instead of the raw pointers, consider using some form of smart pointer, for example, if boost is available, consider shared_ptr.

std::vector<boost::shared_ptr<Node> > nodes;

and

std::list<boost::shared_ptr<Node> > list;

Hence, you only need to create a single instance of Node, and it is "managed" for you. Inside the Node class, you have the option of a shared_ptr for parent (if you want to ensure that the parent Node does not get cleaned up till all child nodes are removed, or you can make that a weak_ptr.

Using shared pointers may also help alleviate problems where you want to store "handles" in multiple containers (i.e. you don't necessarily need to worry about ownership - as long as all references are removed, then the object will get cleaned up).