A shocking discovery about gcc’s unidirectional rotation algorithm -- Raymond Chen

By Blog Staff | Jul 23, 2026 01:26 PM | Tags: None

Last time, we looked at the rotation algorithm used by gcc libstdc++ for random-access iterators, and I concluded by noting that we’re going to make a shocking discovery.

Rotation revisited: A shocking discovery about gcc’s unidirectional rotation algorithm

by Raymond Chen

From the article:

As with all shocking discoveries, this one will shock disappoint you.

The discovery is that the gcc libstdc++ algorithm is the same as the forward-iterator algorithm!

Let’s run both algorithms on a problem where the two blocks are A1, A2, A3, B1, B2, B3, B4, B5. I’ll put the old forward iterator algorithm on top and the new gcc libstdc++ algorithm below.

first		mid				last
↓			↓					↓
A1	A2	A3	B1	B2	B3	B4	B5
↑			↑					↑
first		mid				last

We swap at first and mid, then advance both pointers. The two algorithms agree until first reaches the end of the original A block.

			first		mid		last
			↓			↓		↓
B1	B2	B3	A1	A2	A3	B4	B5
			↑			↑		↑
			first		mid		last

The old algorithm recurses in order to exchange A1, A2, A3 with B4, B4. This happens by exchanging A1 with B4 and A2 with B5.