Pointer problem using Vector containing structs

I am currently really stuck on how to solve the following problem:

struct node {
    int a;
    node* b;
}

I will have two root nodes without parents and then to more nodes pointing to their parents

vector<node> IholdAllTheNodes;

node noparent1; <--- these get returned from a method
node noparent2;

IholdAllTheNodes.pushback(noparent1);
IholdAllTheNodes.pushback(noparent2);

node withparent1; <---- i am happily points to noparent1
node withparent2; <-----i am happily points to noparent2

No problems up to here all working awesomely

IholdAllTheNodes.pushback(withparent1) <<<< oops this causes all the pointers to move.

now the withparent nodes are no longer pointing to their parents because I have moved them.

My question is simply how do I add more nodes to my vector of nodes without moving the pointers of the original nodes. (I cant get a fixed size for the vector)

if anyone has the time to explain, why even though pushback i开发者_运维问答s adding to the end of the vector list is the location of the previous information changing?

You could call reserve

IholdAllTheNodes.reserve(MAX_SIZE);

up front to avoid reallocation. It requires you to know MAX_SIZE up front.

Alternatively,

• suggested: make it a Pointer Container
• make it a std::vector<shared_ptr<node> > (similar but less efficient)
• make it a std::vector<node*> (similar but tedious and error-prone)
• suggested: avoid using pointers if you can. Address the nodes by size_t (integer) index into IholdAllTheNodes instead

Your problem is that you store nodes by value in vector. They are copied, potentially many times. Each time a node will be placed in different memory address. As result you'll receive different pointers to it, and old pointers will point to invalid location.

As other answers suggested, use any kind of pointers to store your nodes in vector. I would recommend boost::ptr_vector<node> or std::vector<boost::shared_ptr<node> >

EDIT:

Just to disagree with reserve recommendations:

It's dangerous. You need to put large bold warnings in all possible places so people who'll modify this code in the future cannot omit it. Because when you'll add more than MAX_SIZE elements to your vector, your space ship will end burning on Sun. In this case I would recommend to use boost::array since it's fixed size (so making your assumption more obivious) and catches buffer overflow at least in Debug builds

Call IholdAllTheNodes.reserve() with a specific size, and it will guarantee that further insertions won't invalidate the pointers until such reserved ammount is reached.