string reverse in C++

Question

I found this piece of code on the site, it seems the author is long gone, anyway, I'm having hard time understanding the actual swap and how the reverse occurs:

void strrev2(char *str)
{
        if( str == NULL )
                return;

        char *end_ptr = &str[strlen(str) - 1];
        char temp;
        while( end_ptr > str )
        {
                temp = *str;
                *str++ = *end_ptr;
                *end_ptr-- = temp;
        }
}

let's say you feed it word "testing"

First iteration:

*end_ptr = 'g';

temp = 't'
*str = 'g' // is it first assigned and then incremented to point to the next location?
*end_ptr = 't' // is it first assigned and then decremented to point to the previous location?

What happens on the second iteration? I'm having hard time because I thought that on this line:

char *end_ptr = &str[strlen(str) - 1];

end_ptr will only contain address of one letter, so how can *end_ptr work?

Anyway, if someone can explain this to me in some graphical way.. Thanks.

Answer 1

First it swaps the first and the last, at the same time incrementing pointer to the first element so that it points to the second and decrementing pointer to the last, so that it points to last but one. It continues this way as long as the "last" character comes after the "first". When it's not the case it's done.

And no, I'm not good ascii artist, so no graphics for you.

Answer 2

The pointers are incremented and decremented after assignment, so the start pointer runs through the word as the end pointer runs backwards.

in "testing", first iteration exchanges "t" and "g", second iteration exchanges "e" and "n", and so on until the pointers meet at the middle of the word.

Answer 3

str and end_ptr are just pointers to the start and end of the string. Each time round the loop their characters are swapped, and they are each moved one step towards the middle of the string. When they meet (or cross), the loop terminates.

Here's a picture...

1. testing        s is str
   ^     ^        e is end_ptr
   s     e

2. gestint
    ^   ^
    s   e

3. gnitset
      ^
      se

4. done!

(By the way, this is the start of a common interview question at companies that think brain-teasers make good interview questions. The question inevitably continues... so now, how would you use the same principle to reverse the words in a sentence, without reversing the letters in each word?)

Answer 4

Side note: this is a lot easier to do:

#include <algorithm>
void strrev2(char *str)
{
    std::reverse(str, str + strlen(str));
}

Answer 5

I liked Alex's art and I wanted to elaborate a little more, so this is a little more drawn version out of that same explanation that every one else has been posting.

To Start off:

|'t'|'e'|'s'|'t'|'i'|'n'|'g'|'\0'| str  |      |      |
  ^                              | 0x00 |      |      |
 str

Then after the line

char *end_ptr = &str[strlen(str) - 1];

since the strlen(str) returns 7,

end_ptr = &str[6]

So:

|'t'|'e'|'s'|'t'|'i'|'n'|'g'|'\0'| str  | end  | temp |
  ^                       ^      | 0x00 | 0x06 |      |
 str                     end

once it enter the loop it checks to see that end is a bigger address than str, and then assigns the value at the address str is pointing to to temp:

|'t'|'e'|'s'|'t'|'i'|'n'|'g'|'\0'| str  | end  | temp |
  ^                       ^      | 0x00 | 0x06 |  't' |
 str                     end

It then continues by assigning the value at end to the address at str:

|'g'|'e'|'s'|'t'|'i'|'n'|'g'|'\0'| str  | end  | temp |
  ^                       ^      | 0x00 | 0x06 |  't' |
 str                     end

Then advances the pointer str to the next address

|'g'|'e'|'s'|'t'|'i'|'n'|'g'|'\0'| str  | end  | temp |
      ^                   ^      | 0x01 | 0x06 |  't' |
     str                 end

Assigns the value of temp to the address at end:

|'g'|'e'|'s'|'t'|'i'|'n'|'t'|'\0'| str  | end  | temp |
      ^                   ^      | 0x01 | 0x06 |  't' |
     str                 end

Then finally decrements end and loops back to the top of the while statement:

|'g'|'e'|'s'|'t'|'i'|'n'|'t'|'\0'| str  | end  | temp |
      ^               ^          | 0x01 | 0x05 |  't' |
     str             end

etc. etc. etc.