Annex D (informative) Compatibility [diff]

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

The Palo Alto report (palo-alto) presents a comprehensive design for the Standard Template Library constrained with concepts. It served both as a basis for the Concepts Lite language feature and for this document. However, this document diverges from the Palo Alto report in small ways. The differences are in the interests of backwards compatability, to avoid confusing a large installed base of programmers already familiar with the STL, and to keep the scope of this document as small as possible. This section describes the ways in which the two suggested designs differ.

D.2.1 Sentinels [diff.n3351.sentinels]

In the design presented in this document, the type of a range's end delimiter may differ from the iterator representing the range's start position. The reasons for this change are described in N4128 (niebler2014). This causes a number of differences from the Palo Alto report:

  • The algorithms get an additional constraint for the sentinel.

  • The return types of the algorithms are changed as described above ([diff.cpp.algo_return]).

  • Some algorithms have operational semantics that require them to know the physical end position (e.g., reverse). Those algorithms must make an Ο(N) probe for the end position before proceeding. This does not change the operational semantics of any code that is valid today (the probe is unnecessary when the types of the begin and end are the same), and even when the probe is needed, in no cases does this change the compexity guarantee of any algorithm.

D.2.2 Invocables and Projections [diff.n3351.invok_proj]

Adobe's Source Libraries ASL pioneered the use of callables and projections in the standard algorithms. Invocables let users pass member pointers where the algorithms expect callables, saving users the trouble of using a binder or a lambda. Projections are extra optional arguments that give users a way to trivially transform input data on the fly during the execution of the algorithms. Neither significantly changes the operational semantics of the algorithms, but they do change the form of the algorithm constraints. To deal with the extra complexity of the constraints, the design presented here adds higher-level composite concepts for concisely expressing the necessary relationships between callables, iterators, and projections.

D.2.3 No Distinct DistanceType Associated Type [diff.n3351.distance_type]

In the Palo Alto report, the WeaklyIncrementable concept has an associated type called DistanceType, and the RandomAccessIterator concepts adds another associated type called DifferenceType. The latter is required to be convertible to the former, but they are not required to be the same type. (DifferenceType is required to be a signed integral type, but DistanceType need not be signed.) Although sensible from a soundness point of view, the author of this document feels this is potentially a rich source of confusion. This document hews closer to the current standard by having only one associated type, DifferenceType, and requiring it to be signed.

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

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.

D.2.5 Output Iterators [diff.n3351.output_iters]

The Palo Alto report does not define concepts for output iterators, making do with WeaklyIncrementable, Writable, and (where needed) EqualityComparable. The author of this document sees little downside to grouping these into the familiar OutputIterator concept. Even if not strictly needed, its absence would be surprising.

D.2.6 No Algorithm Reformulations [diff.n3351.no_eop_algos]

Between the standardization of the Standard Library and the Palo Alto report, much new research was done to further generalize the standard algorithms (see “Element of Programming”, Stepanov, McJones Stepanov:2009:EP:1614221). The algorithms presented in The Palo Alto report reflect the results of that research in the algorithm constraints, some of which (e.g., sort, inplace_merge) take iterators with weaker categories than they do in the current standard. The design presented in this document does not reflect those changes. Although those changes are desirable, generalizing the algorithms as described in The Palo Alto report feels like it would be best done in a separate proposal.