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.
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.