IIRC, these operators are O(log N), right? So you can provide an operator+ that is more efficient than std::advance would be, right?
Close enough - in best case it approximates O(1), in worst case O(N), general case probably closer to O(log N).
I had a similar issue with a filtering iterator adaptor over a std::vector::iterator; is that bidirectional or random access? Its operator< is O(1) but its operator+ is O(N).
Must be a very strange underlying model if the + operator is anything other than O(1)? At any rate, vector iterators are random access.
Perhaps at some point in the future we'll have a more fine-grained set of concepts that allow us to define iterator features more precisely. For the time being, you should definitely implement the operators (if I'm right about them being logarithmic), and then decide whether to declare the iterator to be random-access or not. Weigh up the merits of strict compliance vs. pragmatism. If you don't declare it as random access, what happens? You might like to consider, for example, that some std algorithms are documented to require random access iterators - but typically work in practice with other iterators as long as they implement the required operators.
Yes, we lose access to std::find in particular under GCC I think. I'll remove them for the moment, which's a shame since the code took a long time to write, but I don't see any way around it, unless anybody else has input on the matter.