CODEWITHSUNDEEP
c++algorithm
shihack
shihack

Reputation: 55

Runtime Error when using vec.size() in the for loop

While solving a codeforces problem, I had to make a vector of size=1. Also, I needed to iterate back from the second last element of the vector, so I used the following technique to use for loop.

for(int i = vec.size()-2; i > -1; i--){
    vec[i] = vec[i] + vec[i+1];
}

This technique throws runtime error at codeforces compiler. But, using the size of the vector by precalculating it, it runs fine. Following snippet runs successfully.

int s = vec.size();
for(int i = s-2; i > -1; i--){
    vec[i] = vec[i] + vec[i+1];
}

Can someone help me understand this phenomenon?

PS: While figuring out the issue, I did

cout << vec.size()-2;

and to my surprise, the output came out to be

18446744073709551615

when the vector size was 1. The output should have been -1, right? Is this obvious, or something else. Kindly explain.

Upvotes: 0

Views: 518

Answers (1)

rawrex
rawrex

Reputation: 4064

Here, you trying to access vec[-1], which leads to out of range subscript.

Try to run this and look for output:

for(int i = vec.size()-2; i >= -1; i--){
    cout << i << endl; // At some point will be -1
    vector<int>::size_type j = i; // Then this will be a very large unsigned number
    cout << j << endl; // On my machine it is 18446744073709551615
    //vec[i] = vec[i] + vec[i+1];
}

When you have vec[-1], the -1 will be converted to std::vector<T>::size_type, which is unsigned. This will lead to i in effect being a very large unsigned number, which in turn leads to faulty access via subscript.

The other version is essentially the same thing, but it may execute in some way, or may not (e.g. for me it did not went well). All due to the fact that both cases are an instance of undefined behavior.

As was noted in the comments on your question, you can look toward the at() member function of std::vector (do recommend) or try to implement explicit checks for out of range subscript yourself.

As to the update of the question:

I would suggest you to implement something like the following inspection and to run it on your platform:

for(int i = vec.size()-2; i > -1; i--){
        auto a = vec[i];
        auto b = vec[i+1];
        std::cout << "i: " << i << "; " << "i+1: " << i+1 << std::endl;
        std::cout << "a:" << a << " + " << "b:" << b << " = "  << a+b  <<  std::endl;
        std::cout << std::endl;
        vec[i] = a + b;
    }

E.g. for input: std::vector<int> vec = {1,2,3,4,5}; it gives the following output:

i: 3; i+1: 4
a:4 + b:5 = 9

i: 2; i+1: 3
a:3 + b:9 = 12

i: 1; i+1: 2
a:2 + b:12 = 14

i: 0; i+1: 1
a:1 + b:14 = 15

Upvotes: 3

Related Questions