CODEWITHSUNDEEP
c++syntaxtype-safety
Nick Heiner
Nick Heiner

Reputation: 122450

C++ STL: Trouble with iterators

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);
}

Upvotes: 0

Views: 205

Answers (6)

jfs
jfs

Reputation: 414265

  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());
}

Upvotes: 1

JSchlather
JSchlather

Reputation: 1603

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.

Upvotes: 2

CMircea
CMircea

Reputation: 3568

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.

Upvotes: 0

Jay
Jay

Reputation: 14471

What error are you getting?

Have you tried this?

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

Upvotes: 1

CB Bailey
CB Bailey

Reputation: 791929

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.

Upvotes: 5

Mark Rushakoff
Mark Rushakoff

Reputation: 258208

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.)

Upvotes: 5

Related Questions