Hey all

I have seen a lot of stuff about palindrome checkers so I thought I would write one that works for STL containers as well as arrays. it accepts a bidirectional iterator to the first element and an bidirectional iterator to 1 after the last element. Included is a sample of it working with a string and a vector of int's. At most this function requires O N/2 iterations(correct me please if I'm wrong). Also I chose for single characters to be considered a palindrome. I hope you guys will find this useful.

Edited 6 Years Ago by NathanOliver: n/a

// Palindrome.h
// start points to the beginning of the data and end points to one past the end
template<typename BidirectionalIterator>
bool IsPalindrome(BidirectionalIterator start, BidirectionalIterator end)
{
	if (start == end - 1)
		return true;
	end--;
	while (start <= end)
	{
		if (*start == *end)
		{
			start++;
			end--;
		}
		else
			return false;
	}
	return true;
}



//Main.cpp
#include <iostream>
#include <string>
#include <vector>
#include "Palindrome.h"

using namespace std;

ostream & operator<<(ostream &, vector<int> &);

int main()
{
	string word = "tattarrattat";  // longest palindrome in English
	vector<int> number;
	for (int i = 0; i < 5; i++)
		number.push_back(i);
	for (int j = 4; j >= 0; j--)
		number.push_back(j);
	if (IsPalindrome(word.begin(), word.end()))
		cout << word << " is a palindrome.\n";
	else
		cout << word << " is not a palindrome.\n";
	if (IsPalindrome(number.begin(), number.end()))
		cout << number << " is a palindrome.";
	else
		cout << number << " is not a palindrome.";
	cin.get();
	return 0;
}

ostream & operator<<(ostream & stream, vector<int> & vec)
{
	for(int i = 0; i < vec.size(); i++)
		cout << vec[i];
	return stream;
}

Instead of using two for-loops to load the vector with data, you could also do:

int arr[] = {1,2,3,2,1};
vector<int> number(arr, arr + 5);

Just a tip though.

Edited 6 Years Ago by Nick Evan: n/a

What would you have done differently? I am open to any and all suggestions.

Well you can make your code more concise.

template<typename StartItr, typename EndItr>
bool isPalin(StartItr start,EndItr end){
	assert(start <= end);		
	if(start == --end) return true;
	while(start < end && *start++ == *end--) continue;
	return (*--start == *++end);
}

But one might be able to program this using metaprograming technique, and
be able to find out whether an input is a palindrome during compile time.

If you start adding examples, it quickly becomes apparent that there is a fair amount of repetitious code in the presentation of results which could be factored out. Also, you should probably show the negative case as well.

So, if you have something like:

template<typename StartItr, typename EndItr, typename Item>
bool checkIfPal(StartItr start, EndItr end, Item item)
{   bool rc=1;
    cout << item << " is";
    if (!isPalindrome(start, end))
    {   cout << " not";
        rc=0;
    }
    cout << " a palindrome.\n";
    return rc;
}

You could more easily add an example like this:

int arrNotP[] = {1,2,3,99,1};
    vector<int> num1(arrNotP, arrNotP + 5);
    checkIfPal(num1.begin(), num1.end(), num1);

You pass num1 which is a vector of ints, and you pass its start position and its end
position, thats redundant. Makes the user do extra code. And you can't print a vector
using operator<< without defining the operator<<.

This seems somewhat unnecessary to me - the STL will already do this for any container which supports bidirectional iterators - all of those containers support begin/end and rbegin/rend, so you can use the std::equal algorithm

#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>

int main()
{
    std::string str("level");
    std::vector<char> vec(str.begin(), str.end());

    if ( std::equal(str.begin(), str.end(), str.rbegin()) )
        std::cout << "str is a palindrome" << std::endl;

    if ( std::equal(vec.begin(), vec.end(), vec.rbegin()) )
        std::cout << "vec is a palindrome" << std::endl;
}

I hate to rain on people's parades, but the original post says that it requires a bidirectional iterator. In fact, the code does <= comparisons on iterators--which means that it really requires random-access iterators.

Comments
Thanks

You are right with that arkoenig. I didn't realize that <= wasn't supported by bidirectional iterators.

The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.