This section details the known breaking changes likely to effect user code when being ported to the version of the Standard Library described in this document.
The algorithms described in this document permit the type of the end sentinel to differ from the type of the begin iterator. This is so that the algorithms can operate on ranges for which the physical end position is not yet known.
The physical end position of the input range is determined during the execution of many of the algorithms. Rather than lose that potentially useful information, the design presented here has such algorithms return the iterator position of the end of the range. In many cases, this is a breaking change. Some algorithms that return iterators in today's STL are changed to return pairs, and algorithms that return pairs today are changed to return tuples. This is likely to be the most noticeable breaking change.
Alternate designs that were less impactful were considered and dismissed. See Section 3.3.6 in N4128 (niebler2014) for a discussion of the issues.
In this proposal, many algorithms and utilities get stricter type checking. For example, algorithms constrained with LessThanComparable today are constrained by StrictTotallyOrdered in this document. This concept requires types to provide all the relational operators, not just operator<.
The use of coarser-grained, higher-level concepts in algorithm constraints is to make the type checks more semantic in nature and less syntactic. It also has the benefit of being less verbose while giving algorithm implementors greater implementation freedom. This approach is in contrast to the previous effort to add concepts to the Standard Library in the C++0x timeframe, which saw a proliferation of small, purely syntactic concepts and algorithm constraints that merely restated the algorithms' implementation details more verbosely in the algorithms' function signatures.
The potential for breakage must be carefully weighed against the integrity and complexity of the constraints system. The coarseness of the concepts may need to change in response to real-world usage.
The algorithm design described in this document assumes that the function objects std::equal_to and std::less get constraints added to their function call operators. (The former is constrained with EqualityComparable and the latter with StrictTotallyOrdered). Similar constraints are added to the other function objects in <functional>. As with the coarsely-grained algorithm constraints, these function object constraints are likely to cause user code to break.
Real-world experience is needed to assess the seriousness of the breakage. From a correctness point of view, the constraints are logical and valuable, but it's possible that for the sake of compatibility we provide both constrained and unconstrained functional objects.
In today's STL, iterators need not be default-constructible. The Iterator concept described in this document requires default-constructibility. This could potentially cause breakage in users' code. Also, it makes the implementation of some types of iterators more complicated. Any iterator that has members that are not default constructible (e.g., an iterator that contains a lambda that has captured by reference) must take special steps to provide default-constructibility (e.g., by wrapping non-default-constructible types in something like std::optional, as specified in the C++17 Working Draft N4618 §20.6). This can weaken class invariants.
The guarantee of default-constructibility simplifies the implementation of much iterator- and range-based code that would otherwise need to wrap iterators in std::optional. But the needs of backward-compatibility, the extra complexity to iterator implementors, and the weakened invariants may prove to be too great a burden.
We may in fact go even farther and remove the requirement of default-constructibility from the Semiregular concept. Time and experience will give us guidance here.
In this STL design, iterator_traits changes from being a class template to being an alias template. This is to intentionally break any code that tries to specialize it. In its place are the three class templates difference_type, value_type, and iterator_category. The need for this traits balkanization is because the associated types belong to separate concepts: difference_type belongs to WeaklyIncrementable; value_type belongs to Readable; and iterator_category belongs to InputIterator.
This breakage is intentional and inherent in the decomposition of the iterator concepts established by the Palo Alto report (palo-alto).
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.
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.
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.
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.
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 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.
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.
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.