Section: 26 [algorithms] Status: Open Submitter: Alisdair Meredith Opened: 2009-10-15 Last modified: 2020-09-06
Priority: 3
View other active issues in [algorithms].
View all other issues in [algorithms].
View all issues with Open status.
Discussion:
The library has many algorithms that take a source range represented by a pair of iterators, and the start of some second sequence given by a single iterator. Internally, these algorithms will produce undefined behaviour if the second 'range' is not as large as the input range, but none of the algorithms spell this out in Requires clauses, and there is no catch-all wording to cover this in clause 17 or the front matter of 25.
There was an attempt to provide such wording in paper n2944 but this seems incidental to the focus of the paper, and getting the wording of this issue right seems substantially more difficult than the simple approach taken in that paper. Such wording will be removed from an updated paper, and hopefully tracked via the LWG issues list instead.
It seems there are several classes of problems here and finding wording to solve all in one paragraph could be too much. I suspect we need several overlapping requirements that should cover the desired range of behaviours.
Motivating examples:
A good initial example is the swap_ranges algorithm. Here there is a
clear requirement that first2 refers to the start of a valid range at
least as long as the range [first1, last1). n2944 tries to solve this
by positing a hypothetical last2 iterator that is implied by the
signature, and requires distance(first2,last2) < distance(first1,last1).
This mostly works, although I am uncomfortable assuming that last2 is
clearly defined and well known without any description of how to obtain
it (and I have no idea how to write that).
A second motivating example might be the copy algorithm. Specifically,
let us image a call like:
copy(istream_iterator<int>(is),istream_iterator(),ostream_iterator<int>(os));
In this case, our input iterators are literally simple InputIterators,
and the destination is a simple OutputIterator. In neither case am I
happy referring to std::distance, in fact it is not possible for the
ostream_iterator at all as it does not meet the requirements. However,
any wording we provide must cover both cases. Perhaps we might deduce
last2 == ostream_iterator<int>{}, but that might not always be valid for
user-defined iterator types. I can well imagine an 'infinite range'
that writes to /dev/null and has no meaningful last2.
The motivating example in n2944 is std::equal,
and that seems to fall somewhere between the two.
Outlying examples might be partition_copy that takes two output
iterators, and the _n algorithms where a range is specified by a
specific number of iterations, rather than traditional iterator pair.
We should also not accidentally apply inappropriate constraints to
std::rotate which takes a third iterator that is not intended to be a
separate range at all.
I suspect we want some wording similar to:
For algorithms that operate on ranges where the end iterator of the second range is not specified, the second range shall contain at least as many elements as the first.
I don't think this quite captures the intent yet though. I am not sure
if 'range' is the right term here rather than sequence. More awkwardly,
I am not convinced we can describe an Output sequence such as produce by
an ostream_iterator as "containing elements", at least not as a
precondition to the call before they have been written.
Another idea was to describe require that the trailing iterator support
at least distance(input range) applications of operator++ and may be
written through the same number of times if a mutable/output iterator.
We might also consider handling the case of an output range vs. an input range in separate paragraphs, if that simplifies how we describe some of these constraints.
[ 2009-11-03 Howard adds: ]
Moved to Tentatively NAD Future after 5 positive votes on c++std-lib.
[LEWG Kona 2017]
Recommend Open: The design is clear here; we just need wording
[2019-01-20 Reflector prioritization]
Set Priority to 3
Rationale:
Does not have sufficient support at this time. May wish to reconsider for a future standard.
Proposed resolution: