Back to basics: Palindrome

In this post, we will look at the implementation of a program to determine if a given sequence of values is a palindrome.

Wikipedia defines palindrome as "... a word, phrase, number, or other sequence of units that may be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers."

Note that palindrome applies not only to strings (strings of characters) but to sequences of units of other types as well. For the purpose of this article, we will ignore 'adjustments to punctuation and word dividers'

Here is a short program in C++11 that determines if a given sequence is a palindrome.

#include <iostream>
#include <string>
#include <vector>

class PalTester
{
public:
   template<class IT>
   bool IsPalindrome(IT itb, IT ite)
   {
      return isPalindrome(itb, ite);
   }
   
private:
   template<class IT>
   bool isPalindrome(IT itb, IT ite);
};

template<class IT>
bool PalTester::isPalindrome(IT itb, IT ite)
{
   --ite;
   
   while(itb < ite)
   {
      if(*ite != *itb)
      {
         break;
      }
      else
      {
         --ite;
         ++itb;
      }
   }

   return (ite <= itb);
}

int main()
{
   PalTester t;
   
   std::wstring s(L"MON");
   std::cout << t.IsPalindrome(s.begin(), s.end());
   
   std::vector<int> v{1, 2, 3, 4, 3, 2, 1};
   std::cout << t.IsPalindrome(v.begin(), v.end());
}

The important design highlights are as follows:

a) The interface of the class PalTester has a single member function template IsPalindrome which accepts an interator to the start and one past the end of any arbitrary sequence (similar to the way end of range iterators are handled in STL)

b) This makes the design to be consistent with the definition of a palidrome. Such an interface is also consistent with the design of several STL containers and algorithms which achieve container independence by working on appropriate iterator ranges. Note, how our example determines that the sequence of values (units of integer type) form a palindrome.

c) The function PalTester::IsPalindrome is a member function template. It requires bidirectional iterators which support prefix opertaor ++ and --. Also, the iterator needs to be deferenceable.

d) The elements of the sequence need to provide operator !=, opertaor < and operator <=.

c) Notice that the v is initialized using list initialization which is introduced in C++11.