26
\$\begingroup\$

I am attempting to reinvent the wheel by writing my own palindrome checking program in C++, using only basic loops and mathematical operations. I have arrived at a solution, but was wondering if it's the best solution and if it could be improved. I'm doing this primarily as a learning exercise. My code:

#include <iostream> // cout
#include <stdio.h>  // printf
#include <string>

using namespace std;

bool is_palidrome(string inputString) {
  int num_to_parse = inputString.size();

  /* immediately return on single letter string as all single letter strings are palindromes -- saves CPU time as programme does not need to enter the loop */
  if(num_to_parse == 1) {
      return true;
  }

  for(int i=0; num_to_parse; i++) {
      int point_end = num_to_parse - i - 1;
    if(inputString[i] == inputString[point_end]) {
      continue;
    } else if (i == num_to_parse) {
      return true;
    } else {
      return false;
    }
}}


int main() {
    // Change the value of inputString to test different palindromes
    string inputString = "caabaac";
    printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome."); // ternary: test condition ? return this if true : return this if false
    return 0;
}

I think at the moment I'm doing about 2x the number of loops I need to do, and so wasting CPU time. Also, there may be further optimizations. Any help really appreciated as I really want to understand this stuff properly and contribute to code-bases, rather than just doing everything with other people's higher-level code.

\$\endgroup\$
  • 3
    \$\begingroup\$ I realize this is a small program, but you should still check this out; stackoverflow.com/questions/1452721/… \$\endgroup\$ – Nilzone- Apr 22 '17 at 14:22
  • 27
    \$\begingroup\$ what exactly is close to the metal here? \$\endgroup\$ – Sarge Borsch Apr 23 '17 at 11:13
  • 2
    \$\begingroup\$ When you are up to a task you are supposed to analyse what you have at hand before writing the code. A palindrome is a word that is mirrored across its middle, who could even think about checking all the chars in it? Remove the for, declare two indexes (two int), set one to 0, the other one to the end of the string, and while-loop 'till the first index is greater or equal than the second one (remember to ++ and -- the indexes inside the loop, obviously) \$\endgroup\$ – motoDrizzt Apr 23 '17 at 12:43
  • \$\begingroup\$ What exactly is your definition of palindrome? Many traditional english palindromes will not be detected by your solution. For example: - Madam I'm Adam - Able was I ere I saw Elba - A man, a plan, a canal, Panama! Does your solution consider languages other than English? - Japanese: かるいきびんなこねこなんびきいるか - Chinese: 上海自来水来自海上 - Hindi: नवजीवन Does it consider accent folding? - Spanish: Adán no cede con nada. \$\endgroup\$ – Chas Apr 24 '17 at 17:39
  • 1
    \$\begingroup\$ If you're going to say "close to the metal", make sure your code is in assembly, not a high-level language. \$\endgroup\$ – code_dredd Apr 25 '17 at 1:44
42
\$\begingroup\$
for(int i=0; num_to_parse; i++)

wut

Why is num_to_parse your condition? Then you have if (i == num_to_parse) in there, too? That's odd. I'd rewrite this as:

for(int i=0; i < num_to_parse; i++) {
  int point_end = num_to_parse - i - 1;
  if(inputString[i] == inputString[point_end]) {
    continue;
  } else {
    return false;
  }
}
return true;

If you want to simplify that even further, you can just do this:

for(int i=0; i <= num_to_parse; i++) {
  int point_end = num_to_parse - i - 1;
  if(inputString[i] != inputString[point_end]) {

    return false;
  }
}
return true;

Take note of the different condition. There are a couple of other simplifying improvements, but they're mentioned in another answer.


While I was writing that, I realized that your indentation is... odd, to say the least. Please don't use things like }} in code; while there are a few rare cases where it might be OK (nested namespaces that, as is typical, you didn't indent), none of them apply here.


using namespace std is a bad idea. Please don't do it.


printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome.");

This is just... weird. I mean, first of all, you don't have a trailing newline, so it might never output anything at all. In my C IDE, for example, it would, but on my Bash console, it'd definitely look odd (This is a palindrome.q@my-hostname ~>), if it prints at all. Even ignoring that inconsistency... why do it like that? The ternary just makes it more complicated than it has to be.

If you insist on using C functions (more on that later), do this:

