Another String reversal question

[Michael]

As if we needed another string reversal question.

I have a problem with the following code, that I believe should work.

int StringReverse(char* psz)
{
char *p = psz;
char *q = psz + strlen(psz) - 1;
while (p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
return 1;

}

Thing is, when it gets to the *p = *q line, I get an access violation.

Any ideas why, or what I can do to fix this?

Thanks,

Michael

 

[Karl Heinz Buchegger]

int StringReverse(char* psz)
{
char *p = psz;
char *q = psz + strlen(psz) - 1;
while (p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
return 1;

}

Thing is, when it gets to the *p = *q line, I get an access violation.

A strong indication that either the pointer value is wrong
or you use the function in an invalid way.
What did your debugger say?

 

[Artie Gold]

Michael wrote:




A strong indication that either the pointer value is wrong
or you use the function in an invalid way.
What did your debugger say?

The OP couldn't *possibly* done something like:

char * some_str = "reverse me";
int result = StringReverse(some_str);
...

Ya think? ;-)

--ag

 

[Karl Heinz Buchegger]

The OP couldn't *possibly* done something like:

char * some_str = "reverse me";
int result = StringReverse(some_str);
...

Ya think? ;-)

Yep. Another possibility is that he feeds a bogous C-style string
to this function (one, which eg. has no terminating '\0')

The function has a bug (the subtraction of 1 is faulty), but
as long as he dosn't feed an empty char array to it, it should not crash.

 

[Artie Gold]

Yep. Another possibility is that he feeds a bogous C-style string
to this function (one, which eg. has no terminating '\0')

In which case it would likely die on the call to strlen().

The function has a bug (the subtraction of 1 is faulty), but
as long as he dosn't feed an empty char array to it, it should not crash.

Hmmm. The subtraction of 1 seems right to me.

