觀察以下程式碼：
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\) 行。我嘗試將這兩行替換為下面的程式碼：
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\) 行程式碼中的操作：
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 的過程了。在這之後，我又進行了一些測試，目的在於弄清楚產生兩種不同情況的本質原因。繼續觀察以下程式碼：
#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++ 作為編譯器，輸出結果如下：
func1
func2
func3
當我使用 clang 作為編譯器，輸出結果如下：
func3
func2
func1
歸根結底，產生這兩種區別的原因還是在於編譯器的實現。從上面的例子可以看出，g++ 在執行賦值語句的過程中，會從左往右進行運算，而 clang 則是從右往左。
在我的本機上，常用的編譯器是 apple-clang，因此上文中線段樹分治的程式碼從右往左執行賦值操作，不會產生參照失效的問題。而學校 OJ 的預設編譯器為 g++，自然就出現與預期相違的情況了。
個人認為，對於這兩種執行順序，應當是從右往左更加符合正常人的邏輯，畢竟如 A = B = C 這樣的連續賦值語句也是從右往左執行的。
總而言之，為了不觸發此類未定義行為，在寫程式碼時還需要多注意一下。對於本文開頭的例子，最好還是在呼叫 \(solve\) 函數之前先對 \(X\) 和 \(Y\) 的記憶體空間進行 \(reserve\)，這樣就不會在 \(push\_back\) 時出現參照失效的問題了。