P2408R1
Ranges views as inputs to non-Ranges algorithms

1. Abstract

Change the iterator requirements for non-Ranges algorithms. Instead of requiring that iterators meet certain Cpp17Iterator requirements, require that the iterators model certain iterator concepts. This makes iterators from several standard views usable with non-Ranges algorithms.

2. Revision history

2.1. R0

This paper arose out of a private e-mail discussion where Bryce Adelstein Lelbach questioned why code that is similar to the first example in § 3 Motivation didn’t compile with MSVC.

2.2. R1

Add the section § 7 Sentinels based on discussion in SG9 (Ranges) on 9 Aug 2021. This is just background information; there is no change to what is being proposed.

3. Motivation

These two snippets of code should be well-formed:

std::vector<int> data = ...;
auto v = data | std::views::transform([](int x){ return x * x; });
int sum_of_squares = std::reduce(std::execution::par, begin(v), end(v));

auto idxs = std::views::iota(0, N);
std::transform(std::execution::par, begin(idxs), end(idxs), begin(sqrts),
               [](int x) { return std::sqrt(float(x)); });

It should be possible, in most cases, to use the iterators from ranges and views as the inputs to C++17 parallel algorithms and to other algorithms that require forward iterators or greater.

4. Analysis

std::reduce requires that its iterator parameters satisfy the requirements of Cpp17ForwardIterator. One of those requirements is that std::iterator_traits<I>::reference be a reference type, either T& or const T&. ([forward.iterators]/p1.3) The iterator category of transform_view::iterator matches the iterator category of the underlying range only if the transformation function returns an lvalue reference. If the return type of the transformation function is a value rather than a reference, the iterator category of transform_view::iterator is input_iterator_tag, because the iterator’s reference type alias can’t be a reference type. ([range.transform.iterator]/p2)

In this example, the lambda transformation function returns a value, so the iterators passed to std::reduce are only input iterators in the classic iterator taxonomy used by the non-Ranges algorithms, even though the iterators satisfy the random_access_iterator concept in the Ranges iterator taxonomy.

Several other views have the same issue, where the iterator_category is input_iterator_tag even when the iterator_concept is something else.

• iota_view's iterator_category is always input_iterator_tag while its iterator_concept is often random_access_iterator_tag. [range.iota.iterator]

• lazy_split_view's iterator_category is always input_iterator_tag while its iterator_concept is forward_iterator_tag if the underlying range is a forward range. [range.lazy.split.outer]

• split_view's iterator_category is always input_iterator_tag and its iterator_concept is always forward_iterator_tag. [range.split.iterator]

• elements_view is similar to transform_view in that the iterator_category depends on the value category of the return type of the std::get<N> function used to extract the element. iterator_category is input_iterator_tag if std::get<N> returns an rvalue, and (mostly) matches the iterator category of the base range otherwise. The iterator_concept depends only on the base range, not the std::get<N> function. [range.elements.iterator]/p2

4.1. Current situation

MSVC checks that iterator arguments to parallel algorithms have the correct iterator category. If either of the code snippets in § 3 Motivation are compiled, the compilation will fail with "error C2338: Parallel algorithms require forward iterators or stronger."

libstd++ does not do any up-front checking of the iterator category of algorithm arguments. Its implementation of algorithms will accept iterators of any category as long as the iterators support the operations that are actually used in the implementation. The code snippets in § 3 Motivation can be successfully compiled with GCC 11.1.

5. Possible Solutions

5.1. Do nothing

We could simply wait for parallel versions of Range-based algorithms to make their way into the standard. Until then, users who want to use certain view iterators as inputs to parallel algorithms are out of luck.

This solution might be worth considering if parallel Range-based algorithms were on track for C++23. But [P2214] "A Plan for C++23 Ranges" puts parallel Range-based algorithms in Tier 2 of Ranges work, with the caveat that the work needs to be coordinated with Executors to make sure the interface is correct. That pushes the work well past C++23.

