Walid_Amin's blog

Undefined behavior from C++ vector [Answered]
By Walid_Amin, history, 8 years ago, In English

UPD: It was answered in Errichto's comment

I was coding a build function for persistent segment tree using vectors and I am getting Runtime error.

I replaced vector with array and it passes.

The code is just a few lines.

Code using vector (State: gives Runtime error): http://ideone.com/2c5tec

Code using arrays (State: Okay): http://ideone.com/WxBwJJ

I spent hours trying to spot the bug in the code and I removed all the code which is irrelevant to the bug to make it more simple to debug.

What really makes it more weird is when i removed those: "v[p].l=" and "v[p].r" it runs okay, here is it: http://ideone.com/alzUxP (State: Okay)

I will appreciate it very much if anyone told me why it keeps giving RTE.

Thanks very much.

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I'm not sure about it but here's what I think/remember.

The thing is that when vector doubles its size (it must do it sometimes to contain more elements), it can be moved in the memory. So, when there is v[p].l=build(s,mid);, first a place with v[p] is remembered and then build() is run, where the size of v can be doubled and thus v[p] won't longer be in the same place.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Oh, yes you are right :)

    I modified the code and stored the returned value in a variable then store it in v[p].l and worked : http://ideone.com/wIgY3x

    Thanks you very very much Errichto :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Alternatively, you could've called reserve function on the vector, so that it won't be reallocated during the call to the build.

      → Reply