C++ vector of pointers problem

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(&no开发者_如何学Godes[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?

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?

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.

The problem is that, every time you add to a vector, it might need to expand its internal memory. If it does so, it allocates a new piece of storage, copies everything over, and deletes the old one, invalidating iterators and pointers to all of its objects.

As solution to your problem you could either

• avoid reallocation by reserving enough space upfront (nodes.reserve(42))
• turn nodes into a std::list (which doesn't invalidate iterators or pointers to elements not directly affected by changes)
• store indexes instead of pointers.

Besides your problem, but still worth mentioning:

• The legal use of identifiers starting with underlines is rather limited. Yours is legal, but if you don't know the exact rules, you might want to avoid using them.
• Your comparison operator doesn't tell that it won't change its left argument. Also, operators treating their operands equally (i.e. not modifying them, as opposed to, say, +=), are usually best implemented as free functions, rather than as member functions.

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).

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