if (is_palindrome(inputString)) {
  puts("This is a palindrome.");
} else {
  puts("Not a palindrome.");
}

The C++ equivalent should be fairly straightforward; replace the puts(...) with std::cout << ... << "\n";, or std::endl in place of "\n" if you want to be paranoid about flushing every single line instead of just ensuring that it's flushed in a few key places (which is what I do in performance-critical stuff, because writing to the console is slow, and until you tell them to, most C++ standard libraries will avoid doing it for as long as is reasonable)


Now to talk about that "using C functions" thing. Why are you doing it at all? You have all of C++'s power to bring to bear, but you don't. If you want to write this in C, write it in C -- it'd only be changing, like four lines. Maybe less. Don't use just a tiny part of C++. Or, alternatively, just write C.


With regards to your original concern about speed, you're doing this in O(n) (as far as I can tell), which is the absolute lower limit. You're still iterating over every character, though, so it's not as fast as it could get -- you only need to iterate over half.


Finally, what do you mean by "close to the metal"? This is just C with a tiny sprinkling of C++, which are both high-level languages. Not as high-level as, say, Python, but the definition of a high-level language is that it's abstracted from any one particular machine, which C and C++ are. There's nothing close to the metal here. That would be machine code, or maybe Assembly.

\$\endgroup\$
  • \$\begingroup\$ Wow, it's strange it works in any coding environment with that error in there! No-wonder I was seeing divergent behaviour in different environments! \$\endgroup\$ – Angular4 Kiddie Apr 22 '17 at 14:15
  • \$\begingroup\$ ...In the time it took me to finish my review after I forgot that Tab moves to the next thing, rather than indenting, I got 2 upvotes and an accept. Thanks? :D \$\endgroup\$ – Nic Hartley Apr 22 '17 at 14:16
  • \$\begingroup\$ @RailsKiddie That's not the only one -- see my edit. There's one other thing that'd make it behave inconsistently, at least that I saw. \$\endgroup\$ – Nic Hartley Apr 22 '17 at 14:16
  • \$\begingroup\$ I'll have a proper read through. This is all really useful. Obviously if I'd known the code wouldn't work in all environments when posting I'd have posted in SO, not here, but as it is I'm very pleased with the feedback and this is a really useful response. \$\endgroup\$ – Angular4 Kiddie Apr 22 '17 at 14:20
  • 1
    \$\begingroup\$ @CodyGray OK, fair enough. I was thinking in terms of C, because this program is basically just C, and C doesn't have (user-specifiable) namespaces. \$\endgroup\$ – Nic Hartley Apr 22 '17 at 17:42
29
\$\begingroup\$

First thing: this doesn't work


#include <iostream> // cout
#include <stdio.h>  // printf
#include <string>

You included <iostream>, but didn't use it in favour of printf. If we actually use <iostream> as is the C++ way, then <stdio.h> isn't needed.


using namespace std;

For small examples and programs, this isn't much of a issue; but in bigger programs, using the std namespace at the top level of a file pollutes the global namespace, which is especially terrible if used in a header file.


    int num_to_parse = inputString.size();

auto should be used here instead of int, for correctness and in case the input string is ever really large and overflows the maximum limit of int.


    if (num_to_parse == 1) {
        return true;
    }

This can be removed entirely, and dealt with in a rewritten for loop.


    for (int i = 0; num_to_parse; i++) {
        int point_end = num_to_parse - i - 1;
        if (inputString[i] == inputString[point_end]) {
            continue;
        } else if (i == num_to_parse) {
            return true;
        } else {
            return false;
        }
    }

The for loop's condition is never zero (it can't be once the suggestions are applied), this is just an infinite loop with a counter attached. The condition should be i < num_to_parse. That isn't what for loops are for. It just messes up everything (like your if statement does, it doesn't make sense). I'd rewrite the end of that function as (EDIT: improvements from comments):

    // (num_to_parse/2) means that i will reach the middle of the string, and no further.
    auto middleOfString = num_to_parse / 2;
    for (decltype(num_to_parse) i = 0; i < middleOfString; ++i) {
        if (inputString[i] != inputString[num_to_parse-i-1]) {
            return false;
        }
    }

    return true;
}

Much more simple, and it works :)


