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

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.

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

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.