0

I was making a simple palindrome checker and can't understand why the iterator works with index 0, but won't work with index -1, you can see that both codes print the SAME text, but not the same boolean.

Can anyone explain me what's the logic behind this?

The only different part on both codes is this:

for(int i=text.size();i>=-1;i--) Not Working
for(int i=text.size()-1;i>=0;i--) Working

WORKING:

#include <iostream>

// Define is_palindrome() here:
std::string is_palindrome(std::string text){
  std::string reverse= "";
  for(int i=text.size()-1;i>=0;i--){
    reverse += text[i];
  }
  if(reverse == text){

    return text + " IS palindrome (reverse text: " + reverse +")";
  } else {

    return text + " NOT palindrome (reverse text: " + reverse + ")";
  }
}

int main() {
  
  std::cout << is_palindrome("madam") << "\n";
  std::cout << is_palindrome("ada") << "\n";
  std::cout << is_palindrome("lovelace") << "\n";
  
}

output

madam IS palindrome (reverse text: madam)
ada IS palindrome (reverse text: ada)
lovelace NOT palindrome (reverse text: ecalevol)

NOT WORKING

#include <iostream>

// Define is_palindrome() here:
std::string is_palindrome(std::string text){
  std::string reverse= "";
  for(int i=text.size();i>=-1;i--){
    reverse += text[i];
  }
  if(reverse == text){

    return text + " IS palindrome (reverse text: " + reverse +")";
  } else {

    return text + " NOT palindrome (reverse text: " + reverse + ")";
  }
}

int main() {

  std::cout << is_palindrome("madam") << "\n";
  std::cout << is_palindrome("ada") << "\n";
  std::cout << is_palindrome("lovelace") << "\n";

}

output

madam NOT palindrome (reverse text: madam)
ada NOT palindrome (reverse text: ada)
lovelace NOT palindrome (reverse text: ecalevol)
Davi Areias
  • 95
  • 1
  • 1
  • 7
  • 1
    If text is of size `N`, then `text[N]` is out of bounds. `text[-1]` is out of bounds no matter the size. Your second loop is the correct loop. What is your question? – sagi Jan 13 '22 at 09:59
  • 1
    I assume you are new to c++ and is coming from python. c/c++ doesn't support negative index as python does (also no index splicing). – Abdur Rakib Jan 13 '22 at 09:59
  • Also, there is an easy way of reversing a string. It's the `std::reverse()` function. Works great with string. – Abdur Rakib Jan 13 '22 at 10:02
  • @sagi the code is working , check the output. if it was out of bounds it wouldn't even compile – Davi Areias Jan 13 '22 at 10:05
  • Or, if you don't want in place, `std::string::insert(this.end(), other.rbegin(), other.rend())`. – Abdur Rakib Jan 13 '22 at 10:09
  • @DaviAreias The first part of your question has the `i>=-1` loop as the first loop, but later the code snippets have the `i>=0` loop as the first loop. That will confuse everyone when talking about first and second loop... – mch Jan 13 '22 at 10:10
  • 2
    The compiler can't know that the indexing will be out of bounds. – sagi Jan 13 '22 at 10:10
  • 1
    @Davi - sagi explains why the non-working version is not working. :-) The difference is not in the for-loop, but in the indexing. When you start at `i = text.size()`, you are immediately out of bounds. – BoP Jan 13 '22 at 10:10
  • In c++ container classes use index differently from conventional arrays. In short, the index never fails even if it's out of bound (unchecked). But out of bound indices won't show error and compile but will very definitely give weird outputs. – Abdur Rakib Jan 13 '22 at 10:11
  • @AbdurRakib, what do you mean by "the index never fails even if it's out of bound"? – kuro Jan 13 '22 at 10:17
  • Do you expect both versions to work? Why? Explain the reason why you think the difference is not important. – n. m. could be an AI Jan 13 '22 at 10:18
  • @kuro https://stackoverflow.com/questions/65373289/does-string-in-c-have-no-out-of-bound-exeption-error – sagi Jan 13 '22 at 10:21
  • @n. 1.8e9-where's-my-share m. I want to understand why both versions print the same text and reversed text, but print different booleans – Davi Areias Jan 13 '22 at 10:22
  • one is wrong and the other is correct. Wrong code can print correct results by chance. – 463035818_is_not_an_ai Jan 13 '22 at 10:23
  • This is called `undefined behaviour`. @DaviAreias, you can't understand it, because as the name suggests, it's undefined. – sagi Jan 13 '22 at 10:23
  • @sagi, uh. I misunderstood his comments. stupid of me – kuro Jan 13 '22 at 10:30
  • @kuro, for container classes. For example, say there is a vector `v` with size `100`. Then out of bound indices like `v[-1]`, `v[100]`, `v[200]` etc. won't give any error but will return weird values. But for conventional arrays like `int arr[100]=//something`, `arr[-1]`, `arr[100]` etc. will give compile-time error. – Abdur Rakib Jan 13 '22 at 10:38
  • Both versions *print* the same text, but it doesn't mean it *is* the same text. Strings may contain unprintable characters. To be absolutely sure about the content of the string, you need to print each character individually. Print printable characters as is, print numeric codes in place of unprintable characters. (Actually doing this is not extremely useful in this particular case, because you know where undefined behaviour is. But it is generally useful if you see strange string-related behaviour). – n. m. could be an AI Jan 13 '22 at 10:38
  • @AbdurRakib "will give compile-time error" It may, or it may not, depending on lots of things. There is no such requirement in C++. – n. m. could be an AI Jan 13 '22 at 11:25

