Re: reverse a string with 0 terminator in one pass
James Kanze <james.kanze@gmail.com> writes:
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 ) ;
}
You are cheating. It all depends on the definition of pass.
We could agree that one pass is accessing each elements of a vector
once (let's say one read and one write to each element of a vector).
The stack is itself to be considered a vector, pushing is writting,
poping is reading. Hiding a pass inside a function doesn't remove it.
In your reverse you have three passes at least:
- malloc may initialize the allocated memory block, 1/2 pass,
- for loop, 1/2 pass (just reading source),
- memmove, 1 pass,
- strcpy, 1 pass.
The most efficient way to implement it is to scan for the null byte
(1/2 pass) and to do the reversing (1 pass), for a total of 1.5
"passes".
std::string tmp( source ) ; 1 pass
std::reverse( tmp.begin(), tmp.end() ) ; 1 pass
std::strcpy( source, tmp.c_str() ) ; 1 pass
-----------------------------------------------------------
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.
You doubt it?
The whole question is, of course, silly.
Indeed.
--
__Pascal Bourguignon__