But, indeed, an empty C-style string (i.e. *psz = '\0') would make the
pointers in the `while' condition incomparable.

Cheers,
--ag

 

[Ben Hutchings]

As if we needed another string reversal question.

I have a problem with the following code, that I believe should work.

int StringReverse(char* psz)
{
char *p = psz;
char *q = psz + strlen(psz) - 1;
while (p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
return 1;

}

Thing is, when it gets to the *p = *q line, I get an access violation.

Any ideas why, or what I can do to fix this?

The code seems reasonable to me, except that it has undefined
behaviour if you give it a zero-length string. I suspect that
you have mistakenly passed a string literal to it. String
literals are arrays of const char, even though they can be
converted to char *. An attempt to modify a string literal
has undefined behaviour.

As for zero-length strings, the problem is that if strlen(psz)
== 0 then the evaluation of q's initialiser has undefined
behaviour. You can avoid this by making q point to the byte
after the one to be swapped:

void StringReverse(char * psz)
{
char * p = psz;
char * q = psz + strlen(psz);
while (q - p >= 2)
{
--q;
char tmp = *p;
*p = *q;
*q = tmp;
++p;
}
}

Anyway, you don't need to write all that yourself; just use
std::reverse:

void StringReverse(char * psz)
{
std::reverse(psz, psz + strlen(psz));
}

 

[Default User]

As if we needed another string reversal question.

I have a problem with the following code, that I believe should work.

int StringReverse(char* psz)
{

Thing is, when it gets to the *p = *q line, I get an access violation.

Any ideas why, or what I can do to fix this?

Show us a complete program. I'll bet you are passing in a string
literal, which should not be modified.




Brian Rodenborn

 

[Hyman Rosen]

As if we needed another string reversal question.
I have a problem with the following code, that I believe should work.
Thing is, when it gets to the *p = *q line, I get an access violation.
Any ideas why, or what I can do to fix this?

As a guess, you are calling it with a literal string.

 

[Francis Glassborow]

As if we needed another string reversal question.

I have a problem with the following code, that I believe should work.

int StringReverse(char* psz)

what is the return value for? It communicates nothing.

{
char *p = psz;
char *q = psz + strlen(psz) - 1;
while (p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
return 1;

}

Thing is, when it gets to the *p = *q line, I get an access violation.

Any ideas why, or what I can do to fix this?

I will leave others to find the problem with your code, instead I will
deal with the problem of using the available tools:

inline void StringReverse(char* psz){
return std::reverse(psz, psz+strlen(psz));
}

should do what you want without making demands debugging re-invented
wheels. Much less typing, provides a method that can be used on all
sequence containers, and has less risk of logic errors.

And here is a complete program:

#include <algorithm>
#include <iostream>
#include <ostream>

inline void StringReverse(char* psz){
return std::reverse(psz, psz+strlen(psz));
}

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

 

[Thomas Hansen]

As if we needed another string reversal question.

All though this is probably school work I'll try to fix it...

I have a problem with the following code, that I believe should work.

int StringReverse(char* psz)

Why do you return int here?

{
char *p = psz;

Why don't you use std::string?

char *q = psz + strlen(psz) - 1;
while (p < q)
{
char tmp = *p;

Why don't you instead use std::swap here?

*p = *q;
*q = tmp;
p++;
q--;

Why don't you use pre incremental operators here?

}
return 1;

Once again, why do you return the integer here?
Return values are either to state some kind of "state" (C-style) or to
return some kind of result (C++-style).
The signature of your function should rather have been:
std::string StringReverse( const std::string & input )
Or at least "void StringReverse( char * psz )"

}

Thing is, when it gets to the *p = *q line, I get an access violation.

No idea why you get this, but I have some theories...
Se further down...

Any ideas why, or what I can do to fix this?

This is how I would have done it:

std::string StringReverse( const std::string & input )
{
std::string retVal;
for( std::string::const_iterator idx = input.end();
idx != input.begin();
--idx )
{
retVal.push_back( *idx );
}
return retVal;
}

....or maybe even better...:
template<class T>
std::basic_string<T> StringReverse2( const std::basic_string<T>
& input )
{
typedef std::basic_string<T> myString;
myString retVal;
for( myString::const_iterator idx = input.end()-1;
idx != input.begin();
--idx )
{
retVal.push_back( *idx );
}
retVal.push_back( *input.begin() );
return retVal;
}

....or the _completely_ generic way...:
template<class T>
T StringReverse2( typename T::const_iterator begin,
typename T::const_iterator end )
{
--end;
T retVal;
while( end != begin )
{
retVal.push_back( *end );
--end;
}
retVal.push_back( *end );
return retVal;
}

The last one works for both std::string, std::vector and std::list...!
But you need to explicitly define in the calling of it which class you
wish to use, e.g.:
"std::string x = StringReverse<std::string>( or.begin(), or.end() );"

If you are persistant on using c-strings (maybe you're a game
programmer) you can allways do it like this, but I would have choosen
ANY of the above solutions before I did it like this:

void StringReverse( char * input )
{
char * begin = input;
char * end = input+(strlen(input)-1);
while( begin < end )
{
char tmp = *end;
*end = *begin;
*begin = tmp;
++begin, --end;
}
}

Why your solution doesn't work I wouldn't know, but I tried it in
Visual Studio and I added up a "char * tmp = "Thomas Hansen";" line
and when I tried to reverse that line I got an "access violation".
This is probably since Visual Studio define that memory as "read only"
since it's statically linked into the process image...
Don't know if this is a bug or not....?
Why can't we do:

char * tmp = "Thomas Hansen";
StringReverse( tmp );

Anybody?!?
Suggestions?!?
Is it illegal?!?

Thanks,

Michael

 

[Karl Heinz Buchegger]

In which case it would likely die on the call to strlen().

Ah. right. That would not explain the access violation.

Hmmm. The subtraction of 1 seems right to me.

strlen returns the length without the terminating '\0'.
If he subtracts 1, then he will swap the first character
with the one-before-last character. If the goal
is to revert the string then I call this behaviour a bug.

But, indeed, an empty C-style string (i.e. *psz = '\0') would make the
pointers in the `while' condition incomparable.

The most plausible explanation is: He feed a string literal to this
function. That's why I asked for an example of how he is using it.

 

[kanze]

Karl Heinz Buchegger wrote:
Michael wrote:
int StringReverse(char* psz)
{
char *p = psz;
char *q = psz + strlen(psz) - 1;
while (p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
return 1;
}
Thing is, when it gets to the *p = *q line, I get an access violation. [...]
The OP couldn't *possibly* done something like:
char * some_str = "reverse me";
int result = StringReverse(some_str);
...
Ya think? ;-)

That would be my guess as well.

In which case it would likely die on the call to strlen().

