Quote Originally Posted by Lindley View Post
It's not a "choice" of iterators. The coder writing the algorithm does not necessarily control what type of iterator they're going to get when the algorithm is called. They could put a restriction on that, but the better option is to fall back to a simpler, less efficient algorithm if the iterator type provided doesn't work with the fast approach.

The proposed "jump" optimization can be applied best to random-access iterators, and for those I'm sure it works fantastically. I was simply speculating on how well it would extend to the other types, if at all.

And yes, I did grasp why it's such a good idea.
Well the "jump optimization" can be applied to almost all iterator types. The less "random access" the iterator is, the slower the algorithm, but probably better than the "dumb" algorithm regardless.

RA works very fast.
Bidirectional requires many iterations for the jumps, but does less comparisons
Forward iterator also works, if you keep the "previous" iterator in memory.

I was surprised, but I tested it, and there are gains for all iterator types.

The only iterator where the "jump" algorithm does not work are input iterators*...

I did not realize it at first, but I guess it is a generalization of the Boyer Moore algorithm.

*I had said in some previous posts that the algorithm did not work on forward iterators, but I meant input.