LLI_E_P_JI_O_K's blog

Strange behaviour for vector<> in GNU C++11
By LLI_E_P_JI_O_K, history, 8 years ago, In Russian

Hello, guys!

Today in Codeforces round 402 (Div 2) I tried to challenge this solution with a test:

5 2
1 1 1 1 1
5 5 5 5 5

So, as you can see in the code this cycle has no any check for reaching the end of the vector "v":

...
while (v[j].first<0||j<r)
{
sum1+=v1[v[j].second];
j++;    
}
...

Obviously "j" will be out of the vector for such testcase and we will check whether "v[5].first<0" or not, but no any Runtime Error when trying to get nonexistent element of vector. So, as you can understand, challenge was unsuccessful. Why?

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

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

Usually std::vector preallocates more memory than you need, so amortized cost of vector::push_back was O(1).

You can check what's std::vector::capacity() is. Depending on implementation it could be different. E.g. if capacity() == size() and we want to insert a new element, new capacity() will likely be either 1.5 * size() or 2 * size().

So that's likely the case here.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, but as I thought, if we try to get element with index >= current size of vector via operator [], then an exception should be thrown and immediately we should get Runtime Error. Isn't it?

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

      No, it's only happens when you use std::vector::at(idx). In case of operator[] no boundary checks are performed, so it's likely to be an undefined behaviour.

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

        Ok, that's a pity. How to challenge such solutions? They obviously contain error. I met one more such solution in my room today, but didn't try to challenge, because it would be unsuccessful too :(

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

          If it's + small constant out of boundary of std::vector I wouldn't risk.

          Even so in this case it has some garbage in index >= current_size elements it's hard to predict what exactly we have there. It can be a positive value and everything will work. So to challenge the solution you probably need a few attempts.

          Although if it has more limited range check for a value like: l <= vec[out_of_boundary] && vec[out_of_boundary] <= r and r - l is very small, then you can try it =).

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

You need size to be a large power of 2. 1024 is minimal sufficient to crash this solution.

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

    Even if the accessed element will be out of the reserved capacity of the vector it might not crash anyway. And you can't guess what garbage will be there. So it's not sufficient.

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

Difference between operator[] and method at() is that operator[] has no bounds checking. So you can use elements which are not logically existent, but physically they are. I mean, it just a place in RAM — so if it is valid, you can use it, but you cant be sure if it is not used by another piece of code or even another program.

Runtime error appears when you are trying to get element by invalid address. It may cause if you are getting element of vector<vector<T> > by using [i][j] with invalid i. In this case it is possible to get invalid pointer by asking this from nonexistent vector<T>.

→ Reply