gccの単方向ローテーションアルゴリズムに関する驚くべき発見 -- Raymond Chen

Blog Staff 著 | 2026年7月23日 午後1:26 | タグ: なし

前回、random-access イテレータ向けに gcc libstdc++ が使用するローテーションアルゴリズムについて解説し、最後に「驚くべき発見がある」と述べました。

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

by Raymond Chen

記事より:

驚くべき発見と言っても、がっかりする内容です。

それは、gcc libstdc++ のアルゴリズムが、前方向イテレータアルゴリズムと同一だったという発見です！

2 つのブロックが 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 でスワップを行い、両方のポインタを進めます。2 つのアルゴリズムは、first が元の A ブロックの末尾に到達するまで一致します。

			first		mid		last
			↓			↓		↓
B1	B2	B3
			↑			↑		↑
			first		mid		last

古いアルゴリズムは再帰呼び出しを行い、A1, A2, A3 を B4, B5 と交換します。これは A1 と B4、A2 と B5 を交換することで実現されます。