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.