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.

I've added a C tag. Although technically this is C++ code, reversing a string in C++ is a one-liner. — avakar
– avakar, Commented Sep 22, 2009 at 17:22

alex tingle · Accepted Answer · 2009-09-22 17:27:15Z

23

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?)

edited Sep 22, 2009 at 17:27

answered Sep 22, 2009 at 17:19

alex tingle

7,3013 gold badges28 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Chezz · Accepted Answer · 2009-09-22 18:52:01Z

8

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.

edited Sep 22, 2009 at 18:52

answered Sep 22, 2009 at 18:45

Chezz

1231 silver badge7 bronze badges

5 Comments

Nathan Fellman Over a year ago

It looks like you forgot to update the value of temp in your example

Michael Krelin - hacker Over a year ago

OMG, it evolves into a nice ascii-art contest!

Michael Krelin - hacker Over a year ago

So why is it takes so long to update temp? Is algorithm that bad? ;-)

Michael Krelin - hacker Over a year ago

Chezz, you sounds like enterprise programmer — a nice picture and no sense. 55 minutes and pictures aren't edited into shape ;-)

Chezz Over a year ago

Am I missing something? It's only to the bottom of the first itteration... Man I really hope I am not doing that "blind to glaring retartion stare" thing I do when I code at 2 am with no more caffine in sight. :|

Emilio M Bumachar · Accepted Answer · 2009-09-22 17:19:20Z

4

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.

answered Sep 22, 2009 at 17:19

Emilio M Bumachar

2,6134 gold badges27 silver badges31 bronze badges

Comments

Michael Krelin - hacker · Accepted Answer · 2009-09-22 17:16:30Z

2

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.

answered Sep 22, 2009 at 17:16

Michael Krelin - hacker

144k25 gold badges200 silver badges177 bronze badges

Comments

rlbond · Accepted Answer · 2009-09-22 18:48:15Z

2

Side note: this is a lot easier to do:

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

edited Sep 22, 2009 at 18:48

answered Sep 22, 2009 at 17:20

rlbond

68.4k56 gold badges182 silver badges233 bronze badges

5 Comments

Michael Krelin - hacker Over a year ago

-1 for not getting the point, not paying attention to the c tag and generally suggesting to quit smoking when asked how to get to the subway station.

Michael Krelin - hacker Over a year ago

-1 for myself for not knowing that c tag has been added later. Sorry man, but still -1 for you as well.

rlbond Over a year ago

Wow hacker. Nice job admitting that you're wrong and not doing anything to apologize.

avakar Over a year ago

rlbond, I agree with hacker, you're not answering the question. Your answer could have easily been a comment. Not to mention your code is incorrect (drop "- 1").

Michael Krelin - hacker Over a year ago

rlbond, I haven't done anything to apologize, I actually did apologize, that' what "Sorry man" stands for. Like I said, I am sorry and I would reverse my downvote if it's been the primary reason for downovoting.

Collectives™ on Stack Overflow

string reverse in C++

5 Answers 5

Comments

5 Comments

Comments

Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

5 Comments

Comments

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related