By Blog Staff | Jul 21, 2026 01:24 PM | Tags: None

RaymondChen_5in-150x150.jpgSome time ago, we looked at how to swap two adjacent blocks of memory in constant extra space, and along the way explored how std::rotate accomplishes the same task. I later claimed that the random-access implementations in both libc++ and libstdc++ treat the operation as a permutation decomposed into cycles—but after taking a closer look, I discovered that only libc++ does; libstdc++ uses a different algorithm altogether.

Rotation revisited: Another unidirectional algorithm

by Raymond Chen

From the article:

Some time ago, we looked at the problem of swapping two blocks of memory that reside inside a larger block, in constant memory, and along the way, we learned about std::rotate which swaps two adjacent blocks of memory (not necessarily the same size).

I noted in a postscript that clang’s libcxx and gcc’s libstdc++ contain specializations of std::rotate for random-access iterators that view the operation as a permutation and decomposes the permutation into cycles.

I was mistaken.

The implementation in gcc’s libstdc++ has special cases for single-element rotations, but in the general case, it uses a different algorithm.

Let’s call the blocks of memory to be exchanged A and B, where A is made up of elements A1, A2, A3, and so on; and block B has elements B1, B2, B3, and so on. Without loss of generality, suppose the A block is smaller. (If not, we can just mirror the algorithm.) And for concreteness let’s say that the elements are A1, A2, A3, B1, B2, B3, B4, B5.