观察以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

vector<int> X, Y, A, val;
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
int solve(int i, int l, int r) {
  if (l == r)
    return val[i] = A[l];
  int mid = (l + r) >> 1, p = X.size();
  X.push_back(0), Y.push_back(0);
  X[p] = solve(ls(i), l, mid);
  Y[p] = solve(rs(i), mid + 1, r);
  // do something
  return val[i];
}

这是一份标准的线段树分治代码，其中数组 $A$ 是给定的，val 在 solve 函数调用之前已经分配好了内存，而 $X$ 和 $Y$ 的内存空间则是动态分配的。

当我在本地测试完整的代码时，不会出现任何的异常。当我将代码提交到学校的 OJ 上时，却发现输出的结果不符合预期，而且对于同样的输入，输出却和本地有所出入。

经过艰难的排查，我最终发现问题出现在了 solve 函数中，即上述代码的第 8 至 9 行。我尝试将这两行替换为下面的代码：

1
2
3
4

int lp = solve(ls(i), l, mid);
X[p] = lp;
int rp = solve(rs(i), mid + 1, r);
Y[p] = rp;

这时 $X[p]$ 与 $Y[p]$ 的值就从错误的 0 变成了正确的答案。

我不禁陷入沉思，为何看似逻辑完全相同的代码，产生的效果却大相径庭？直到我发现第 7 行代码中的操作：

1

X.push_back(0), Y.push_back(0);

有没有可能，在第 8 行和第 9 行的赋值过程中，编译器先对等号左边的表达式进行计算，得到 $X[p]$ 和 $Y[p]$ 的左值引用，然后再计算了等号右边的表达式，调用了 $solve$ 函数呢？

这样一切就解释得通了，$X[p]$ 和 $Y[p]$ 的引用先被取出，然后在递归调用 $solve$ 函数的过程中，执行到了第 7 行的 push_back 函数，使得 vector 重新分配了堆空间，导致 $X[p]$ 和 $Y[p]$ 的引用失效。于是，在赋值的过程中，我们对一个已经被释放掉的空间进行了修改，且不说有没有访问到不该访问的位置，当前 vector 中真实的 $X[p]$ 和 $Y[p]$ 也没能被赋为正确的值。

现在我们弄清楚发生 UB 的过程了。在这之后，我又进行了一些测试，目的在于弄清楚产生两种不同情况的本质原因。继续观察以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <bits/stdc++.h>
using namespace std;
int func1() {
  cout << "func1" << endl;
  return 1;
}
int func2() {
  cout << "func2" << endl;
  return 2;
}
int func3() {
  cout << "func3" << endl;
  return 3;
}
struct node {
  int arr[100];
  int &operator[](int i) {
    func1();
    return arr[i];
  }
};
int main() {
  node a;
  (a[0] = func2()) = func3();
  return 0;
}

当我使用 g++ 作为编译器，输出结果如下：

1
2
3

func1
func2
func3

当我使用 clang 作为编译器，输出结果如下：

1
2
3

func3
func2
func1

归根结底，产生这两种区别的原因还是在于编译器的实现。从上面的例子可以看出，g++ 在执行赋值语句的过程中，会从左往右进行运算，而 clang 则是从右往左。

在我的本机上，常用的编译器是 clang，因此上文中线段树分治的代码从右往左执行赋值操作，不会产生引用失效的问题。而学校 OJ 的默认编译器为 g++，自然就出现与预期相违的情况了。

个人认为，对于这两种执行顺序，应当是从右往左更加符合正常人的逻辑，毕竟如 A = B = C 这样的连续赋值语句也是从右往左执行的。

总而言之，为了不触发此类未定义行为，在写代码时还需要多注意一下。对于本文开头的例子，最好还是在调用 solve 函数之前先对 $X$ 和 $Y$ 的内存空间进行 reserve，这样就不会在 push_back 时出现引用失效的问题了。