關於 gcc 單向旋轉演算法的驚人發現 -- Raymond Chen

By Blog Staff | 2026 年 7 月 23 日 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	A3	B4
			↑			↑		↑
			first		mid		last

舊的演算法會遞迴地將 A1, A2, A3 與 B4, B5 進行交換。這是透過將 A1 與 B4 交換，以及 A2 與 B5 交換來完成的。