ouuan's blog

Undefined behavior when writing persistent segment tree
By ouuan, history, 5 years ago, In English

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
  • Vote: I like it
  • +122
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Some notes:

  1. The old code is always correct in C++ 17.
  2. The same thing happen for something like x.emplace_back(x[0]), or auto& stored_reference = ...; modify();.
  3. This kind of bug cannot be prevented with _GLIBCXX_DEBUG currently. However, iterator invalidation can be prevented.
  4. Another way to fix the bug is auto tmp = foo(p - 1); bar[x] = tmp;
→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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).

→ Reply