Rectangle 27 0

How do you reverse a string in place in C or C++?


#include <bits/types.h>
#include <stdio.h>

#define SWP(x,y) (x^=y, y^=x, x^=y)

void strrev(char *p)
{
  char *q = p;
  while(q && *q) ++q; /* find eos */
  for(--q; p < q; ++p, --q) SWP(*p, *q);
}

void strrev_utf8(char *p)
{
  char *q = p;
  strrev(p); /* call base case */

  /* Ok, now fix bass-ackwards UTF chars. */
  while(q && *q) ++q; /* find eos */
  while(p < --q)
    switch( (*q & 0xF0) >> 4 ) {
    case 0xF: /* U+010000-U+10FFFF: four bytes. */
      SWP(*(q-0), *(q-3));
      SWP(*(q-1), *(q-2));
      q -= 3;
      break;
    case 0xE: /* U+000800-U+00FFFF: three bytes. */
      SWP(*(q-0), *(q-2));
      q -= 2;
      break;
    case 0xC: /* fall-through */
    case 0xD: /* U+000080-U+0007FF: two bytes. */
      SWP(*(q-0), *(q-1));
      q--;
      break;
    }
}

int main(int argc, char **argv)
{
  do {
    printf("%s ",  argv[argc-1]);
    strrev_utf8(argv[argc-1]);
    printf("%s\n", argv[argc-1]);
  } while(--argc);

  return 0;
}
#include <stdio.h>

void strrev(char *p)
{
  char *q = p;
  while(q && *q) ++q;
  for(--q; p < q; ++p, --q)
    *p = *p ^ *q,
    *q = *p ^ *q,
    *p = *p ^ *q;
}

int main(int argc, char **argv)
{
  do {
    printf("%s ",  argv[argc-1]);
    strrev(argv[argc-1]);
    printf("%s\n", argv[argc-1]);
  } while(--argc);

  return 0;
}
$ ./strrev Rksmrgs 

 

Rksmrgs sgrmskR

