question on _strrev

  • Thread starter Thread starter songie D
  • Start date Start date
S

songie D

when using _strrev to reverse a string, does it actually go through and
pick up each character in turn and put it to the new position, or does it do
some clever pointer arithmetic meaning it doesn't take longer? the longer
the string is? I'm afraid I have no knowledge of machine code so am unable
to determine this by stepping through it.
 
_strrev has time complexity O(n). There is no way this can be written to be
O(1) with conventional architectures.

Ronald Laeremans
Visual C++ team
 
songie said:
when using _strrev to reverse a string, does it actually go through and
pick up each character in turn and put it to the new position, or does it do
some clever pointer arithmetic meaning it doesn't take longer? the longer
the string is? I'm afraid I have no knowledge of machine code so am unable
to determine this by stepping through it.
Click to expand...

Well, you ought to have the CRT source code, and I'd bet the function is
expressed in C there. The usual approach goes something like this:

if (length < 2)
return;

char* p = ptr_to_first_char;
char* q = ptr_to_last_char;

while (p < q)
{
swap(*p, *q);
++p;
--q;
}
 
that simple eh. nice

Doug Harrison said:
Well, you ought to have the CRT source code, and I'd bet the function is
expressed in C there. The usual approach goes something like this:

if (length < 2)
return;

char* p = ptr_to_first_char;
char* q = ptr_to_last_char;

while (p < q)
{
swap(*p, *q);
++p;
--q;
}
Click to expand...
 
That isn't shorter when it comes down the assembly and machine language.
:-)

It'll compile the same as the previous three line will.
 
That isn't shorter when it comes down the assembly and machine language.
:-)

It'll compile the same as the previous three line will.
Click to expand...

That depends on the compiler, optimization, etc. Just for example,
with VC++ 7.1 with optimization turned off, the one I posted is
minutely shorter and more efficient. Even minimal optimization will
usually make the difference disappear though.

I'd also note that as posted, both contained one potential problem --
the call to swap passed *p and *q as the arguments. In C++, this
could be made to work by using pass-by-reference. In C, you'd have
to pass p and q as the parameters instead.
 
Yes, it is O(n). Which I think you have seen from the other message in the
thread.

Ronald
 
Back
Top