How would you improve this algorithm? (c string re

Question

Working through some programming interview challenges I found online, I had to write an algorithm to reverse a const char * and return a pointer to a new char *. I think I have it, but to make it work properly I had to do some wonky stuff - basically having to account for the null-terminating character myself. Somehow I feel this is wrong, but I'm stumped, and I was wondering if someone could help me out:

char * reverse(const char * str)
{
  int length = strlen(str);
  char * reversed_string = new char[length+1];

  for(int i = 0; i < length; ++i)
  {
    reversed_string[i] = str[(length-1) - i];
  }
  //need to null terminate the string
  reversed_string[length] = '\0';

  return reversed_string;

}

int main(int argc, char * argv[])
{

  char * rev_str = reverse("Testing");

  cout << "Your string reversed is this: " << rev_str << endl;

  delete rev_str;
  rev_str = 0;

  return 0;
}

Answer 1

this works nicely:

#include <algorithm>
#include <iostream>
#include <cstring>

void reverse_string(char *str) {    
    char *end = str + strlen(str) - 1;
    while (str < end) {
        std::iter_swap(str++, end--);
    }
}

int main() {
    char s[] = "this is a test";
    reverse_string(s);
    std::cout << "[" << s << "]" << std::endl;
}

Answer 2

I had this question once. That's the first answer that comes to mind, but the follow-up is, "now do it without allocating any memory."

int length = strlen(string);
for(int i = 0; i < length/2; i++) {
  char c = string[i];
  string[i] = string[length - i];
  string[length - i] = c;
}

EDIT: Some folks have expressed disdain for not using pointers. This is a tiny bit more readable, though not completely optimal. Others have entered the pointer solution, so I won't repeat it here.

One commenter challenged that it should be doable without a (stack based) holding cell for the swap. The mechanism for doing that is bitwise XOR. Replace the inside of the loop with

string[i] = string[i] ^ string[length - i];
string[length - i] = string[i] ^ string[length - i];
string[i] = string[i] ^ string[length - i];

But in general, modern compilers can optimize out the local variable of a naive swap. For details, See Wikipedia

Answer 3

String reversed in place, no temp variable.

static inline void
byteswap (char *a, char *b)
{
  *a = *a^*b;
  *b = *a^*b;
  *a = *a^*b;
}

void
reverse (char *string)
{
  char *end = string + strlen(string) - 1;

  while (string < end) {
    byteswap(string++, end--);
  }
}

Answer 4

Your code is straight forward and unsurprising. A few things:

1. Use size_t instead of int for your loop index
2. While your compiler is most likely smart enough to figure out that (length -1) is invariant, it's probably not smart enough to figure out that (length-1)-i is best replaced by a different loop variable that is decremented in each pass
3. I'd use pointers instead of array syntax - it will look cleaner to me to have *dst-- = *src++; in the loop.

In other words:

char *dst = reversed_string + length;
*dst-- = '\0';
while (*src) {
   *dst-- = *src++;
}

Answer 5

Uh? No one did it with pointers?

char *reverse(const char *s) {
    size_t n = strlen(s);
    char *dest = new char[n + 1];
    char *d = (dest + n - 1);

    dest[n] = 0;
    while (*s) {
        *d-- = *s++
    }

    return dest;
}

Hopefully years of Java haven't ruined my C ;-)

Edit: replaced all those strlen calls with an extra var. What does strlen return these days? (Thanks plinth).

Answer 6

@Konrad Rudolph: (sorry I don't have the "experience" to post a comment)

I want to point out that the STL supplies a reverse_copy() algorithm, similar to reverse(). You need not introduce a temporary the way you did, just allocate a new char * of the right size.