Does insertion of elements in a vector damages a pointer to the vector ?

Question

In a program to simulate logic gates I switched from using arrays

node N[1000];

to vectors

vector<node> N;

And my program did work perfectly before using vectors but now it prints wrong results, so I tried debugging and I found out that the bug happens here:

node* Simulator::FindNode(string h)
{
    int i;
    for(i = 0; i < NNodes; i++)
    {
        if (N[i].getname() == h)
        {
            return &N[i];
        }
    }

    node n ;
    N.push_back(n);
    N[NNodes].setname(h);
    NNodes++;
    return &N[NNodes-1]; //why?because of NNodes++  
}

// ...

node* inp1;
node* inp2;
node* out;
string NodeName;

inp_file >> NodeName;
inp1 = FindNode(NodeName);
s1 = inp1;

inp_file >> NodeName;
inp2 = FindNode(NodeName); //inp1 is destroyed here 

inp_file >> NodeName;
out = FindNode(NodeName); //inp2 and inp1 are destroyed here 

When calling FindNode for the 1st time, the 1st pointer inp1 points to the right place which is &N[0].

When calling FindNode for the second time the 1st pointer inp1 points to rubbish and the second pointer inp2 points to the right place &N[1].

When calling FindNode for the 3rd time the both the 1st and 2nd pointers (inp1, inp2) point to rubbish! And 3rd pointer out points to the right place.

Why would that happen?
How does vector work when I insert items to them and which kind of pointers should I use to point to vectors items?

Answer 1

Yes, it can re-allocate the entire buffer, making all pointers into the old location invalid.

You can limit this by preallocating, but that's really just a performance boost. The better way is to use indexes instead of raw pointers.

Answer 2

When a vector grows, it is reallocated, which effectively invalidates all pointers to elements of the vector.

If you know beforehand how many elements you will have in the vector, you could use the reserve() method to preallocate space.

Answer 3

Returning a pointer to an internal STL member is probably not the best idea. When you give an object to an STL container you are basically giving up control of it. You are telling the STL it can move it around as it sees fit to maintain the promises that the container gives you. Returning the index where the node is located is a better idea like Steven Sudit mentioned.

Once you get the index you could create a function that returns a copy of the contents of the node you are interested in. This way you also maintain data encapsulation with the STL container, not allowing anyone else to modify its contents.

Answer 4

Yes, inserts will invalidate old pointers to vector elements on reallocation. If you want to use stable pointers really hard, you can switch from vector to deque. It offers a very similar interface to vector and can grow without reallocating and moves previous contents by allocating further chunks.

The price you pay for using a deque instead of a vector is one more level of indirection on random access. Depending on your usage, that may be totally irrelevant. You should iterate over deque the whole deque if necessary by using iterators. That will be as fast a iterating over a vector.

The gain is: zero reallocations!

Answer 5

Imagine you needed to write the array-based code so that it could possibly re-size the array if necessary.

Imagine how you would do it.

Imagine what would happen to stale pointers.

Rewrite your code to use indices rather than pointers, or to guarantee that re-allocation doesn't happen, as appropriate.