int main() {
    // Change the value of inputString to test different palindromes
    string inputString = "caabaac";
    printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome."); // ternary: test condition ? return this if true : return this if false
    return 0;
}

The printf can be replaced with the C++ goodness and the ternary statement with a more readable (in this case) if/else statement.


With all this applied, the final code looks like this:

#include <iostream>
#include <string>

bool is_palidrome(std::string inputString) {
    auto num_to_parse = inputString.size();
    auto middleOfString = num_to_parse / 2;

    for (decltype(num_to_parse) i = 0; i < middleOfString; ++i) {
        if (inputString[i] != inputString[num_to_parse-i-1]) {
            return false;
        }
    }

    return true;
}


int main() {
    // Change the value of inputString to test different palindromes
    std::string inputString = "caabaac";

    if (is_palidrome(inputString)) {
        std::cout << "This is a palindrome." << std::endl;
    } else {
        std::cout << "Not a palindrome." << std::endl;
    }

    return 0;
}
\$\endgroup\$
  • 6
    \$\begingroup\$ Nice first answer! I'm gonna pretend you stole all the things we both noticed from me, even though that's probably not true at all. :) \$\endgroup\$ – Nic Hartley Apr 22 '17 at 14:35
  • 2
    \$\begingroup\$ Thank you, thank you :) The truth is, I started writing this before you submitted it, so we both did these things ourselves :P But then the iffy if statement struck me, so I tested it and had to rewrite because OP's code didn't work. \$\endgroup\$ – user136614 Apr 22 '17 at 14:37
  • 2
    \$\begingroup\$ @InternetAussie Yeah, it just happened in the coding environment I was using it did work, hence posting here, but I've since found it doesn't work in most others. \$\endgroup\$ – Angular4 Kiddie Apr 22 '17 at 14:40
  • 4
    \$\begingroup\$ I'm curious, why didn't you rewrite it using iterators rather than indexing? leftChar = inputString.begin() rightChar = inputString.end() while (leftchar != rightChar) { ... } \$\endgroup\$ – pacmaninbw Apr 22 '17 at 15:19
  • 4
    \$\begingroup\$ @pacmaninbw A few reasons: (1) More people are familiar and comfortable with indices, including myself. (2) There's not much benefit to using iterators. (3) If the string has an even length, the iterators will "cross over" and iterate over the entire string, rather than only half. (4) I have to remember to decrement the end iterator before starting, because it points to the element after the end. \$\endgroup\$ – user136614 Apr 22 '17 at 15:33
16
\$\begingroup\$

Ignoring issues of correctness and some of the other things that the other answers have gone into detail on, and instead focusing on simple program transformations (transforming the program into an equivalent program):

It is worth pointing out that whenever you have

if (c) {
  return true;
} else {
  return false;
}

you can just replace that with

return c;

