C++'s std::rotate

Fool via Digitalmars-d digitalmars-d at puremagic.com
Tue Aug 19 12:32:00 PDT 2014


On Monday, 18 August 2014 at 05:27:11 UTC, Andrei Alexandrescu 
wrote:
> On 8/17/14, 9:06 AM, Fool wrote:
>>  http://dpaste.dzfl.pl/8fc83cb06de8
>
> Yah, it's a good option. Relevant code:
>
> if (right is whole)
> {
>     //writeln("case identical");
>     return tuple(right, whole.dropExactly(whole.length));
> }
>
> (Prolly it would be better to use "whole.sameHead(right)" 
> instead of "right is whole". Also whole may not define length 
> so the actual algo is just a tad different.)

A cleaned-up version is here: http://dpaste.dzfl.pl/a8c36a0c36d0


> Trouble is it takes O(n) for that trivial case and for what may 
> be in all likelihood a useless return (iterate right all the 
> way through the end and return the empty balance).

Yah, on the other hand you can only expect to get what you pay 
for.

The strategy that naturally arises from the basic algorithm is 
even worse. In the case at hand, it suggests executing n trivial 
swaps.


> Loosely related, Xinok wrote a nice piece on in-place merge: 
> http://goo.gl/AS2P4A. A great use of rotateTail.

Thanks for that link. It's a nice writeup.

-- Fool


More information about the Digitalmars-d mailing list