Annex D (informative) Compatibility [diff]

D.2 Ranges and the Palo Alto TR (N3351) [diff.n3351]

D.2.4 Distance Primitive is Ο(1) for Random Access Iterators [diff.n3351.distance_algo]

1

In the Palo Alto report, the distance iterator primitive for computing the distance from one iterator position to another is not implemented in terms of operator- for random access iterators. distance, according to the report, should always be Ο(N). It reads:

The standard mandates a different definition for random access iterators: distance(i, j) == j - i. We see this as a specification error; the guarantees of the distance operation have been weakened for an iterator specialization. In our design, we consider the two operations to be distinct.

The design presented in this document keeps the specialization for random access iterators. To do otherwise would be to silently break complexity guarantees in an unknown amount of working code.

To address the concern about weakened guarantees of the distance primitive, the design presented here requires that random access iterators model SizedSentinel ([iterators.sizedsentinel]). The SizedSentinel concept requires that b - a return the number of times a would have to be incremented to make it compare equal to b. Any type purporting to be a random access iterator that fails to meet that requirement is by definition not a valid random access iterator.