关于 gcc 单向旋转算法的惊人发现 -- Raymond Chen

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

上次，我们研究了 gcc libstdc++ 针对随机访问迭代器使用的旋转算法，并在结尾处提到我们将揭示一项惊人的发现。

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

by Raymond Chen

文章内容：

正如所有惊人发现一样，这次发现会让你大失所望。

这项发现是：gcc libstdc++ 算法与 前向迭代器算法完全相同！

让我们在两个区块分别为 A1, A2, A3, B1, B2, B3, B4, B5 的问题上运行这两种算法。我将旧的前向迭代器算法放在上方，把新的 gcc libstdc++ 算法放在下方。

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

我们在 first 和 mid 处交换，然后同时前移两个指针。两种算法在 first 到达原始 A 区块末尾之前完全一致。

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

旧算法通过递归来交换 A1, A2, A3 与 B4, B5。具体做法是 A1 与 B4 交换，A2 与 B5 交换。