C++'s std::rotate

[Andrei Alexandrescu via Digitalmars-d]

On 8/11/14, 6:55 AM, Ary Borenszweig wrote:
> On 8/11/14, 12:29 AM, Andrei Alexandrescu wrote:
>> Hello,
>
> In which algorithms would one use std::rotate?

Depends on whom you ask :o). I think it's a fairly obscure algorithm, 
better suited as representative of a class rather than frequently 
useful. Facebook's C++ code base only has few uses, all in the same 
pattern rotate(b, b + 1, e) i.e. bubble the front all the way to the 
back with random iterators. (The result is not used and is trivially e - 1.)

(One frequent use is in ranges/iterators debates; out of the woodwork 
come people whose livelihood apparently depends on rotate, in particular 
on using rotate with non-random iterators (random access ranges make it 
easy to implement) AND needing the result.)

I do think that, like partition or partialSort, std::rotate is one of 
those algorithms that's good to know about because it may save some 
otherwise awkward solutions. Sean Parent has a nice talk 
http://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoning on such.

For my money I think http://dpaste.dzfl.pl/a0effbaee0a9 is fine (after 
being of course productionized to take advantage of random access if 
available, improve on the recursion, etc). Requiring sameHead or random 
access seems to me a good sweet spot.


Andrei