gems2でのSTLの説明にて
---
Collectionがvectorなら、++itはポインタのインクリメント、すなわち
マシン命令一つである。しかしこれが、setかmapのときは、++itは
Red-Blackツリーの次のノードへのトラバースを伴う。この操作は比較的
複雑であり、ツリーのノードがメモリ全体に散乱するので
キャッシュミスを起こしやすくもなる
---
ならねーよタコ。つかSTL厨って地球の裏側にもいるのね。
STLの実装系によっては、例えvectorでも単純なインクリメントでは
済まないこともあれば、逆にsetやmapでも、内部で別の単方向線形リ
ストが確保されてる処理系では次ノード検索がメモリ参照1回に過ぎない
ケースもある。