0

I was working on a competitive programming question. I wrote this question to count the number of "VK" substrings.

int count(string test) {
    int answer = 0;

    for (int i = 0; i <= test.size()-2; i++) {
        if (test.substr(i,2) == "VK")
            answer++;
    }

    return answer;
}

Why did I receive this error message when I try just "V" as the argument?

terminate called after throwing an instance of 'std::out_of_range'
what():  basic_string::substr: __pos (which is 2) > this->size() (which is 1)

Shouldn't the statements in the for loop not execute because the loop's condition failed?

Rakete1111
  • 47,013
  • 16
  • 123
  • 162
Boz Steinkalt
  • 43
  • 1
  • 5

1 Answers1

3

Shouldn't the statements in the for loop not execute because the loop's condition failed?

Yes, you are right, but the condition didn't fail!. test.size() is a std::size_t, an implementation defined unsigned type.

The key here is that it is unsigned, meaning that it can overflow without invoking undefined behavior. When you pass "V", test.size() is 1. Then, 1 - 2 is equal to -1, but this overflows as an unsigned number cannot take negative numbers! The result is a very large number.

So, the loop executes a lot more times than you would have thought, and that is were the std::out_of_range exception comes from: On the second iteration, you are already accessing index 1, which is out of range (as test has size 1).

You need to introduce a pre-condition check:

if (test.size() < 2)
    return 0;
Rakete1111
  • 47,013
  • 16
  • 123
  • 162
  • 1
    Isn't it: if (test.size() < 2) – J. Calleja Apr 16 '17 at 19:32
  • 1
    This is good all the way up to the suggested fix. The `size` test would need to be `< 2` or `<= 1` but personally I suggest just changing the OP's `for` loop condition by adding `2` to both sides of the equation: `for (int i = 0; i + 2 <= test.size(); i++)` – Mark B Apr 16 '17 at 19:33
  • @Rakete111 So "test.size() - 2" remains an unsigned int even when compared to the integer i? – Boz Steinkalt Apr 16 '17 at 21:11
  • @BozSteinkalt Yes, see this [question](http://stackoverflow.com/questions/5416414/signed-unsigned-comparisons) for more information about that. – Rakete1111 Apr 16 '17 at 21:14