Even if parallel Range-based algorithms were already in the draft IS, it would still be worth investigating how to get Ranges iterators to work better with non-Ranges algorithms, in the interest of having the various parts of the Standard work well together.

5.2. Relax the Cpp17 iterator requirements

We could change the definition of Cpp17ForwardIterator ([forward.iterators]), removing the requirement that reference be defined for constant iterators. reference would still need to be defined, and be T&, for mutable iterators.

The authors do not consider this option to be feasible. This change would break existing code that assumes that iterator_traits<I>::reference exists and is a reference type if the iterator category is forward_iterator_tag or greater. There are other possible solutions that don’t break existing code.

5.3. Algorithms require concepts instead of categories

We could change the wording in [algorithms.requirements] to say that the template arguments of the algorithms shall model an iterator concept rather than meet a set of Cpp17 requirements. For example:

If an algorithm’s template parameter is named ForwardIterator, ForwardIterator1, or ForwardIterator2, the template argument shall meet the Cpp17ForwardIterator requirements ([forward.iterators]) model forward_iterator ([iterator.concept.forward]) .

This change relaxes the requirements on the template arguments for non-Ranges algorithms. Implementations may need to change to no longer depend on requirements that are no longer required. It is not expected that this will be a big burden, since a well-written algorithm shouldn’t be depending on iterator_traits<I>::reference being a reference type for an iterator that is only used for input.

This change will not break any existing code because the iterator concept imposes fewer requirements on the type than the corresponding Cpp17...Iterator requirements. Any well-formed program will continue to be well-formed and have the same behavior. Some programs that were not well-formed may become well-formed, such as the two motivating examples in this paper; these will have reasonable, non-surprising behavior.

This is the solution proposed by this paper. See immediately below for more details and analysis of this solution.

6. Impact and Details

6.1. Changes

In every bullet of [algorithms.requirements]/p4 except for the one about InputIterator, change the requirement on the iterator from meeting a set of Cpp17...Iterator requirements to modeling the corresponding iterator concept.

For InputIterator, the iterator shall model both the input_iterator and equality_comparable concepts. The input_iterator concept does not require equality comparisons, because in Ranges input iterators are often compared with a sentinel rather than with another iterator. Classic algorithms, however, take iterator pairs rather than iterator/sentinel, so any input iterator must be equality comparable.

This equality_comparable exception applies only to input iterators because:

• Concept forward_iterator requires equality_comparable via incrementable and regular. That also covers bidirectional, random access, and contiguous iterators because they all require forward_iterator.

• Output iterators are generally not compared for equality with other iterators in well-behaved algorithms.

6.2. Relaxed requirements

The Cpp17...Iterator requirements and the iterator concepts are worded very differently, making it challenging to compare them directly. As far as I can determine, no iterator concept requires anything of its type that is not also required by the corresponding Cpp17...Iterator set of requirements. In the other direction, these are the things required by the Cpp17...Iterator requirements that are not required by the concepts:

• Cpp17InputIterator and Cpp17OutputIterator require that the iterator be copyable, but input_iterator and output_iterator only require that it be movable.

• Cpp17InputIterator requires that the iterator be Cpp17EqualityComparable, but input_iterator does not require equality_comparable. (See § 6.1 Changes for how this is dealt with.)

• Cpp17ForwardIterator requires that reference be a reference type, either T& or const T&. forward_iterator requires that iter_reference_t<I> exist but doesn’t require that it be a reference type. This same difference also applies to bidirectional iterators and random access iterators. (This difference is the root cause of the problems, and the reason for this paper.)

6.3. Other uses

The Cpp17...Iterator requirements are used in several other places in the standard besides [algorithms.requirements]. It is proposed that in places where the requirements are on iterator types that the program passes to standard algorithms, the wording is changed from meeting Cpp17...Iterator requirements to modeling an iterator concept, just like is being done for [algorithms.requirements]. See § 10 Wording for all the places where this happens.

