You might write your own container with random-access iterators...

There is std::iterator_traits that can tell you the category of an iterator. This requires some extreme template programming, of course.