2 Answers2

1

C++ uses 0-based indexing, ie valid indices of a N sized container are 0,1,2...N-1. If you try to use an index out of bounds your code invokes undefined behavior.

Look at the output of this code:

#include <iostream>
#include <string>

void foo(const std::string& text){
    for(int i=text.size();i>=-1;i--){
        std::cout << i << "\n";
    }
}
int main() {
    foo("madam");
}

It is

5
4
3
2
1
0
-1

Both -1 and 5 are not elements of the string, because it has only 5 characters. (For 5 I am allowing myself to simplify the matter a bit, because strings have some oddities for accessing the one past last character null terminator. As -1 definitely is out of bounds and with std::string you usually need not deal with the null terminator explicitly, this is ok for this answer).

Now look at the output of this code:

#include <iostream>
#include <string>

void foo(const std::string& text){
    for(int i=text.size()-1;i>=0;i--){
        std::cout << i << "\n";
    }
}
int main() {
    foo("madam");
}

It is

4
3
2
1
0

It iterates all characters of the input string. Thats why this is correct and the other is wrong.

When your code has undefined behavior anything can happen. The results may appear to be correct or partially correct. Wrong code does not necessarily produce obviously wrong output.

Note that for(int i=text.size()-1;i>=0;i--) is a problem when the size of the string is 0, because size() returns an unsigned which wraps around to result in a large positive number. You can avoid that by using iterators instead. There are reverse iterators that make a reverse loop look the same as a forward loop:

#include <iostream>
#include <string>

int main() {    
    std::string text("123");
    for (auto i = text.rbegin(); i != text.rend(); ++i) std::cout << *i;
}

Output

321
463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
0

In addition to the answer by 463035818_is_not_a_number, you can also construct a string from another string using iterators:

#include <iostream>
#include <string>

int main() {    
    std::string text("123");
    std::string rev(crbegin(text), crend(text));
    std::cout << rev << '\n';
}

And there's std::reverse

#include <iostream>
#include <string>
#include <algorithm>

int main() {    
    std::string text("123");
    reverse(begin(text), end(text));
    std::cout << text << '\n';
}

But for a palindrome, you don't have to compare two whole strings. You just need to see of the first half of the string is equal to the reverse of the last half of the string.

JHBonarius
  • 10,824
  • 3
  • 22
  • 41