Other uses of Cpp17...Iterator requirements are not changed by this proposal. In some of those cases the requirement is on a standard iterator, not a program iterator, so relaxing the requirements could break existing code. The other uses are in [sequence.reqmts], [associative.reqmts.general], [move.iter.requirements], [locale.category], [fs.req], [fs.path.req], [fs.class.directory.iterator.general], [time.zone.db.list], [reverse.iter.requirements], [allocator.requirements.general], [stacktrace.basic.obs], [string.view.iterators], [container.requirements.general], [span.iterators], [iterator.operations], [alg.equal], and [valarray.range].

6.4. Implementation impact

If any standard algorithm implementations rely on the requirements listed in § 6.2 Relaxed requirements, those implementations will have to change to not rely on those requirements. It is assumed, though not yet verified, that not many algorithm implementations will have to change, and that the changes will not be difficult to make. The hardest part might be identifying places that need to be changed.

Any implementation that checks the iterator category of algorithm iterator arguments, such as MSVC, will have to change the way those checks happen. That should be a straightforward, if somewhat tedious, change.

6.5. User impact

No well-formed programs will become ill-formed or have different behavior as a result of this change. Some ill-formed programs will become well-formed with the behaviors users would expect. This change will reduce the number of surprises by making code that users reasonably expect to be well-formed actually well-formed. It is not expected that any users would be negatively impacted by this change.

7. Sentinels

Many ranges use iterator/sentinel pairs, rather than a pair of iterators, as the bounds of the range. Non-Ranges algorithms always require a pair of iterators that have the same type, and will not work with iterator/sentinel pairs. If this proposal is adopted, more ranges than before will be usable with classic algorithms, but the sentinel issue will still prevent some ranges from being useful as inputs to classic algorithms.

The two examples in § 3 Motivation use iterator pairs and don’t suffer from the sentinel issue. transform_view::end() returns an iterator rather than a sentinel if the base range is a common range. In the example, the base range is std::vector, which is a common range. iota_view::end() returns an iterator rather than a sentinel when the range has an upper bound of the same type as the lower bound. It is primarily unbounded iota_views that use a sentinel. Passing an unbounded iota_view to any classic algorithm function as a first/last pair isn’t going to work well, even if first and last are of the same type. I don’t think iota_view's use of sentinels will be a problem in practice in this area.

If a range with iterator/sentinel pairs needs to be used with a classic algorithm, there is a good chance that the user can simply wrap the range in a common_view. The common_view's iterators will be random access if the base range is random access and sized, and will be forward iterators if the base range’s iterator is at least forward. That will allow the common_view to be used in most places where the base range would have been usable if it had used an iterator rather than a sentinel.

I am in favor of changing the non-Ranges algorithms to use iterator/sentinel pairs. But that change can be done independently, not as part of this paper. Both changes are useful on their own, independent of the other, and wouldn’t benefit from being tied together.

8. Implementation Experience

None so far. Some implementation experience will be attempted if LEWG likes the proposal and is considering forwarding it on.

Because this is a change to a specification that is not directly implemented in code, it is not a simple matter to make the change to a standard library implementation and test it. I want to find out if the committee is at all interested in this idea before spending much time on implementing it.

9. Feature Test Macro

This change affects the well-formed-ness of certain code. Some users might want to write their code two different ways based on whether or not a standard library has implemented this change. Therefore, I believe that the benefit to users of a feature test macro is greater than the cost to implementers of defining it. This proposal adds the new macro __cpp_lib_algorithm_iterator_requirements.

10. Wording

Changes are relative to N4888 from June 2021.

Change 25.2 "Algorithms requirements" [algorithms.requirements] paragraph 4 as follows:

Throughout this Clause, where the template parameters are not constrained, the names of template parameters are used to express type requirements.

• If an algorithm’s template parameter is named InputIterator, InputIterator1, or InputIterator2, the template argument shall meet the Cpp17InputIterator requirements ([input.iterators]) model input_iterator ([iterator.concept.input]) and equality_comparable ([concept.equality.comparable]) .

