What you are asking for is impossible.
counted_iterator is intended to mirror the functionality of the iterator it is given. But it can only work with what it is given. If you give it a random-access iterator, it will mirror that functionality.
If you give it a forward iterator and then allow the user to increment it with any integer, you are lying to the user. Random access iterator incrementing means more than that you can call operator+ with an integer. It means that this operation has O(1) complexity. And if the underlying iterator doesn't have that complexity on its iteration advancement... you cannot manufacture it from outside of the iterator.
Well, you could by heap-allocating an array of iterators of the size determined by the range you're given. But that's a really bad idea.
If you want to increment an iterator a bunch, but you don't know that the iterator is random-access, use std::next or std::advance .