How to tell advance() to use += operator on input iterators if they aren't random access

Question

Consider an input iterator like join_iterator: it iterates over the concatenation of other ranges. Calling ++i repeatedly can be much slower than a simple i += n.

Nevertheless, most C++ code that requires advancing an iterator by an arbitrary amount uses std::advance, which automatically resorts to calling ++i when the iterator isn't random-access.

(Sadly, most people use std::advance(i, n) instead of using std::advance; advance(i, n), so I can't just supply advance for my iterator and rely on ADL.)

On the other hand, I can't use + or += because input iterators don't have to implement them.

So the question is: how would I go about supporting such a scenario, when:

• Implementing such an iterator?

• Using an input iterator which might have an optimized operator +=?

(Note that advance and + isn't the only scenario in which this matters -- distance and - has the same problem.)

Answer 1

According to C++11 §24.4.4,

Since only random access iterators provide + and - operators, the library provides two function templates advance and distance. These function templates use + and - for random access iterators (and are, therefore, constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations.

You should only have to define + and -, and specify std::random_access_iterator_tag. There is no need to specialize or overload std::advance.