Palindrome Tester

NathanOliver 3 328 Views

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.

// 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;
}
Member Avatar for mrnutty
mrnutty 761 Senior Poster

Nice post. Although I would have done some things different, the idea
is good.

Member Avatar for NathanOliver
NathanOliver 429 Veteran Poster

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

Member Avatar for iamthwee
iamthwee

Why have you hard coded the numbers 5 and 4?

Member Avatar for NathanOliver
NathanOliver 429 Veteran Poster

I hard coded them just to show that you can use a vector as well. It was just an example.

Member Avatar for Nick Evan
Nick Evan 4,005 Industrious Poster

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 by Nick Evan because: n/a
Member Avatar for NathanOliver
NathanOliver 429 Veteran Poster

Thanks Nick I did not know a vector could be inialized that way..

Member Avatar for mrnutty
mrnutty 761 Senior Poster

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.

Member Avatar for DevonMcC++
DevonMcC++ 0 Newbie Poster

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);
Member Avatar for mrnutty
mrnutty 761 Senior Poster

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

Member Avatar for Bench
Bench 212 Posting Pro

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;
}
Member Avatar for arkoenig
arkoenig 340 Practically a Master Poster

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.

NathanOliver commented: Thanks +2
Member Avatar for NathanOliver
NathanOliver 429 Veteran Poster

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview