C++: vector of pointer loses the reference after push_back()

Question

In my code a have a global vector of Node object and a local vector of Node pointers:

#include<cstdio>
#include<cstdlib>
#include<vector>

using namespace std;

class Node {
    int n;

public:
    Node(int i) : n(i);
    int getN() { return n; }
};

vector<Node> v;

int main() {
    vector<Node*> p;
    v.push_back(Node(1));
    p.push_back(&v[0]);
    printf("first node id : %d\n", (*p[0]).getN());

    return 0;
}

I inserted a node object to global vector & inserted the pointer of that object in the local vector. Output of my above code is:

first node id : 1

However, if I change my main function to this:

int main()
{
    vector<Node*> p;
    v.push_back(Node(1));
    p.push_back(&v[0]);
    v.push_back(Node(2));
    p.push_back(&v[1]);
    printf("first node id : %d\n", (*p[0]).getN());

    return 0;
}

The code prints a garbage value:

first node id : 32390176

I can't figure out the problem. Does the vector data structure changes the references of each object after an insertion ? How can I fix this ?

Answer 1

"Does a vector change the references after an insertion?"

Possibly, yes. An std::vector may reallocate its (heap) storage when you add additional elements to it - thus invalidating all pointers:

Iterator [read: Pointer] Invalidation

(for operations) push_back, emplace_back ... If the vector changed capacity, all of them [i.e. all iterators are invalidated]. If not, only end().

"How can I fix this?"

The above invalidation rule does not apply if a vector's capacity does not change due to an insertion - since vectors do not reallocate storage unnecessarily. So if you pre-set your vector's capacity to 2 in your example (say, with v.reserve(2)), the pointer will remain valid. If you don't know the size in advance, but you can delay the construction of the second vector (with the pointers), you don't have to reserve, you'll just have the size after inserting the last element.

The approaches above are highly unrecommended, however. If you were to make your vector constant - at least in the scope of a function in which you would construct and use the second vector - you would have a strong guarantee of non-reallocation. Alternatively, if you could determine the size in advance you might use an std::array, and it would be more fitting to use pointers into that container's storage:

Iterator Invalidation

As a rule, iterators to an array are never invalidated throughout the lifetime of the array.

You might also consider storing indices into your vector (although there, as well, the vector might shrink, invalidating the indices, or you might insert elements in the middle etc).

Anyway, I suspect that you might not actually want to do any of this, i.e. it seems to be a not-so-good solution to a problem which could be handled with a different approach altogether.

_{PS - If the vector has a custom allocator then everything I've written might be irrelevant.}