HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMajor

Close to the metal C++ Palindrome Program

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
closetheprogrammetalpalindrome

Problem

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  // cout
#include   // printf
#include 

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.

Solution

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.

Code Snippets

for(int i=0; num_to_parse; i++)
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;
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;
printf("%s", is_palidrome(inputString)?"This is a palindrome.":"Not a palindrome.");
if (is_palindrome(inputString)) {
  puts("This is a palindrome.");
} else {
  puts("Not a palindrome.");
}

Context

StackExchange Code Review Q#161501, answer score: 41

Revisions (0)

No revisions yet.