指向 std::vector 的指针的内存问题

Question

我正在做一个关于SPFA的算法问题，我使用

std::vector

来存储图的加权边，其中我有一个指向它的指针数组：

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;}

问题输入是这样的，

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

我需要为

p

中存储的每条边修改

edge[maxN]

，因此我跟踪

ptr_arr

中每个元素的地址。当我调试时，我发现对于这种情况，

ptr_arr[2]

和

ptr_arr[5]

指向同一个地址，这是不应该的。我想知道是什么原因导致这个问题？

我猜测这与向量数组的内存分配有关，但我不太确定，而且我无法掌握这个问题的核心原因。

Answer 1

这里的核心问题是向量在修改诸如push_back之类的操作后使其迭代器（以及指向元素的指针）无效。这是由容器的实现引起的：当容器没有足够的容量容纳新元素时，它会创建一个新的存储并将所有内容移动到那里，然后在末尾添加一个新元素。 如果您知道元素的最大数量，您可以尝试通过保留一些初始容量来解决此问题，以防止出现此行为。

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

但是，当然，当你达到这个最大数量时，这个修复就不起作用了。

这就是为什么存储指向向量元素的指针通常不是一个好主意。