STL

それで嬉しくなってしばらくGCCのSTLのソースコードを眺めていました. "M-. RET"でカーソル周辺の単語をtags-searchしてくれるので関数階層を下るのも簡単. 以下分かったこと.

• sortは基本的にはquick sort. pivotはリスト中の3要素のmedian, 再帰が対数回を超えたらあとはheapsortする. またquick sortの再帰は最後まで行わず*1, 最後にinsertion sortで全体を整える.
• stable_sortは基本的にはmerge sort. 十分なバッファが確保できなかったらinplaceで行うためにコードはややこしい. inplaceの場合は最悪計算量がO(n * log(n))になるかは怪しい.
• nth_elementはリスト中の3要素のmedianをpivotとして使うpartitionベースのselection.

*1:具体的には各小リストの長さが16以下になったらやめる.