Memory issue about pointer that points to std::vector

Question

I was doing an algorithm problem about SPFA, and I used std::vector to store the weighted edge of the graph, where I have a pointer array that points to it:

struct e{
    int to,p,v;
    e(int _to_,int _p_, int _v_) {to = _to_, p = _p_, v = _v_;}
};
vector <e> edge[maxN];
e* ptr_arr[maxM]; //ptr array points to the struct object

for(int i=0; i<m;i++){scanf("%d%d%d",&a,&b,&v_temp);  
    edge[a].push_back(e(b,0,v_temp));
    ptr_arr[i]=&edge[a].back();}
    for(int i=0;i<m;i++){scanf("%d",&p_temp);
    ptr_arr[i]->p=p_temp;
    cout << ptr_arr[i]->v;}

The problem input is like this,

5 6
2 3 2 
5 2 5 
1 5 7 
3 4 3 
1 3 5 
4 1 8 
2 3 1 4 1 3

I need to modify p for every edge that is stored in edge[maxN], so I keep track of the address of each element in ptr_arr. When I was debugging, I discover that for this case, ptr_arr[2] and ptr_arr[5] points to the same address, which should not be. I am wondering what causes this problem?

I am guessing there's something to do with the memory allocating for vector array but I am not so sure, and I cannot grasp the core cause for this problem.

Answer 1

The core problem here is that the vector invalidates its iterators (and thus pointers to elements) after modifying operations such as push_back. This is caused by the implementation of the container: when it is not enough capacity for new elements, it creates a new storage and moves everything there and then adds a new element to the end. You can try to fix this by reserving some initial capacity to prevent this behavior if you know the maximum amount of elements.

for(int i=0; i<m;i++){
 scanf("%d%d%d",&a,&b,&v_temp);
 edge[a].reserve(some_max_number_of_elements)
 

But of course, when you reach this maximum amount, this fix would not work.

That is why storing pointers to vector elements usually not a good idea.