Palindrome Tester

3

By Nathan Oliver on May 11th, 2010 8:11 am

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

2 Years Ago

0

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

firstPerson

Senior Poster

3,923 posts since Dec 2008

Reputation Points: 841

Solved Threads: 608

2 Years Ago

0

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

NathanOliver

Veteran Poster

1,084 posts since Apr 2009

Reputation Points: 215

Solved Threads: 189

2 Years Ago

0

Why have you hard coded the numbers 5 and 4?

iamthwee

Posting Expert

5,950 posts since Aug 2005

Reputation Points: 1,543

Solved Threads: 439

2 Years Ago

0

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

NathanOliver

Veteran Poster

1,084 posts since Apr 2009

Reputation Points: 215

Solved Threads: 189

2 Years Ago

Show Comments

1

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.

Nick Evan

Not a Llama

Moderator

10,112 posts since Oct 2006

Reputation Points: 4,142

Solved Threads: 403

2 Years Ago

0

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

NathanOliver

Veteran Poster

1,084 posts since Apr 2009

Reputation Points: 215

Solved Threads: 189

2 Years Ago

0

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.

firstPerson

Senior Poster

3,923 posts since Dec 2008

Reputation Points: 841

Solved Threads: 608

1 Year Ago

0

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

DevonMcC++

Newbie Poster

16 posts since Feb 2008

Reputation Points: 10

Solved Threads: 1

1 Year Ago

0

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

firstPerson

Senior Poster

3,923 posts since Dec 2008

Reputation Points: 841

Solved Threads: 608

1 Year Ago

0

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

Bench

Posting Pro

577 posts since Feb 2006

Reputation Points: 307

Solved Threads: 63

1 Year Ago

Show Comments

1

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.

arkoenig

Master Poster

703 posts since Jun 2010

Reputation Points: 359

Solved Threads: 109

1 Year Ago

0

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

NathanOliver

Veteran Poster

1,084 posts since Apr 2009

Reputation Points: 215