CODEWITHSUNDEEP
c++stringfor-loop
Vishal Srivastav
Vishal Srivastav

Reputation: 603

For loop running infinitely with string length in C++

I am very surprised with this behavior of for loop :

program 1 : 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    for(int i=0;i<(s1.length()-s2.length()+1);i++)
    {
        cout<<"Hello\n";
    }
}

After giving input : s1 = "ab" , s2 = "abcdef"

This for loop of program 1 is running infinitely and printing "Hello" infinite times.

Whereas , Program 2 (below) is working fine for both same input of string s1 and s2.

program 2 :

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    int len = (s1.length()-s2.length()+1);
    for(int i=0;i<len;i++)
    {
        cout<<"Hello\n";
    }
}

Why is the for loop of program 1 running infinite times?

Upvotes: 0

Views: 633

Answers (2)

yeputons
yeputons

Reputation: 9238

In your example, s1.length() is evaluated to 2u (i.e. 2, but in an unsigned type), s2.length() is evaluated to 6u, s1.length() - s2.length() is most probably evaluated to 4294967292u (because there is no -4 in unsigned types), and s1.length() - s2.length() + 1 is evaluated to 4294967293u.

.length() return size_t in C++, which is unsigned value. Subtracting an unsigned value from another unsigned value yields an unsigned value, e.g. 1u - 2u may result in 4294967295.

When mixing signed and unsigned values (e.g. s.length() - 1 or i < s.length()), the signed value is converted to an unsigned, e.g. -1 > 1u is typically true because -1 is converted to 4294967295. Modern compilers will warn you about such type of comparisons if you enable warnings.

Knowing that, you may expect that your loop is running for 4 billion iterations, but that's not necessarily true, because i is a signed int, and if it's 32-bit (most probably), it cannot become bigger than 2147483647. And the moment your program increases it from 2147483647, signed overflow happens, which is undefined behavior in C++. So your loop may very well run infinitely.

I suspect you're doing competitive programming. My recommendation for competitive programming would be to always cast .length() to int whenever you want to calculation anything. You can create a macro like this:

#define sz(x) ((int)(x).size())

and then write sz(s) instead of s.length() everywhere to avoid such bugs.

However, that approach is highly frowned upon in any area of programming where code has to live longer than few hours. E.g. in the industry or open-source. For such cases, use explicit static_cast<int>(s.length())/static_cast<ssize_t>(s.length()) every time you need it. Or, even better, ask about during code review to get specific recommendations concerning your code, there are lots of possible caveats, see comments below for some examples.

Upvotes: 4

Flight Odyssey
Flight Odyssey

Reputation: 2287

I haven't had a chance to test this yet so I can't say for sure, but I strongly suspect that this is related to the fact that string::length() returns a size_t, which is an unsigned type. Unsigned types wrap around to the maximum value if they become negative, so 2-6+1=-3 which becomes 2^32-3 when interpreted as 32 bit unsigned. This causes your loop to iterate billions of times, hence seemingly not terminating. Whereas in your second program you are explicitly converting to a signed int so the result is -3 as expected.

Upvotes: 1

Related Questions