STLのイテレータは、
ポインタのインターフェイスで、
STLのコンテナ間の実装の差異を埋めるためのものでしょ。

じゃあ、全部ランダムアクセスにしろと。