question on _strrev

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.

Ronald
Mon May 10 14:11:37 CDT 2004

_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 D" <songie@d.com> wrote in message
news:uSva0irNEHA.1388@TK2MSFTNGP09.phx.gbl...
> 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.
>
>

Doug
Mon May 10 14:18:17 CDT 2004

songie D wrote:

> 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.

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;
}

--
Doug Harrison
Microsoft MVP - Visual C++

songie
Mon May 10 17:44:11 CDT 2004

ok thanks...but it is O(n) and not O(n-squared) or anything?

"Ronald Laeremans [MSFT]" <ronaldl@online.microsoft.com> wrote in message
news:%23xoziKsNEHA.1004@TK2MSFTNGP10.phx.gbl...
> _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 D" <songie@d.com> wrote in message
> news:uSva0irNEHA.1388@TK2MSFTNGP09.phx.gbl...
> > 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.
> >
> >
>
>

songie
Mon May 10 17:44:42 CDT 2004

that simple eh. nice

"Doug Harrison [MVP]" <dsh@mvps.org> wrote in message
news:f2lv90deqbeen62pfpothrdujpk07d9qc8@4ax.com...
> songie D wrote:
>
> > 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.
>
> 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;
> }
>
> --
> Doug Harrison
> Microsoft MVP - Visual C++

Jerry
Mon May 10 19:56:34 CDT 2004

In article <uHgrgBuNEHA.1400@TK2MSFTNGP10.phx.gbl>, songie@D.com
says...
> that simple eh. nice

Usually it's shorter, though one statement is arguably more complex:

while (p<q)
swap(*p++, *q--);

--
Later,
Jerry.

The universe is a figment of its own imagination.

Relvinian
Mon May 10 20:02:29 CDT 2004

That isn't shorter when it comes down the assembly and machine language.
:-)

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

"Jerry Coffin" <jcoffin@taeus.us> wrote in message
news:MPG.1b09d2ad249152c69896c4@msnews.microsoft.com...
> In article <uHgrgBuNEHA.1400@TK2MSFTNGP10.phx.gbl>, songie@D.com
> says...
> > that simple eh. nice
>
> Usually it's shorter, though one statement is arguably more complex:
>
> while (p<q)
> swap(*p++, *q--);
>
> --
> Later,
> Jerry.
>
> The universe is a figment of its own imagination.

Jerry
Mon May 10 21:28:11 CDT 2004

In article <IO-dnfEaA7C4uz3dRVn_iw@comcast.com>, m@msn.com says...
> 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 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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Ronald
Tue May 11 15:57:59 CDT 2004

Yes, it is O(n). Which I think you have seen from the other message in the
thread.

Ronald

"songie D" <songie@D.com> wrote in message
news:uTOjOBuNEHA.3944@tk2msftngp13.phx.gbl...
> ok thanks...but it is O(n) and not O(n-squared) or anything?
>
> "Ronald Laeremans [MSFT]" <ronaldl@online.microsoft.com> wrote in message
> news:%23xoziKsNEHA.1004@TK2MSFTNGP10.phx.gbl...
>> _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 D" <songie@d.com> wrote in message
>> news:uSva0irNEHA.1388@TK2MSFTNGP09.phx.gbl...
>> > 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.
>> >
>> >
>>
>>
>
>