Generic Programming in C++ part 3a: Palindromes

If you've been to an interview where you've been asked to write some C++ code, there's a fair chance that you'll have come across the "isPalidrome" problem.

It goes something like this: A palidrome is a group of letters that is the same written backwards or forwards. The challenge is to write a function that tests whether a given string is a palindrome.

A typical solution may look something like this:

bool isPalindrome(const std::string &str)
{
    std::string::const_reverse_iterator itEnd = str.rbegin()++;
    for (std::string::const_iterator itStart = str.begin(); itStart < itEnd.base(); ++itStart, ++itEnd)
    {
        if (*itStart != *itEnd)
        {
            return false;
        }
    }    return true;
}

(Actually, if you're in an interview you may have forgotten to start at before the one-past-end iterator and you may not have used a reverse iterator or perhaps forgot the call to base when comparing iterators and reverse iterators.  Those kind of things you can be forgiven!)

That solution works fine. Use two iterators, one pointing to the first and one to the last characters (which, as mentioned above is one before that returned by end).  Compare the characters and move the iterators toward the middle of the string.  If any comparison fails, the string is not a palindrome.  Finish when the start iterator is past the end (note that this takes into consideration both finishing conditions ie when there is an even or an odd number of characters in the string).

[There are other algorithms but we’ll stick with this one for now.]

We can do better. Why not write it generically?  It may not be obvious to you, but std::string is a container.  We can apply this same algorithm for any other container.  Consider writing reusable functions generically – especially after ‘getting them right’ non-generically.

template <typename RaIterator>
bool
isPalindrome(RaIterator begin, RaIterator end)
{
    for (--end; begin < end; ++begin, --end)
    {
        if (*begin != *end)
        {
            return false;
        }
    }
    return true;
}

Something has changed; we’re assuming that two random access iterators have been passed in.  We need random access iterators because of the less than operator, which is only provided on these kind of iterators.  And you’ll not that we’ve used a bidirectional operation – the decrement operator – instead of using a reverse iterator.  That’s to avoid weird syntax – asking the user to supply two different kinds of iterators is unusual (and prone to error!) and you won’t see that done in any standard algorithm.

Usage is slightly different, now we have to pass in stringname.begin() and stringname.end() instead of just stringname.  But again that’s consistent with the Way Of The Standard.  (It also has an advantage - we can operate on slices of a container.)

So how is this better?  Well, if we have a vector of characters we can use this function.  Or if we have a vector of longs.  Or a deque of longs.  Or an array of longs.  We could even have a vector of strings that form a sentence and use this function to determine if the sentence is a palindrome!

You get the picture.  Generic is better.

Unfortunately if we have a list or set of chacters we can’t use this function – you’ll get an ugly compilation error.  Why?  Because lists only provide bidirectional iterators.  And bidirectional iterators don’t give us that lovely less than operator.  So any container that provides anything less than random access iterators will not compile.  Bugger!  I wonder if we can get around that limitation…

Tune in to part b where I improve our isPalindrome function further, so we can use it with lists!

 

[I’ll admit that thinking at this level of abstraction is difficult in an interview situation but when you start thinking generically you’ll find that it won’t be too much of a stretch.  Disclaimer:  In the last interview I sat I wrote the first example…]