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