Also, the continue; is unnecessary since there is nothing outside of those ifs. You could make that if body empty (if you wanted to keep that structure). This would make it (note: I would not recommend actually using code with an empty if body, this is just a step in the larger transformation I'm suggesting):

if (inputString[i] == inputString[point_end]) {
} else {
  return i == num_to_parse;
}

From there, you could just change the loop to (fixing the conditional a bit, to what I suspect your intent was)

for (int i=0; i<num_to_parse; i++) {
  if (inputString[i] != inputString[point_end]) {
    return i == num_to_parse;
  }
}

This reveals an unnecessary computation, now the conditional in the return can never be true, because the loop will end before i == num_to_parse. Now this can be changed to:

for (int i=0; i<num_to_parse; i++) {
  if (inputString[i] != inputString[point_end]) {
    return false;
  }
}

Again, this won't fix the issues of correctness since, other than my changing the conditional, none of the transformations changed the meaning of the program (as is usually the intent of program transformation). This was, however, addressed in the other answers.

This might better illuminate problems with correctness though, now that the code is simplified.

Also, on a somewhat unrelated subject: I'm not sure that I would describe this as "close to the metal." It definitely requires an operating system and it uses high-level constructs like std::string. This is not to say that it is bad, but I would not describe it as "close to the metal."

\$\endgroup\$
  • 3
    \$\begingroup\$ The only thing I don't agree with is the suggestion of eliding continue in favour of an empty body. continue is nice and explicit, an empty body looks like someone accidentally deleted something. I get that it's just a single step in a bigger transformation, but it would be good to make that clearer in case someone gets the wrong end of the stick and starts swapping their continues for empty statements. \$\endgroup\$ – Pharap Apr 23 '17 at 0:37
  • 2
    \$\begingroup\$ @Pharap Good point! I added a note about that. \$\endgroup\$ – David Apr 23 '17 at 0:42
13
\$\begingroup\$

All other factors being equal, the best solution to a problem is the one that's easiest for someone else to understand. You mention that you don't want to use anything but "basic loops and mathematical operations," but code that is easiest to understand usually does not contain raw, explicit loops. Therefore I suggest the best solution is simply:

bool is_palindrome = std::equal(in.begin(), in.end(), in.rbegin());

Having a healthy understanding of iterators is essential to writing concise algorithms using the standard library, so you owe it to yourself to make sure you're comfortable with them. std::equal compares the elements of two ranges and returns true if the first element of each is equal, the second element of each is equal, etc. until the end is reached. The rbegin() and rend() functions of standard-library containers return reverse iterators over the container. That is, iterators which traverse the container from the last element to the first instead of first to last. So essentially what we're doing is checking if a reversed view of the string is equal to the string itself.

Of course, this does roughly twice as much work as is necessary, reading each character twice. Unless you have extremely long strings, this is unlikely to matter at all, but if you want to reduce that linear-time coefficient in half anyway, you can do so without losing much readability:

bool is_palindrome = std::equal(in.begin(), in.begin() + (in.size() / 2), in.rbegin());

All the edge cases here just do the right thing, but I'll go over them anyway, just for laughs and kicks.

In the case of an empty string, in.begin() == in.end(), and std::equal returns true for empty ranges, so it is correctly considered a palindrome. In the optimized version, in.begin() + 0 == in.begin() so we get the same thing.

In the case of a single character input, the first version compares it with itself, and (surprise!) finds that it's equal. In the optimized version in.size() / 2 becomes 1 / 2, which when doing integer division, ends up as 0, so we're back to comparing an empty range, and it's considered a palindrome.

In the case of an input with odd length, the first version compares the character in the middle with itself, which is unnecessary but doesn't change the result. In the optimized version, again n / 2 truncates towards 0, so the middle character is ignored, and that's okay.

Since we know that the length counting from the beginning of the string is always going to be equal to the length if we start counting from the end of the string, we never need to worry about checking sizes explicitly or using the std::equal overload that takes an end iterator for the second range.

Finally, with a few modifications, you can make this algorithm truly generic, so that it will work on not only std::string, but also std::wstring, char[N] (though not string literals due to the null termination), std::vector<int>, etc.

template <typename T>
bool is_palindrome(const T& in) {
    using std::begin;
    using std::end;
    using std::rbegin;

    auto it1 = begin(in);
    auto it2 = it1 + (std::distance(it1, end(in)) / 2);
    return std::equal(it1, it2, rbegin(in));
}
\$\endgroup\$
8
\$\begingroup\$

Your code has a bug in it when you pass in string("") or string(). One other thing I’d like to point out is that your comment about how it saves time to check that num_to_parse == 1 before entering the loop isn’t quite correct. And you should always be wary when you find yourself writing a second check inside your loop that runs continue. There’s a better way.

It’s never necessary to check the middle letter of an odd-length string, because it’s identical to itself. So you can check i < num_to_parse/2 and, when num_to_parse is 1, the program will immediately fall through the loop.

You do, however, need to check that the string size is not zero, or else you will initialize point_end to -1. That makes inputString[point_end] a dangerous bug!

Here’s a fixed version.

bool is_palindrome2(const std::string& s)
{
  if (s.size() > 0) {
    const size_t last = s.size()-1;
    const size_t sentinel = s.size()/2;

    for (size_t i = 0; i < sentinel; ++i )
      if (s[i] != s[last-i])
        return false;
  } // end if
  return true;  
}

Many programmers don’t like using unsigned indices that way; it might be safer to add an assertion that last >= i, just to be absolutely paranoid in case someone mucks up the loop.. In particular, Google would tell you to use signed types such as ptrdiff_t for loop indices and Microsoft to use rsize_t, so that you can catch underflow bugs more easily.

Since one of the commenters asked, why not use iterators, here’s a version that uses iterators. On an architecture without machine-language indirect addressing, this might count as closer to the metal. It’s also almost identical to the optimized code a C programmer would give you, and compiles to something just as fast:

bool is_palindrome1(const std::string& s)
{
  if (s.size() > 0) {
    std::string::const_iterator left = s.begin();
    std::string::const_iterator right = s.end()-1;

    while (left < right) {
      if (*left != *right)
        return false;

      ++left; // Often written: if (*left++ != *right--)
      --right;
    } // end while
  } // end if
  return true;  
}

And a test driver:

#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using std::cout;
using std::endl;
using std::size_t;

int main()
{
  const std::vector<std::string> testcases =
    { "", "a", "aa", "ba", "abccba", "abcdcba", "abdccba" };

  for ( const std::string& s : testcases )
    if ( is_palindrome2(s) && is_palindrome1(s) )
      cout << '\"' << s << "\" is a palindrome." << endl;
    else if ( !is_palindrome2(s) && !is_palindrome1(s) )
      cout << '\"' << s << "\" is not a palindrome." << endl;
    else
      cout << "Bug on input \"" << s << "\"." << endl;

  return EXIT_SUCCESS;  
}
\$\endgroup\$
4
\$\begingroup\$

Note sure about the "best" solution, but here's how I'd do it in C++:

#include <string>
#include <iostream>

using namespace std;

bool is_palindrome(const string &inputString)
{
    for(int i = 0, j = inputString.size() - 1; i < j; i++, j--)
        if (inputString[i] != inputString[j]) return false;
    return true;
}

int main(int argc, char *argv[])
{
    if (argc != 2) cout << "Usage: " << argv[0] << " <string>" << endl;
    else cout << "The string '" << argv[1] << "' is "
                << (is_palindrome(argv[1]) ? "" : "not ")
                << "a palindrome." << endl;
    return 0;
}

But since you mentioned close-to-the-metal, I endeavored to do it in C instead:

#include <stdio.h>
#include <string.h>

int is_palindrome(const char *inputString)
{
    int i, j;

    if (inputString)
        for(i = 0, j = strlen(inputString) - 1; i < j; i++, j--)
            if (inputString[i] != inputString[j]) return 0;
    return 1;
}

int main(int argc, char *argv[])
{
    if (argc != 2) printf("Usage: %s <string>\n", argv[0]);
    else printf("The string '%s' is %sa palindrome.\n",
                argv[1], (is_palindrome(argv[1]) ? "" : "not "));
    return 0;
}

Note that in both cases, the loop conditional in is_palindrome also ensures that the empty string qualifies as a palindrome, without improperly attempting to access a character at index -1.

\$\endgroup\$
  • 1
    \$\begingroup\$ The C version needs a null pointer check. \$\endgroup\$ – Pharap Apr 23 '17 at 0:45
  • 1
    \$\begingroup\$ Good point. Edited. \$\endgroup\$ – Viktor Toth Apr 23 '17 at 1:02
  • 4
    \$\begingroup\$ It isn't a correctness issue, but since this is a code review site, I must say that I would prefer to see more curly braces in your code. Even though I understand how it works, seeing a for loop immediately after an if, without the introduction of any scope, always makes me do I double-take. It also makes maintenance substantially more difficult. \$\endgroup\$ – Cody Gray Apr 23 '17 at 9:29
  • 2
    \$\begingroup\$ That is a good point but I respectfully disagree. Over the decades (I've been writing code since the 1970s) I came to despise excessive curly braces. Beyond being (in my admittedly personal opinion) unnecessary pedantic, they also make the code harder to read, as it is spread out over more real estate, harder to see all at once. Yes, when there is a chance that there will be more code inserted, I use curly braces as well, or when there are too many levels of indentation. But when I judge that they can be omitted, I happily do so. \$\endgroup\$ – Viktor Toth Apr 23 '17 at 13:11
  • 2
    \$\begingroup\$ @isanae FWIW it makes sense to me. if(expression) statement; is logical because it resembles a simple sentence. It's equally logical to ensure that brace pairs are vertically aligned. K&R's sytem of having the start brace at the end of a line and the end brace at the start of a line seems far more backwards by comparison. \$\endgroup\$ – Pharap Apr 25 '17 at 10:56

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.