Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

Luca1152's blog

By Luca1152, history, 2 months ago, In English,

Consider the following code snippet (for demonstration purposes):

#include <bits/stdc++.h>

using namespace std;

int main(){
    char s[] = "x";
    for (int i=0; i<=strlen(s)-4; i++){
        cout << s[i];
    }
    return 0;
}

You'd expect the for to never loop at all, since the initial value of i (0) would be higher than that of strlen(s)-4 (-3) right? But no, it becomes an infinite loop... You can test it yourself. Here are the watches from a random state in the loop:

After searching about this issue a bit, I read that it isn't a good practice to put strlen() into a for as a condition, since it takes time to compute it each loop. So yes, from now on I will avoid this approach, either by storing the value into a variable beforehand, or by checking if I reached the end using s[i].

But... What if whatever causes this occurs in some other context that doesn't involve strlen()? I'd like to understand why this happens in the first place, so I can better watch out for it.

So could somebody help me understand what is going on here? :)

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Strlen returns size_t (unsigned value), so 1 — 4 = INT_MAX — 2(or -3). That's why it seems it is an infinite loop.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Ohhhh, right.

    Who would have thought that the warning: comparison between signed and unsigned integer expressions [-Wsign-compare] you get with such code is actually useful, since it may sometimes lead to something you'd not expected? :))

    Cheers, mate!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

strlen returns size_t which is basically a type of unsigned integer. In unsigned integers, -3 is actually INT_MAX-2, which is obviously greater than most values of i. That is why your loop runs for a very long time.

You can fix it easily by type casting it to a signed integer.

i<=(int)strlen(s) - 4

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Also beware that strlen() is of O(n) complexity. Putting it in for loop condition may result in TLE

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Just to add a little clarity, your heading says "Weird strlen() behaviour in C++ for loops", but, strlen() is not a C++ function. It is a C function incorporated into C++ with the help of STL. For strict C++ implementation, you should be using std::string. The std::string::size() method is O(1) in comparison to O(N) of strlen(). Like ahshafi mentions above, you could prevent a possible TLE, as you have strlen() involved as a loop condition.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    strlen has nothing to do with templates. It is the same implementation designed to work on C style arrays

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I never said strlen() has anything to do with templates. Maybe you misread. As C++ builds on to C, it must provide backward compatibility for C functions and code. That's the only reason why you can still use strlen() (on const char* and char* of course) instead of the object-oriented std::string, and STL is what incorporates it all for C++.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Aside: C string handling functions are notorious for being difficult to use and understand, and continue to cause many security vulnerabilities to this day. C++ strings are so much better for writing safe robust code.