1. Revision History
1.1. Revision 0  October 7th, 2019

Initial release.
2. Motivation
When building wrapping ranges and iterators, it is useful for individuals working with these wrapped iterators to provide algorithms synonymous to the C++ Standard. For example, if someone is writing a
or a
which wraps an underlying iterator and performs operations on the underlying iterator, one can optimize for the case where the wrapped iterators are potentially of the same
(
) and have the same
s. In an example from realworld code:
template < typename _It0 , typename _It1 > constexpr bool bit_equal ( bit_iterator < _It0 > __first0 , bit_iterator < _It0 > __last0 , bit_iterator < _It1 > __first1 ) { using __iterator0 = __bit_iterator < _It0 > ; using __iterator1 = __bit_iterator < _It1 > ; using __difference_type0 = typename :: std :: iterator_traits < __iterator0 >:: difference_type ; using __iterator_category0 = typename __iterator0 :: iterator_category ; using __iterator_category1 = typename __iterator1 :: iterator_category ; using __base_iterator0 = typename __iterator0 :: iterator_type ; using __base_iterator1 = typename __iterator1 :: iterator_type ; using __base_value_type0 = typename :: std :: iterator_traits < __base_iterator0 >:: value_type ; using __base_value_type1 = typename :: std :: iterator_traits < __base_iterator1 >:: value_type ; if constexpr ( :: std :: is_unsigned_v < __base_value_type0 > && :: std :: is_unsigned_v < __base_value_type1 > && :: std :: is_same_v < __base_value_type0 , __base_value_type1 > ) { if constexpr ( __is_iterator_category_or_better_v <:: std :: forward_iterator_tag , __iterator_category0 > && __is_iterator_category_or_better_v <:: std :: forward_iterator_tag , __iterator_category1 > ) { // get .base() and use internal algorithms... } } // use baseline input algorithm... }
In the innermost branch after checking iterator categories, we would like to use
on the
iterators, to compare whole words at a time or entire sequences at a time rather than just compare 1 bit at a time. The problem with using
here is that it only returns a
value: if there is any additional "work" left over after
is done comparing the fully populated underlying iterators, we now have to manually reincrement all the way to the end.
This problem is present with a large number of algorithms in the standard. From
/
to
, many algorithms advance the iterator or perform useful computation on the iterators that is then discarded, leaving higher levels to redo that work and incur a performance penalty (violating the idea that it could not be done by hand better with optimizations turned on).
This performance penalty was fixed for certain
algorithms. For example,
, where a
returns a
, allows someone to retrieve the underlying incremented
type.
There are three ways around the problem:

reimplement what the
algorithms do now, which is what libstdc++ has done for a handful of algorithms beforestd :: ranges
came along. This works only for an individual library’s implementation of that algorithm;std :: ranges 
reimplement any of the timecomplexity checks and then use a "lower level" algorithm to perform the rest of the work. For example, this would include duplicating logic from
to check sizes in the case of random access. After doing explicitstd :: ranges :: equal
checks upon gettingstd :: distance
s or better to meet the complexity requirements ofrandom_access_iterator
, a developer would then dispatch to its "lower level" algorithmic form by callingstd :: equal
, which does return iterator information;std :: ranges :: mismatch 
or, return iterator information from the
version of the algorithms that currently lose this information by returning only astd :: ranges
.bool
This paper proposes Option 3, which is enhancing only the
versions of these algorithms to return additional iterator information, in the same way
was enhanced over its non
counterpart. This is a backwardscompatible change since it does not touch the original algorithms.
3. Design
The design here is fairly straightforward: we go through all algorithms returning
in the standard library’s
namespace and change it to have a return type similar to the below structure. This proposal uses the same machinery that other range algorithms like
and friends to produce an
type. Most algorithms only need a
type, while others require a little extra information.
3.1. SingleBoolean Predicate Returns
The following result structure...
namespace ranges { template < class I1 > struct predicate_result { [[ no_unique_address ]] I1 in ; bool value ; template < class II1 > requires convertible_to < const I1 & , II1 > operator predicate_result < II1 > () const & { return { in , value }; } template < class II1 > requires convertible_to < I1 > && convertible_to < I2 > operator predicate_result < II1 > () && { return { std :: move ( in ), value }; } explicit operator bool () const { return value ; } }; }
... works for the following algorithm return types.

In Nonmodifying Algorithms [alg.nonmodifying]:

;std :: ranges :: all_of 
;std :: ranges :: any_of 
and,
.std :: ranges :: none_of 
In Sorting and related operations [alg.sorting]:

;std :: ranges :: is_sorted 
;std :: ranges :: is_partitioned 
and,
.std :: ranges :: is_heap
It is notable that
,
, and
all have versions of themselves that return an iterator and also do not have additional complexity requirements specified in the standard over their
versions. Therefore, it may be prudent to just leave changes to these algorithms off entirely rather than also return both a convenience
value and the iterator.
Likewise,
,
, and
can be seen as wrappers around the
algorithms. None of them impose additional complexity requirements, nor do standard libraries today do anything particularly special in the general implementation of these wrappers either. While the information could be returned, simply using a lowerlevel facility would be suitable in the cases here.
3.2. SingleBoolean Comparison Returns
Similarly, the following
structure...
namespace ranges { template < class I1 , class I2 > struct comparison_result { [[ no_unique_address ]] I1 in1 ; [[ no_unique_address ]] I2 in2 ; bool value ; template < class II1 , class II2 > requires convertible_to < const I1 & , II1 > && convertible_to < const I2 & , II2 > operator comparison_result < II1 , II2 > () const & { return { in1 , in2 , value }; } template < class II1 , class II2 > requires convertible_to < I1 , II1 > && convertible_to < I2 , II2 > operator predicate_result < II1 , II2 > () && { return { std :: move ( in1 ), std :: move ( in2 ), value }; } explicit operator bool () const { return value ; } }; }
... works for algorithms which take 2 ranges.

In Nonmodifying Algorithms [alg.nonmodifying]:

;std :: ranges :: equal 
and,
.std :: ranges :: is_permutation 
In Sorting and related operations [alg.sorting]:

;std :: ranges :: binary_search 
and,
.std :: ranges :: lexicographic_compare
Algorithms such as
are not included in this fix up because that algorithm works with input ranges, and the iterators returned from it by the time the algorithm completes can essentially be empty husks that contain no valuable information. The goal would be to have a wellspecified return value for the iterators on algorithm success, where logically that information implies the whole range was examined.
returns whether or not the range is in lexicographic order: an enhancement to that would be to return the incrementedtotheend
and
iterators in the case where the algorithm returns true
for the result. Otherwise, the value of
and
are unspecified. Similarly for
: the incremented iterators should be returned from
in
and
if the algorithm returns true: otherwise, the value of the returned iterators is unspecified.
3.3. Questions
Question 1: These algorithms take in a range. We recognize that the result type is likely more ergonomic and efficient in terms of the amount of times an iterator has to be moved to store the result, and so recommended return types that return iterators like the other modified
algorithms. Still,
is it worthwhile to have the return results return a
type, rather than just a
std :: ranges :: subrange < ... > type with the iterators?
result
Question 2: Some of these algorithms are more or less trivial wrappers around their counterparts with no additional complexity requirements or guarantees obtain by metaprogramming checks. These are
,
, and
.
Is returning the iterator worth it when there are
versions of all these algorithms which do return the iterator and can be defined as convenience wrappers?
X_until