std::vector指针指向重复地址问题求助——SPFA算法内存异常

在实现SPFA算法时，使用std::vector存储图的带权边，通过指针数组ptr_arr记录每个edge元素的地址，用于后续修改结构体的p字段。调试时发现ptr_arr[2]与ptr_arr[5]指向同一地址，不符合预期。

相关代码：

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

猜测问题与std::vector的内存分配机制有关，但无法明确核心原因，寻求解答。

核心原因 #

问题确实源于std::vector的自动扩容机制：

• std::vector以连续内存存储元素，当当前容量不足以容纳新元素时，push_back会触发扩容：申请一块更大的连续内存，将原有所有元素拷贝/移动到新内存，随后释放旧内存。
• 此时，之前通过&edge[a].back()保存的指针会变成野指针——它们指向的旧内存已被释放。后续其他vector（如示例中的edge[4]）执行push_back时，可能会重新分配到这块被释放的旧内存，导致不同指针（如ptr_arr[2]和ptr_arr[5]）指向同一地址。

结合输入示例的具体流程：

• 第三条边是1->5，edge[1]添加元素后，ptr_arr[2]保存该元素的旧内存地址。
• 第五条边是1->3，此时edge[1]容量耗尽触发扩容，原1->5元素被移至新内存，旧内存被释放。
• 第六条边是4->1，edge[4]执行push_back时，恰好分配到edge[1]刚释放的旧内存，导致ptr_arr[5]的地址与ptr_arr[2]指向的旧地址重合。

解决方法 #

方法1：提前预留足够容量 #

在输入边之前，先统计每个节点的出度，调用reserve()为对应vector预留内存，避免后续扩容：

// 先统计每个节点的出度
int out_degree[maxN] = {0};
for(int i=0; i<m; i++){
    scanf("%d%d%d",&a,&b,&v_temp);
    out_degree[a]++;
}
// 为每个vector预留足够容量
for(int i=1; i<=n; i++){
    edge[i].reserve(out_degree[i]);
}
// 重新输入边并保存指针
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();
}

方法2：改用索引替代指针 #

不保存元素指针，而是记录元素所在edge的下标和该vector内的索引，后续通过索引访问元素，彻底避开指针失效问题：

// 替换ptr_arr为存储pair：第一个是edge的下标，第二个是vector内的索引
pair<int, int> idx_arr[maxM];

for(int i=0; i<m;i++){
    scanf("%d%d%d",&a,&b,&v_temp);  
    edge[a].push_back(e(b,0,v_temp));
    idx_arr[i] = {a, (int)edge[a].size()-1};
}
for(int i=0;i<m;i++){
    scanf("%d",&p_temp);
    int a = idx_arr[i].first;
    int idx = idx_arr[i].second;
    edge[a][idx].p = p_temp;
    cout << edge[a][idx].v;
}

方法3：使用不会扩容的容器 #

如果对访问效率要求不高，可改用std::list存储边——list的元素存储在非连续节点中，插入时不会触发扩容，元素地址始终稳定。但list的随机访问效率远低于vector，需根据场景权衡。

内容的提问来源于stack exchange，提问作者Wells