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

Question

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);
}

First solve the : C4018: '<': signed/unsigned mismatch issue. That's a clear clue from the compiler. (I never use signed integers for values that should always be >0, use the same type as returned by array.size()). — Pepijn Kramer, Sep 09 '21 at 12:14
Please post your actual code which is causing the issue. In your posted code, you are not calling the function `countInversions` at all. — Andreas Wenzel, Sep 09 '21 at 12:19
@AndreasWenzel just uncomment the last line :)) I commented it to try to see if array.size() is really 0 — maverick.01, Sep 09 '21 at 12:22
The loop isn't technically infinite - but it will run for a fair while. `array` has size zero, so `array.size() - 1` will produce the largest value that a `std::size_t` can represent, which is often (depending on your compiler and host system) quite a large value (e.g. `4294967295` on a 32-bit system or `18,446,744,073,709,551,615` on a 64-bit system). — Peter, Sep 09 '21 at 12:24
You want to look [here](https://godbolt.org/z/6McdeWP9K) and then [here](https://stackoverflow.com/questions/57842756/why-should-i-always-enable-compiler-warnings). — n. m. could be an AI, Sep 09 '21 at 12:34
@maverick.01: Generally, your posted code should be able to reproduce the issue. It should not be necessary for the readers of your question to have to think about which parts of your code must be uncommented and which ones not, in order to reproduce the issue. It was not immediately obvious that the first part of commented code must stay deactivated but the second part of commented code must be reactivated by uncommenting. This made your question harder to understand. Meanwhile, someone else has edited your question to fix this. — Andreas Wenzel, Sep 09 '21 at 12:50

Vlad from Moscow · Answer 1 · 2021-09-09T12:35:35.643

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 )

JimmyNJ · Answer 2 · 2021-09-09T16:00:20.067

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.

score 1 · Answer 3 · answered Sep 27 '21 at 12:14

1

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

(int)array.size()

answered Sep 27 '21 at 12:14

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

3 Answers3