Advice on iterator vs. index efficiency

[Tim Prince]

me22 wrote:
> On 06/10/2007, Tim Prince <tprince@computer.org> wrote:
>> It can't be identical code, as the termination test is != in one case,
>> and < in the other.  A conversion could be made by calculating the
>> number of iterations, Fortran style, but people more familiar than I
>> with the intent of STL maintain that this is incorrect.  In the 32-bit
>> pointer case, they maintain that, since there is no checking for the
>> case where the starting pointer is beyond the end, it must wrap around
>> in memory.  I haven't seen a 64-bit compiler attempt to implement this,
>> as it would not work; a typical "64-bit" machine supports only 48 bits
>> of address.
>> So it seems unlikely that combining inner and outer STL loops into one
>> would be valid.
> 
> Incrementing a pointer more than one element past the end of an array
> is UB, so calculating the number of iterations should be perfectly
> fine.  Not to mention that almost all algorithms have a (perhaps
> implicit) precondition that the begin and end iterators have to be
> into the same container and the end must be reachable by repeated
> increments from the begin.
> 

I agree about the UB behavior, but the experts we consulted say there is
no implicit rule for STL (and certainly no explicit check).  An obvious
legitimate case where it is not possible to make a simple check or
calculation of number of iterations is iteration on a linked list.  Of
course, compilers have to distinguish such cases from those where
optimizations such as vectorization are possible (and nonsensical in the
UB case).