Pointer problem using Vector containing structs

Question

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 is adding to the end of the vector list is the location of the previous information changing?

I must question that it's "all working awesomely" when you misspelt even the standard library function names - it should be push_back(). Your code can't even compile... — Kerrek SB
– Kerrek SB, Commented Sep 18, 2011 at 20:53

sehe · Accepted Answer · 2011-09-18 20:53:03Z

2

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

answered Sep 18, 2011 at 20:53

sehe

400k49 gold badges475 silver badges673 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Andriy Tylychko Over a year ago

I wouldn't suggest to use reverse to resolve this problem. Most probably it's a temporary solution (if any) that will work up to the next modification.

sehe Over a year ago

@Andy T: I don't suggest reverse [sic]. I don't even suggest reserve! I just point out that the standard provides it: the standard (see, e.g. the linked page) is also very precise on when a std::vector is allowed to reallocate. It could be more than enough. Anyways, I was very explicit in what I'm suggesting as solutions instead :)

Andriy Tylychko Over a year ago

it was typo of course, I couldn't edit my comment because SO doesn't allow it for 5 mins or after another comment, and you was fast :) about reserve I explained in my answer

Andriy Tylychko · Accepted Answer · 2011-09-18 21:11:37Z

1

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

edited Sep 18, 2011 at 21:11

answered Sep 18, 2011 at 21:04

Andriy Tylychko

16.4k10 gold badges70 silver badges113 bronze badges

1 Comment

sehe Over a year ago

For the record: I disagree with the term reserve recommendations. I felt the need to give a relatively complete answer - including the standard library features in this area. I do agree with you that with this kind of linked datastructures, using pointers all the way down is vastly superior

K-ballo · Accepted Answer · 2011-09-18 20:54:16Z

0

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.

answered Sep 18, 2011 at 20:54

K-ballo

81.6k20 gold badges165 silver badges172 bronze badges

2 Comments

sehe Over a year ago

@K: it appears you agree with me :)

K-ballo Over a year ago

@sehe: I even gave you that +1

Collectives™ on Stack Overflow

Pointer problem using Vector containing structs

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related