C++ STL: Trouble with iterators

Question

I'm having a beginner problem:

bool _isPalindrome(const string& str)
{
    return _isPalindrome(str.begin(), str.end()); // won't compile
}

bool _isPalindrome(string::iterator begin, string::iterator end)
{
    return begin == end || *begin == *end && _isPalindrome(++begin, --end);
}

What am I doing wrong here? Why doesn't str.begin() get type checked to be a string::iterator?

Update: Better version:

bool BrittlePalindrome::_isPalindrome(string::const_iterator begin, string::const_iterator end)
{
    return begin >= end || *begin == *(end - 1) && _isPalindrome(++begin, --end);
}

Answer 1

str.begin() is non-const, while the argument str is const.

You can either change the iterator-accepting method to accept const_iterators, or you can change the string-accepting method to accept a non-const string.

Or you could cast away str's const-ness, but that would be a patent Bad Idea ^TM.

_{(I would also parenthesize your return statement on the iterator-accepting method to make your intent more clear, but that's neither here nor there.)}

Answer 2

Assuming that you have a declaration of the second function before the first function, the main issue is that you are passing the strings by const reference.

This means that the only overloads of begin() and end() that you have access to are the const versions which return std::string::const_iterator and not std::string::iterator.

The convention for iterators is that the end iterator points one beyond the end of a range and is not dereferencable - certainly if you pass str.end() as the end parameter. This means that *begin == *end is not valid, you need to decrement end once first. You are also going to have an issue with ranges with odd numbers of elements. By doing ++begin and --end with no further checking your iterators may cross over in the recursion rather than triggering the begin == end condition.

Also note that for maximum portability, global identifiers shouldn't start with an underscore.

Answer 3

What error are you getting?

Have you tried this?

bool _isPalindrome(string::const_iterator begin, string::const_iterator end)

Answer 4

You haven't declared the second function before calling it in the first function. The compiler can't find it and thus tries to convert str.begin() (string::iterator) into a const string &. You can move the first function behind the second function.

Answer 5

As previously mentioned your iterators need to be constant iterators, but there's something else wrong with your algorithm. It works fine if you have a string of odd length, but do you see what happens when your string is even length? Consider the palindrome:

aa

Your algorithm will pass in an iterator pointing to the front and to the end. All's good, then it will go to the next level, and all will still be good, but it won't end. Because your first condition will never be true. You need to check not only if begin==end but if begin+1==end or begin==end-1 if you prefer. Otherwise you're iterators are going to be upset.

Answer 6

1. replace iterator by const_iterator
2. swap function definitions
3. decrement end

Code:

bool isPalindrome(string::const_iterator begin, string::const_iterator end)
{
  return (begin == end || begin == --end || 
          *begin == *end && isPalindrome(++begin, end));
}

bool isPalindrome(const string& str)
{
    return isPalindrome(str.begin(), str.end());
}