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?
Usually
std::vectorpreallocates more memory than you need, so amortized cost ofvector::push_backwasO(1).You can check what's
std::vector::capacity()is. Depending on implementation it could be different. E.g. ifcapacity() == size()and we want to insert a new element, newcapacity()will likely be either1.5 * size()or2 * size().So that's likely the case here.
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?
No, it's only happens when you use
std::vector::at(idx). In case ofoperator[]no boundary checks are performed, so it's likely to be an undefined behaviour.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 :(
If it's
+ small constantout of boundary ofstd::vectorI wouldn't risk.Even so in this case it has some garbage in
index >= current_sizeelements 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] <= randr - lis very small, then you can try it =).Ok, thanks :)
You need size to be a large power of 2. 1024 is minimal sufficient to crash this solution.
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.
Difference between
operator[]and methodat()is thatoperator[]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 nonexistentvector<T>.