### ouuan's blog

By ouuan, history, 7 weeks ago, ,

Today, I spent a whole afternoon solving 786C - Till I Collapse, because of undefined behavior.

The origin code is here: 66394911. It seems pretty well, but can't even pass the sample tests.

However, after adding one line (t.reserve(5000000);) it passed: 66394938.

For those who don't want to read my codes, here is a shorter one:

#include <iostream>
#include <vector>

using namespace std;

vector<int> bar;

int foo(int p)
{
int x = bar.size();
bar.push_back(bar[0]);
if (p == 0) return x;
bar[x] = foo(p - 1);
cout << bar[x] << ' ';
return x;
}

int main()
{
bar.resize(1, 0);
foo(5);
return 0;
}


Can you guess the output?

The output

The reason

• +122

 » 7 weeks ago, # |   +28 Some notes: The old code is always correct in C++ 17. The same thing happen for something like x.emplace_back(x[0]), or auto& stored_reference = ...; modify();. This kind of bug cannot be prevented with _GLIBCXX_DEBUG currently. However, iterator invalidation can be prevented. Another way to fix the bug is auto tmp = foo(p - 1); bar[x] = tmp;
 » 7 weeks ago, # |   +18 this "bug" is fixed with c++17, the order of evaluation is specified to be first the right side of the assignment then the left (as you would probably expect it).