I used Ai to format the Blog
While solving the problem TTM on SPOJ using a Persistent Segment Tree, I ran into a very frustrating bug
My code was logically correct, yet I was getting completely different verdicts depending on the compiler:
- Accepted on
C++14 (Clang) - Wrong Answer on
C++14 (GCC)
After a long debugging, the issue turned out to be caused by unspecified evaluation order
Here is the problematic line:
// 't' is the current version number of the Persistent Segment Tree
if (op == 'C') {
int l, r, d;
cin >> l >> r >> d;
--l, --r;
// The fatal line:
pst.roots[++t] = pst.update(t, l, r, d);
}
What’s the Problem?
In C++14 and older, the C++ standard does not specify the evaluation order of the operands of the assignment operator (=)
That means the compiler is free to evaluate either:
- the left-hand side first (
pst.roots[++t]) - or the right-hand side first (
pst.update(t, ...))
As a result, different compilers may execute the statement differently.
How Clang Evaluated It (Right-to-Left) → AC
Clang evaluated the right-hand side first:
pst.update(t, ...)
At this moment, t still had its old value (say 0).
So the update correctly created a new version based on:
roots[0]
Then Clang evaluated:
++t
which incremented t to 1, and finally assigned the result to:
roots[1]
This happened to match my intended logic.
How GCC Evaluated It (Left-to-Right) → WA
GCC evaluated the left-hand side first:
++t
So t immediately became 1.
Then the right-hand side was evaluated:
pst.update(t, ...)
But now t == 1, meaning the update tried to build the new version from:
roots[1]
instead of:
roots[0]
Since roots[1] had not been created yet, the persistent chain broke completely.
The Fix
Simply separate the increment from the function call:
++t;
pst.roots[t] = pst.update(t - 1, l, r, d);
or:
int newRoot = pst.update(t, l, r, d);
pst.roots[++t] = newRoot;
A Fun C++17 Fact
The C++ standards committee recognized how dangerous and confusing this behavior was.
Starting from C++17, the evaluation order of assignment expressions became well-defined, and the right-hand side is guaranteed to be evaluated before the left-hand side.
So this exact bug disappears in modern C++ standards.
This was one of the sneakiest bugs I’ve encountered, because the code looked perfectly fine and even passed on one compiler.
A good reminder that undefined/unspecified behavior in C++ can destroy your sanity :)
