>>329
iterator のレベルの操作で実装を完全に隠蔽しようと（型を消そうと）すると，
たいていの場合効率の面で許容できない実装になるような気がします．
（例えば，ポインタのインクリメント1つに関数呼び出しが常に生じる）

それでも構わないというなら一応できなくはないと思います．
value_type (reference) の型情報はインタフェースの型安全性を支配するので
この型情報は消せないですが，それ以外の型を消去した
実行時多相のイテレータクラスは作成できるかと思います．

template< class Reference >
class any_iterator
{
......
};

などのような形で， Reference 型が一致する全てのイテレータ型を run-time で
多相的に扱えるようなイテレータクラスを作成できるかと思います．実装技術的には
広く Boost で使用されている Type Erasure という技術でできると思います．

ただ1点だけ難儀があるとすれば， operator==, operator!= などの2項の比較関数において，
異なるイテレータ型の間での inter-operability が存在するので，
厳密にこれ対処しようとすると run-time double dispatch をエミュレートしないといけない，
という問題はあるかと思います．