Re: reverse a string with 0 terminator in one pass
On Mar 4, 12:40 am, Juha Nieminen <nos...@thanks.invalid> wrote:
dbtouch wrote:
I have been thinking solution for this problem: to reverse a string
with 0 terminator in one pass without using auxillary memory. My
initial thought is to use recursion, but I have not succeeded finding
an answer.
I don't even think the problem is solvable strictly in one
single pass even if you are allowed to use additional memory
freely.
Sure it is:
void
reverse( char* source )
{
std::size_t cap = 32 ;
char* result
= static_cast< char* >( std::malloc( cap + 1 ) ) ;
assert( result != NULL ) ;
*result = 0 ;
for ( std::size_t i = 0 ; source[ i ] != '\0' ; ++ i ) {
if ( cap <= i ) {
cap += cap / 2 ;
result = static_cast< char* >(
realloc( result, cap + 1 ) ) ;
assert( result != NULL ) ;
}
std::memmove( result + 1, result, i + 1 ) ;
result[ 0 ] = source[ i ] ;
}
std::strcpy( result, source ) ;
std::free( result ) ;
}
Obviously, it's not the most efficient solution in the world.
But artificial constraints (only one pass) can artificially
increase runtime. (Of course, you really have two passes
anyway. The first, generating the reversed string, and the
second, copying the results back into the original.)
Of course, if all that counts is what's in your own code:
void
reverse( char* source )
{
std::string tmp( source ) ;
std::reverse( tmp.begin(), tmp.end() ) ;
std::strcpy( source, tmp.c_str() ) ;
}
Which is probably more efficient than my code, above, but I'm
willing to bet that there's a call to strlen hidden somewhere in
the constructor of std::string that I use.
The whole question is, of course, silly. If you're doing any
string manipulation, you won't loose the size to begin with.
And if you know the size, you don't need strlen to recalculate
it, and std::reverse can be used immediately.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34