• If an algorithm’s template parameter is named OutputIterator, OutputIterator1, or OutputIterator2, the template argument shall meet the Cpp17OutputIterator requirements ([output.iterators]) model output_iterator ([iterator.concept.output]) .

• If an algorithm’s template parameter is named ForwardIterator, ForwardIterator1, or ForwardIterator2, the template argument shall meet the Cpp17ForwardIterator requirements ([forward.iterators]) model forward_iterator ([iterator.concept.forward]) .

• If an algorithm’s template parameter is named NoThrowForwardIterator, the template argument shall meet the Cpp17ForwardIterator requirements ([forward.iterators]) model forward_iterator , and is required to have the property that no exceptions are thrown from increment, assignment, or comparison of, or indirection through, valid iterators.

• If an algorithm’s template parameter is named BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, the template argument shall meet the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]) model bidirectional_iterator ([iterator.concept.bidir]) .

• If an algorithm’s template parameter is named RandomAccessIterator, RandomAccessIterator1, or RandomAccessIterator2, the template argument shall meet the Cpp17RandomAccessIterator requirements ([random.access.iterators]) model random_access_iterator ([iterator.concept.random.access]) .

As currently worded, before these changes, the implementation is required to issue a diagnostic if the iterator type doesn’t meet the given requirements. The requirements contain some semantic elements, which the implementation cannot reliably check at compile time, making it difficult to always issue the required diagnostic. The proposed wording change does not fix this issue, since the concepts also have semantic requirements that can’t be reliably checked at compile time. Should the wording be changed to make the failure to meet the iterator requirements IFNDR or undefined behavior?

Change 25.7.12 "Sample" [alg.random.sample] paragraphs 2 and 5 as follows:

Paragraph 2:

Preconditions: out is not in the range [first, last). For the overload in namespace std:

• PopulationIterator meets the Cpp17InputIterator requirements ([input.iterators]) models input_iterator([iterator.concept.input]) and equality_comparable ([concept.equality.comparable]) .

• SampleIterator meets the Cpp17OutputIterator requirements ([output.iterators]) models output_iterator ([iterator.concept.output]) .

• SampleIterator meets the Cpp17RandomAccessIterator requirements ([random.access.iterators]) models random_access_iterator ([iterator.concept.random.access]) unless PopulationIterator meets the Cpp17ForwardIterator requirements ([forward.iterators]) models forward_iterator([iterator.concept.forward]).

• remove_reference_t<UniformRandomBitGenerator> meets the requirements of a uniform random bit generator type ([rand.req.urng]).

Paragraph 5:

Remarks:

• For the overload in namespace std, stable if and only if PopulationIterator meets the Cpp17ForwardIterator requirements models forward_iterator . For the first overload in namespace ranges, stable if and only if I models forward_iterator.

• To the extent that the implementation of this function makes use of random numbers, the object g serves as the implementation’s source of randomness.

Change 26.6.8.1 "Class seed_seq" [rand.util.seedseq] paragraphs 6, 9, and 15 as follows:

Paragraph 6:

Preconditions: InputIterator meets the Cpp17InputIterator requirements ([input.iterators]) models input_iterator ([iterator.concept.input]) and equality_comparable ([concept.equality.comparable]) .

Paragraph 9:

Preconditions: RandomAccessIterator meets the Cpp17RandomAccessIterator requirements ([random.access.iterators]) and models random_access_iterator ([iterator.concept.random.access]) and meets the requirements of a mutable iterator.

Paragraph 15:

Preconditions: OutputIterator meets the Cpp17OutputIterator requirements ([output.iterators]) models output_iterator ([iterator.concept.output]) .

Change 26.6.9.6.1 "Class template discrete_distribution" [rand.dist.samp.discrete] paragraph 5 as follows:

Preconditions: InputIterator meets the Cpp17InputIterator requirements ([input.iterators]) models input_iterator ([iterator.concept.input]) and equality_comparable ([concept.equality.comparable]) . If firstW == lastW, let n = 1 and w0 = 1. Otherwise, [firstW,lastW) forms a sequence w of length n > 0.

