Why do I have an infinite loop? Simple question, short code

user_14039173 0
Viewed 142

If the input array is empty, then array.size() should be 0. The first for, that goes from 0 to array.size() - 1, should mean it goes from 0 to -1, right?

This for then, should not be entered and the function should return the inversionsCounter value which would be 0

But this doesn't happen, and the code enters an infinite loop. Why is this?

Here is the code:

#include <vector>
#include <iostream>

using namespace std;

int countInversions(vector<int> array)
{    
    int inversionsCounter = 0;
    for (int i = 0; i < array.size() - 1; ++i)
        for (int j = i + 1; j < array.size(); ++j)
            if (array[i] > array[j])
                ++inversionsCounter;

    return inversionsCounter;
}

int main()
{
    vector<int> array = {};
    cout << array.size();
    cout << countInversions(array);
}
infinite-loop vector for-loop implicit-conversion c++
3 Answers

The type of the return value of the member function size of the class template std::vector is unsigned integer type usually equivalent to the type size_t.

So in the condition of the for loop

for (int i = 0; i < array.size() - 1; ++i)

due to the usual arithmetic conversions the both operands of the expression

i < array.size() - 1

are converted to the unsigned integer type that corresponds to the type std::vector<int>::size_type. As a result the expression array.size() - 1 is converted to a maximum value of the type when the member function size returns 0.

Here is a demonstrative program.

#include <iostream>
#include <iomanip>

int main() 
{
    std::cout << size_t( -1 ) << '\n';
    std::cout << std::boolalpha << ( 0 < size_t( -1 ) ) << '\n';    
    
    return 0;
}

Its output is

18446744073709551615
true

So when the member function size returns 0 you have in fact a loop like this

for (int i = 0; i < 18446744073709551615; ++i)

Instead of the type int you should use at least the type size_t for indices. And the outer loop should look like

for ( size_t i = 0; i < array.size(); ++i )
user_28772410

The return type for the size() method on vector<> is size_t , an unsigned integral value - often just unsigned int. This type , size_t, is unsigned and can not carry negative numbers. In most cases the compiler will warn you about this.

When it is time to execute the code, however, the compiler substitutes the 'ones complement' form of the signed integer -1 (calculated from size() - 1 ) to the size_t (unsigned) type.

This -1 signed number is often very very large when an attempt is made to represent it as an unsigned number. Much of the specifics here depend on your particular machine and compiler details.

This means that your outer for loop for (int i = 0; i < array.size() - 1; ++i) is not running in an infinite loop, but a very long one.

user_60160710

cast array.size() to an int otherwise like ...

(int)array.size()
Admin1
Related