12
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Yep. Try a for loop. Learn how to use references. Consider accidental mutation. \$\endgroup\$ – Martin York Nov 20 '13 at 17:08
  • 1
    \$\begingroup\$ 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"? \$\endgroup\$ – Michael Urman Nov 20 '13 at 22:13
  • 3
    \$\begingroup\$ "A man a plan a canal Panama" also considered a palindrome. \$\endgroup\$ – Martin York Nov 22 '13 at 17:20
  • \$\begingroup\$ "A man a plan a canal Panama" that's not a palindrome... \$\endgroup\$ – Max Nov 28 '13 at 12:04
  • \$\begingroup\$ @Max Yes it is. meta.stackoverflow.com/users/155556/amanap-lanac-a-nalp-a-nam-a \$\endgroup\$ – Mathieu Guindon Nov 29 '13 at 1:52
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Morwenn Nov 20 '13 at 18:58
  • \$\begingroup\$ 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! \$\endgroup\$ – Michael Urman Nov 20 '13 at 19:14
8
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ +1 looks good. Just one nitpick: use std::string::size_type instead of std::size_t. \$\endgroup\$ – Jamal Nov 20 '13 at 17:31
  • 2
    \$\begingroup\$ Looks like you want --j instead of ++j. \$\endgroup\$ – Michael Urman Nov 20 '13 at 18:22
  • \$\begingroup\$ +1 for it's proximity to the original version and for catching the empty case ! \$\endgroup\$ – Wolf Nov 26 '13 at 14:40
  • \$\begingroup\$ ...BTW: isn't an empty string a palindrome? \$\endgroup\$ – Wolf Nov 26 '13 at 14:41
  • \$\begingroup\$ 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. \$\endgroup\$ – Wolf Nov 26 '13 at 18:47
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.