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

A few things.

First, as far as I can tell NNodes is just tracking the size. But you have std::vector::size() for that. You then use it to get the last inserted element, but you can just use std::vector::back() for that: return &N.back();.

Also your parameter is being passed by value, when it should probably be passed by const-reference: const string& h. This avoids unnecessary copies, and in general* you should pass things by const-reference instead of by-value.

And this is bad:

node n;
N.push_back(n);
N[NNodes].setname(h);

node should probably have a constructor that takes a const string& and sets the name during initialization. That way you can never have a node without a name, as in:

node n(h);
N.push_back(n);

Or more terse:

N.push_back(node(h));

Much better.

Second, yes, vector can invalidate pointers to elements; namely, whenever the capacity of the vector needs to be increased. If you can, reserve() the capacity up front to avoid re-allocations. In your case you cannot, so you can go two different routes.

The first route is a level of indirection. Instead of pointing directly at things, get their index into the array. Note that while their address may change, their location within the vector will not. You would have Simulator::FindNode return a size_t, and return N.size() - 1. Add a member like node& GetNode(size_t index), which just does return N[index]; (will error checking if you wish). Now whenever you need a member, hand the index to that member to GetNode and you'll get a reference to that node back.

The other route is to change your container. You can use a deque, for example. This does not have contiguous storage, but it's much like vector. push_back and pop_back are still O(1), and it still has good cache-coherence. (And by the way, deque trades contiguous storage for the ability to push_front and pop_front in O(1) time as well)

The important thing is that deque will not invalidate pointers during a push or pop operation from either end. It works by a sort of vector-list hybrid, where you get chunks of storage for elements linked together. Change your underlying storage to deque (and don't take or put anything in the middle), and you can point to things just fine.

However, from what I can tell you have a terribly inefficient map. You're mapping names to nodes. You should probably just use std::map, which has the exact interface you're trying to recreate. You can even point to any element in a map, which never invalidates things.

_{*The rule is, pass by const-reference unless the type is primitive (built-in like int, double, etc.), if the types size is less than sizeof(void*), or if you are going to need a copy of it anyway.}

That is, don't do this:

void foo(const std::string& s)
{
    std::string ss(s); // make a copy, use copy
}

But do this:

void foo(std::string s) // make a copy, use copy
{
}