为何直接赋值init返回值给nodes成员出错，中间变量可修复？

问题现象 #

实现可持久化线段树时，直接执行nodes[id].lc = init(l,mid)时，nodes[id].lc有时会被赋值为-1，但init()函数从未返回过-1。引入中间变量存储init()返回值再赋值（如int id_l = init(l,mid); nodes[id].lc = id_l;）后，bug消失。

错误代码 #

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int lc,rc,val;
    Node() : lc(-1), rc(-1),val(0) {

    }
};
vector<Node> nodes;
int n,q;
vector<int> a;

///creates a new node for this interval and returns the id of it
int init(int l, int r) {
    nodes.push_back(Node{});
    int id = (int)nodes.size() - 1;
    if ( l == r) {
        nodes[id].val = a[l];
    } else {
        int mid = (l + r) / 2;
        nodes[id].lc = init(l,mid);
        nodes[id].rc = init(mid + 1, r);

        cout << "nodes[id].lc = " << nodes[id].lc << "\n";
        cout << "nodes[id].rc = " << nodes[id].rc << "\n";
        nodes[id].val = nodes[nodes[id].lc].val + nodes[nodes[id].rc].val;
    }

    cout << "id = " << id << "\n";
    return id;
}  
    
int main() {
    cin >> n >> q;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> root; 
    root.push_back(init(1 , n));

    return 0;
}

错误代码输入输出 #

输入6 0 1 2 3 4 5 6的输出：

6 0 1 2 3 4 5 6
id = 3
id = 4
nodes[id].lc = 3
nodes[id].rc = -1
id = 2
id = 5
nodes[id].lc = -1
nodes[id].rc = 5
id = 1
id = 8
id = 9
nodes[id].lc = -1
nodes[id].rc = 9
id = 7
id = 10
nodes[id].lc = -1
nodes[id].rc = 10
id = 6
nodes[id].lc = -1
nodes[id].rc = -1
id = 0

修复后的代码 #

int init(int l, int r) {
    nodes.push_back(Node{});
    int id = (int)nodes.size() - 1;
    if ( l == r) {
        nodes[id].val = a[l];
    } else {
        int mid = (l + r) / 2;
        int id_l = init(l,mid);
        int id_r = init(mid + 1, r);
        nodes[id].lc = id_l;
        nodes[id].rc = id_r;

        cout << "nodes[id].lc = " << nodes[id].lc << "\n";
        cout << "nodes[id].rc = " << nodes[id].rc << "\n";
        nodes[id].val = nodes[nodes[id].lc].val + nodes[nodes[id].rc].val;
    }

    cout << "id = " << id << "\n";
    return id;
}  

修复后代码输入输出 #

相同输入下的输出：

id = 3
id = 4
nodes[id].lc = 3
nodes[id].rc = 4
id = 2
id = 5
nodes[id].lc = 2
nodes[id].rc = 5
id = 1
id = 8
id = 9
nodes[id].lc = 8
nodes[id].rc = 9
id = 7
id = 10
nodes[id].lc = 7
nodes[id].rc = 10
id = 6
nodes[id].lc = 1
nodes[id].rc = 6
id = 0

成因分析 #

问题核心是vector动态扩容导致引用失效：

• 错误代码中，nodes[id].lc = init(l,mid)执行时，nodes[id]是对vector中元素的直接引用。而init()内部会调用nodes.push_back(Node{})，当vector当前容量不足时，会触发扩容——重新分配更大的内存块，拷贝原元素后释放旧内存。
• 扩容完成后，原来的nodes[id]引用已经指向被释放的无效内存，后续对nodes[id].rc的赋值、读取nodes[id].lc的操作，都是在操作无效内存，最终读到的是随机值（这里恰好是Node构造函数默认的-1）。
• 修复后的代码先将init()的返回值存在栈上的中间变量里，这些变量不受vector扩容影响。等两次init()调用完成（可能的扩容已经结束），再将中间变量的值赋值给nodes[id].lc和nodes[id].rc，此时nodes[id]的引用已经指向扩容后的有效内存，所有操作都能正常执行。

内容的提问来源于Stack Exchange，提问作者Jeff