./strrev verrts/.
  • Also, UTF-8 over 0x10000 is untested (as I don't seem to have any font for it, nor the patience to use a hexeditor)
  • Why, yes, if the input is borked, this will cheerfully swap outside the place.

(This is XOR-swap thing. Take care to note that you must avoid swapping with self, because a^a==0.)

1. XOR-swap can swap arbitrary size elements without allocating any intermediate storage. (Admittedly not relevant.) 2. I like it.

@Bill, that's not what the common definition of in-place means. In-place algorithms may use additional memory. However, the amount of this additional memory must not depend on the input i.e. it must be constant. Therefore, swapping of values using additional storage is completely in-place.

There's no good reason to use XOR swap outside of an obfuscated code competition.

XOR swapping is slower than swapping via register on modern out-of-order processors.

You think "in-place" means "no extra memory", not even O(1) memory for temporaries? What about the space on the stack for str and the return address?

Note
Rectangle 27 0

How do you reverse a string in place in C or C++?


#include <stddef.h>
#include <string.h>

/* PRE: str must be either NULL or a pointer to a 
 * (possibly empty) null-terminated string. */
void strrev(char *str) {
  char temp, *end_ptr;

  /* If str is NULL or empty, do nothing */
  if( str == NULL || !(*str) )
    return;

  end_ptr = str + strlen(str) - 1;

  /* Swap the chars */
  while( end_ptr > str ) {
    temp = *str;
    *str = *end_ptr;
    *end_ptr = temp;
    str++;
    end_ptr--;
  }
}

Aside from a potential performance improvement with maybe int temp, this solution looks best. +1

Fair enough. I was trying (and failing) to avoid the off-by-one error in @uvote's answer.

I need stddef, but not stdio.

Non-evil C, assuming the common case where the string is a null-terminated char array:

Rather than using a while loop to find the end pointer, can't you use something like end_ptr = str + strlen (str); I know that will do practically the same thing, but I find it clearer.

You don't need the stddef.h and string.h headers.

Note
Rectangle 27 0

How do you reverse a string in place in C or C++?


Reverse a string in place (visualization):

Note
Rectangle 27 0

How do you reverse a string in place in C or C++?


In any of these variable-width encoding schemes, the simple algorithms posted here (evil, non-evil or otherwise) would not work correctly at all! In fact, they could even cause the string to become illegible or even an illegal string in that encoding scheme. See Juan Pablo Califano's answer for some good examples.

In the interest of completeness, it should be pointed out that there are representations of strings on various platforms in which the number of bytes per character varies depending on the character. Old-school programmers would refer to this as DBCS (Double Byte Character Set). Modern programmers more commonly encounter this in UTF-8 (as well as UTF-16 and others). There are other such encodings as well.

std::reverse does NOT take this into account. It reverses value_type's. In the std::string case, it reverses char's. Not characters.

std::reverse() potentially would still work in this case, as long as your platform's implementation of the Standard C++ Library (in particular, string iterators) properly took this into account.

Note
Rectangle 27 0

How do you reverse a string in place in C or C++?


void strrev(char *str)
{
    if (str == NULL)
        return;
    std::reverse(str, str + strlen(str));
}

Note that the beauty of std::reverse is that it works with char * strings and std::wstrings just as well as std::strings

Note
Rectangle 27 0

How do you reverse a string in place in C or C++?


The first byte will be treated as a NUL-terminator. No reversing will take place.

The result is gibberish and an illegal UTF-8 sequence

The second byte will be treated as a NUL-terminator. The result will be 0x61, 0x00, a string containing the 'a' character.

@Eclipse If it reverses a surrogate pair, the result won't be correct anymore. Unicode is not actually a fixed-width charset

I'm not very familiar with C++, but my guess is that any respectable standard library function dealing with strings will be able to handle different encodings, so I agree with you. By "these algorithms", I meant the ad-hoc reverse functions posted here.

If you're looking for reversing NULL terminated buffers, most solutions posted here are OK. But, as Tim Farley already pointed out, these algorithms will work only if it's valid to assume that a string is semantically an array of bytes (i.e. single-byte strings), which is a wrong assumption, I think.

Take for example, the string "ao" (year in Spanish).

The Unicode code points are 0x61, 0xf1, 0x6f.

Unfortunately, there's no such thing as "respectable function dealing with strings" in standard C++.

std::reverse will work for two-byte unicode types, as long as you're using wstring.

Note
Rectangle 27 0

How do you reverse a string in place in C or C++?


#include <algorithm>
std::reverse(str.begin(), str.end());

@fredsbend, the "ridiculously long" version of the selected answer handles a case which this simple answer doesn't - UTF-8 input. It shows the importance of fully specifying the problem. Besides the question was about code that would work in C as well.

In C++ a string is represented by the string class. He didn't asked for "char star" or a "char brackets". Stay classy, C.

This answer does handle the case if you use a UTF-8 aware string class (or possibly a utf-8 character class with std::basic_string). Besides, the question said "C or C++", not "C and C++". C++ only is "C or C++".

Note
Rectangle 27 0

How do you reverse a string in place in C or C++?


Standard Template Library is a pre-standard term. The C++ standard does not mention it, and former STL components are in the C++ Standard Library.

You use std::reverse algorithm from the C++ Standard Library.

right. i always wonder why so many people still call it "STL" even though it just serves to confuse the matter. would be nicer if more people are like you and call it just "C++ Standard Library" or STL and say "STandard Library" :)

Note
Rectangle 27 0

How do you reverse a string in place in C or C++?


#include <string.h>

void reverse(char s[])
{
    int length = strlen(s) ;
    int c, i, j;

    for (i = 0, j = length - 1; i < j; i++, j--)
    {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

@Eric This does not run in O(log(n)) time. It runs in O(n) if you're referring to the number of character swaps the code performs, for n of string length, then n swaps are performed. If you we're talking about the amount of loops performed then its still O(n) - albeit O(n/2) but you drop the constants in Big O notation.

Its important to note in this example that the string s must be declared in an array form. In other words, char s[] = "this is ok" rather than char *s="cannot do this" because the latter results in a string constant which cannot be modified

Shouldn't variable "c" be a char instead of an int?

Tested on my iphone this is slower than using raw pointer addresses by about 15%

With apologizes to "The Godfather" .... "Leave the guns, bring the K&R". As a C bigot, I'd use pointers, as they're simpler and more straight-forward for this problem, but the code would be less portable to C#, Java, etc.

Note