Change 26.6.9.2 "Class template piecewise_constant_distribution" [rand.dist.samp.pconst] paragraph 5 as follows:

Preconditions: InputIteratorB and InputIteratorW each meet the Cpp17InputIterator requirements ([input.iterators]) model input_iterator ([iterator.concept.input]). InputIteratorB models equality_comparable ([concept.equality.comparable]) . If firstB == lastB or ++firstB == lastB, let n = 1, w0 = 1, b0 = 0, and b1 = 1. Otherwise, [firstB,lastB) forms a sequence b of length n + 1, the length of the sequence w starting from firstW is at least n, and any wk for k ≥ n are ignored by the distribution.

Change 26.6.9.3 "Class template piecewise_linear_distribution" [rand.dist.samp.plinear] paragraph 5 as follows:

Preconditions: InputIteratorB and InputIteratorW each meet the Cpp17InputIterator requirements ([input.iterators]) model input_iterator ([iterator.concept.input]) InputIteratorB models equality_comparable ([concept.equality.comparable]) . If firstB == lastB or ++firstB == lastB, let n = 1, ρ0 = ρ1 = 1, b0 = 0, and b1 = 1. Otherwise, [firstB,lastB) forms a sequence b of length n + 1, the length of the sequence w starting from firstW is at least n + 1, and any wk for k ≥ n + 1 are ignored by the distribution.

Change 25.7.9 "Unique" [alg.unique] paragraph 8.2.2 as follows:

• For the overloads with no ExecutionPolicy, let T be the value type of InputIterator. If InputIterator meets the Cpp17ForwardIterator requirements models forward_iterator ([iterator.concept.forward]) , then there are no additional requirements for T. Otherwise, if OutputIterator meets the Cpp17ForwardIterator requirements models forward_iterator and its value type is the same as T, then T meets the Cpp17CopyAssignable (Table 31) requirements. Otherwise, T meets both the Cpp17CopyConstructible (Table 29) and Cpp17CopyAssignable requirements.

Change 25.7.14 "Shift" [alg.shift] paragraphs 5 and 6 as follows:

Preconditions: n >= 0 is true. The type of *first meets the Cpp17MoveAssignable requirements. ForwardIterator meets the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]) or models bidirectional_iterator ([iterator.concept.bidir]) or meets the Cpp17ValueSwappable requirements.

Effects: If n == 0 or n >= last - first, does nothing. Otherwise, moves the element from position first + i into position first + n + i for each non-negative integer i < (last - first) - n. In the first overload case, if ForwardIterator meets the Cpp17BidirectionalIterator requirements models bidirectional_iterator, does so in order starting from i = (last - first) - n - 1 and proceeding to i = 0.

Change 25.8.5 "Partitions" [alg.partitions] paragraph 8.1 as follows:

• For the overload with no ExecutionPolicy, exactly N applications of the predicate and projection. At most N/2 swaps if the type of first meets the Cpp17BidirectionalIterator requirements for the overloads in namespace std or models bidirectional_iterator for the overloads in namespace ranges , and at most N swaps otherwise.

Change 30.9.6 "Formatting" [re.results.form] paragraph 1 as follows:

Preconditions: ready() == true and OutputIter meets the requirements for a Cpp17OutputIterator ([output.iterators]) models output_iterator ([iterator.concept.output]) .

Change 30.10.2 "regex_match" [re.alg.match] paragraph 1 as follows:

Preconditions: BidirectionalIterator meets the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]) models bidirectional_iterator ([iterator.concept.bidir]) .

Change 30.10.3 "regex_search" [re.alg.search] paragraph 1 as follows:

Preconditions: BidirectionalIterator meets the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]) models bidirectional_iterator ([iterator.concept.bidir]) .

Add the following feature test macro to [version.syn]:

#define __cpp_lib_algorithm_iterator_requirements date // also in <algorithm>, <numeric>, <memory>