Close to the metal C++ Palindrome Program

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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.