Perhaps your not aware of C++ random_access iterators? You can indeed do random access with iterators and this functionality is integral to many standard library algorithms.

http://www.cplusplus.com/reference/iterator/RandomAccessIter...