Checking for a palindrome

Question

What I'm basically wondering is if there's anything that is possible to improve in this C++ code:

#include <cstddef>
#include <string>
bool is_palindromic(std::string s)
{
 std::size_t i = 0;
 std::size_t j = s.length() - 1;
 while (i < j) {
 if (s[i++] != s[j--]) {
 return false;
 }
 }
 return true;
}

• Loki Astari: Yep. Try a for loop. Learn how to use references. Consider accidental mutation.
• Michael Urman: Stepping outside the C++ code a bit, make sure you have a clear definition of what qualifies as a palindrome. Are there things (such as spaces or punctuation or letter case) that should be ignored: "Sir, I’m Iris." or just "SIRIMIRIS"?
• Loki Astari: "A man a plan a canal Panama" also considered a palindrome.
• Max: "A man a plan a canal Panama" that's not a palindrome...
• Mathieu Guindon: @Max Yes it is. meta.stackoverflow.com/users/155556/amanap-lanac-a-nalp-a-nam-a

Answer 1

I wanted to offer a different angle of better. This code could be more generic. Why is it tied to exactly std::string - what if I need to check palindromic nature of std::wstring or the contents of a std::vector<T>? How about std::list<T> or std::map<T> (if palindromic can even mean anything on a std::map)? Here's how you can handle all of those with a single function:

template <typename Sequence>
bool is_palindromic(const Sequence& seq)
{
 auto count = seq.size() / 2; // rounded down is fine, as a middle element matches itself
 auto i = seq.begin(); // prefer std::begin(seq) in C++14
 auto j = seq.rbegin(); // prefer std::rbegin(seq) in C++14
 for (Sequence::size_type c = 0; c < count; ++c, ++i, ++j)
 {
 if (*i != *j)
 return false;
 }
 return true; // considers sequences without mismatched characters to be palindromes
}

Note that I incorporated the other comments I agree with - in particular passing by const reference, and using the sequence's size_type. I'm not sure how to best support arrays, however; while std::[r]begin will handle arrays, I don't believe arrays have a .size() or ::size_type to use. I guess that means they need their own overload, or at least some overloaded helpers.

• Morwenn: Use std::distance(std::begin(seq), std::end(seq)) if you want to have a generic way to handle the size. With it, you can handle arrays. I don't know whether it is specialized for random-access iterators; if not, your code may be slower.
• Michael Urman: Ah, std::distance sounds great for random access and thus supporting arrays. However it's linear on non-random access, so would be slower on std::list (though no worse algorithmically). Thanks for the idea at least!

Answer 2

First of all, you should pass the std::string by const reference and not by value, therefore, replace std::string s by const std::string& s, otherwise you will make a whole copy of the string everytime you invoke the function.

Also, you program may crash if the std::string is empty since you're doing std::size_t j = s.length() - 1;. If s.length() == 0, j will probably be a big number and you will end up with a segfault due to an out of range index.

As suggested by Loki in the comments, you could also use a for loop instead of a while loop in order for your code to look cleaner.

Yet another suggestion by Jamal: using std::string::size_type instead of std::size_t (and removing #include <cstddef> by the way) would be more idiomatic. The type returned by std::string::length is not required to be std::size_t but std::string::size_type.

Therefore, I would rewrite it as:

bool is_palindromic(const std::string& s)
{
 if (s.empty())
 {
 // You can return true if you think that
 // an empty string is a palyndrome
 return false;
 }
 for (std::string::size_type i=0, j=s.length()-1
 ; i < j ; ++i, --j)
 {
 if (s[i] != s[j]) {
 return false;
 }
 }
 return true;
}

• Jamal: +1 looks good. Just one nitpick: use std::string::size_type instead of std::size_t.
• Michael Urman: Looks like you want --j instead of ++j.
• Wolf: +1 for it's proximity to the original version and for catching the empty case !
• Wolf: ...BTW: isn't an empty string a palindrome?
• Wolf: I'd agree, if there was something special referred in the question, maybe a definition like this. In lack of such, I prefer the idea of empty strings as palindromes.

Answer 3

I just wanted to chime in with the "lazy" (if not performant) way of doing this, using reverse iterators:

bool is_palindrome(const std::string& s)
{
 return s == std::string(s.rbegin(), s.rend());
}

This is very simple and very readable. You could expand this to do things like remove punctuation if you want, but it gets a bit trickier (although it's still short):

// Note that the pass by value is intentional here, so we don't modify
// the original string when using std::remove_if
bool is_palindrome(std::string s)
{
 auto it = std::remove_if(s.begin(), s.end(), [](char c) { return !std::isalpha(c); });
 return std::equal(s.begin(), it, std::reverse_iterator<std::string::iterator>(it));
}

This can likewise be made into a template that will work with any sequence with very little effort.

Answer 4

Searching for something as symmetrical as palindromes themselves, I came to this somewhat picturesque solution, that doesn't handle the empty string in a specific way, but as palindromic:

#include <string>
bool is_palindromic(const std::string& s)
{
 std::string::const_iterator start = s.begin();
 std::string::const_iterator end = s.end();
 while (start < end) {
 if (*(start++) != *(--end)) {
 return false;
 }
 }
 return true;
}

Its major drawback is the redundant check for self-equality of the central char.