Hmmm. The subtraction of 1 seems right to me.

But, indeed, an empty C-style string (i.e. *psz = '\0') would make the
pointers in the `while' condition incomparable.

If psz points to an empty string, then the second line will result in
undefined behavior, before even getting to the comparison in the while
(which is also undefined, of course).

I'm also surprised that no one mentioned the obvious solution in C++:

void
StringReverse( std::string& s )
{
std::reverse( s.begin(), s.end() ) ;
}

A bit simpler than his solution.

 

[Francis Glassborow]

char * tmp = "Thomas Hansen";
StringReverse( tmp );

Anybody?!?
Suggestions?!?
Is it illegal?!?

Yes, attempts to write to a string literal have been undefined behaviour
for a couple of decades. And as from 1996 the type of a string literal
in C++ has been 'array of const char'.

 

[Artie Gold]

Artie Gold wrote:
[snip]

Hmmm. The subtraction of 1 seems right to me.

strlen returns the length without the terminating '\0'.
If he subtracts 1, then he will swap the first character
with the one-before-last character. If the goal
is to revert the string then I call this behaviour a bug.

Perhaps I'm dense today, but...

If strlen(some_string) is x, the last character is some_string[x - 1] or
some_string + x - 1, no?
[snip]

--ag

 

[Dhruv]

On Thu, 18 Dec 2003 06:41:26 -0500, Thomas Hansen wrote:

[...]

void StringReverse( char * input )
{
char * begin = input;
char * end = input+(strlen(input)-1);
while( begin < end )
{
char tmp = *end;
*end = *begin;
*begin = tmp;
++begin, --end;
}
}

You would be better off using std::reverse. Also, if you are so concerned
about efficiency, then I guess this would perform badly compared to a
straight run reverse, because for decently long strings, the cache is
getting messed up, not once, but twice!

Why your solution doesn't work I wouldn't know, but I tried it in
Visual Studio and I added up a "char * tmp = "Thomas Hansen";" line
and when I tried to reverse that line I got an "access violation".
This is probably since Visual Studio define that memory as "read only"
since it's statically linked into the process image...
Don't know if this is a bug or not....?
Why can't we do:

char * tmp = "Thomas Hansen";
StringReverse( tmp );

Anybody?!?
Suggestions?!?
Is it illegal?!?

Your compiler might put the string literal "..." in some sort of read-only
memory, or rather in the code segment of the program, so trying to assign
to memory there is seg-faultable... So much for self modifying code!


Regards,
-Dhruv.

 

[Marco Oman]

...or maybe even better...:
template<class T>
std::basic_string<T> StringReverse2( const std::basic_string<T>
& input )
{
typedef std::basic_string<T> myString;
myString retVal;
for( myString::const_iterator idx = input.end()-1;
idx != input.begin();
--idx )
{
retVal.push_back( *idx );
}
retVal.push_back( *input.begin() );
return retVal;
}

Is this variant better?
(works with any traits/allocators or other
implementation of string that do not use them)

template<class String>
String StringReverse2( const String & input )
{
String retVal;
for( String::const_iterator idx = input.end()-1;
idx != input.begin();
--idx )
{
retVal.push_back( *idx );
}
retVal.push_back( *input.begin() );
return retVal;
}

 

[Ulrich Eckhardt]

std::string retVal;
for( std::string::const_iterator idx = input.end();
idx != input.begin();
--idx )
{
retVal.push_back( *idx );

*KABOOM!*
The first iteration dereferences input.end(), which isn't dereferencable.

Wasn't there something like std::reverse()? Even if not, one could use
reverse_iterators.... it's all so easy!

Uli

 

[George van den Driessche]

As if we needed another string reversal question.

I have a problem with the following code, that I believe should work.

int StringReverse(char* psz)
{
char *p = psz;
char *q = psz + strlen(psz) - 1;
while (p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
return 1;

}

Thing is, when it gets to the *p = *q line, I get an access violation.

Any ideas why, or what I can do to fix this?

[snip]
As for zero-length strings, the problem is that if strlen(psz)
== 0 then the evaluation of q's initialiser has undefined
behaviour.

Does it? If strlen(psz)==0 then q==psz+0-1 and so q==psz-1. q is not a
pointer to a valid object, but it's never going to get dereferenced since
!p<q. That makes it a singular pointer, no? I think that's the term.

I suppose the question I'm asking is, does pointer arithmetic which gives
rise to a singular pointer constitute undefined behaviour? I know you're
allowed to produce a pointer which is one beyond the end of an array, even
though you're not allowed to dereference it. But is it wrong to produce any
other kind of pointer that isn't to a valid object?

George

 

[John Potter]

This is how I would have done it:

std::string StringReverse( const std::string & input )
{
std::string retVal;
for( std::string::const_iterator idx = input.end();
idx != input.begin();
--idx )
{
retVal.push_back( *idx );
}
return retVal;
}

Which shows that the problem is just too difficult for the average
programmer. The first thing you do is dereference end(). Try
this test to either get a fault or unexpected results.

cout << StringReverse("Hello") << " "
<< StringReverse("World").c_str() << "\n";

...or maybe even better...:
template<class T>
std::basic_string<T> StringReverse2( const std::basic_string<T>
& input )
{
typedef std::basic_string<T> myString;
myString retVal;
for( myString::const_iterator idx = input.end()-1;
idx != input.begin();
--idx )
{
retVal.push_back( *idx );
}
retVal.push_back( *input.begin() );
return retVal;
}

This is much better, it fails to compile and can do no damage. Should
you decide to fix that, test it with

cout << StringReverse2(string()) << "\n";

...or the _completely_ generic way...:

[snip]

Also dereferences end.

void StringReverse( char * input )
{
char * begin = input;
char * end = input+(strlen(input)-1);

Undefined behavior for an empty string just like the original.

while( begin < end )
{
char tmp = *end;
*end = *begin;
*begin = tmp;
++begin, --end;
}
}

Running pointers and iterators backwards is not for the novice.
Use subscripts.

Why your solution doesn't work I wouldn't know, but I tried it in
Visual Studio and I added up a "char * tmp = "Thomas Hansen";" line
and when I tried to reverse that line I got an "access violation".
This is probably since Visual Studio define that memory as "read only"
since it's statically linked into the process image...
Don't know if this is a bug or not....?

In your code, yes. In the compiler, no.

Why can't we do:

char * tmp = "Thomas Hansen";

Because that litteral string is constant. For histerical reasons, you
can get a non-const pointer to it, but you can not modify it. You need
an array.

char tmp[] = "Thomas Hansen";

StringReverse( tmp );

Now just forget about that hard to write function and use the one in the
library.

std::reverse(tmp, tmp + sizeof(tmp) - 1);

We do not want the null terminator on the front.

Since you seem to want to produce a reversed copy, we also have

char const* tmp = "Thomas Hansen";
*std::reverse_copy(tmp, tmp + strlen(tmp),
ostream_iterator<char>(cout)) = '\n';

John

 

[Siemel Naran]

"Michael" <[email protected]> containing:

std::string StringReverse( const std::string & input )
{
std::string retVal;
for( std::string::const_iterator idx = input.end();
idx != input.begin();
--idx )
{
retVal.push_back( *idx );
}
return retVal;
}

The original problem appears to be to reverse a char[] array in place. Your
solution employs additional memory.

Also, it's still in error. The expression *string.end() is an access
violation. Use reverse iterators.

for( std::string::const_reverse_iterator idx = input.rbegin();
idx != input.rend();
++idx )
{
retVal.push_back( *idx );
}

Or even better

std::copy(input.rbegin(), input.rend(), std::back_inserter(retVal));

Or just try std::reserve.

Also, since we know the final length of retVal, we can optimize by calling
reserve.

std::string retVal;
retVal.reserve(input.size());

But the above does not generalize to generic containers (as you try to do
later) as only vector and string have the function reserve.

template<class T>
T StringReverse2( typename T::const_iterator begin,
typename T::const_iterator end )

For these sorts of generic functions consider the example of std::transform
and the like

template<class InputIter, class OutputIter>
OutputIter Reverse(InputIter begin, InputIter end, OutputIter output);

Why your solution doesn't work I wouldn't know, but I tried it in
Visual Studio and I added up a "char * tmp = "Thomas Hansen";" line
and when I tried to reverse that line I got an "access violation".
This is probably since Visual Studio define that memory as "read only"
since it's statically linked into the process image...
Don't know if this is a bug or not....?

It's a feature.