Title
Iterators of Containers of move-only types do not model InputIterator
Status
open
Section
[input.iterators]
Submitter
Gašper Ažman

Created on 2017-05-10.00:00:00 last changed 23 months ago

Messages

Date: 2022-04-25.15:04:14

Proposed resolution:

This wording is relative to N4910.

  1. Change [input.iterators], Table 83 — "Cpp17InputIterator requirements (in addition to Cpp17Iterator) [tab:inputiterator]" as indicated:

    Table 83 — Cpp17InputIterator requirements (in addition to Cpp17Iterator) [tab:inputiterator]
    Expression Return type Operational
    semantics
    Assertion/note pre-/post-condition
    *a reference,
    convertible to T
    that binds to const T&
    […]
    *r++ convertible to T
    that binds to const T&
    When T tmp = *r is well-formed and
    T is Cpp17MoveConstructible, then
    { T tmp = *r;
    ++r;
    return tmp; }
Date: 2022-04-15.00:00:00

[ 2022-04-25; Daniel rebases wording on N4910 ]

Date: 2022-04-25.15:04:14

[ 2018-11 San Diego Thursday night issue processing ]

Look at Ranges; EricWF to investigate. Status to Open

Previous resolution [SUPERSEDED]:

This wording is relative to N4741.

  1. Change Table 89 — "Input iterator requirements", [input.iterators] as indicated:

    Table 89 — Input iterator requirements (in addition to Iterator)
    Expression Return type Operational
    semantics
    Assertion/note pre-/post-condition
    *a reference,
    convertible to T
    that binds to const T&
    […]
    *r++ convertible to T
    that binds to const T&
    When T tmp = *r is well-formed and
    T is MoveConstructible, then
    { T tmp = *r;
    ++r;
    return tmp; }
Date: 2018-04-15.00:00:00

[ 2018-04-20; Eric Niebler provides improved wording ]

The revised wording makes it clear that you can only rely on those operational semantics when the value type is constructible from the reference type and is movable. When those conditions aren't met, we can make no guarantees about the operational semantics of *r++ (which is why *r++ is no longer a required expression of the InputIterator concept in the Ranges TS).

Really, no generic code should be doing *r++ on input iterators. Another option would be to simply deprecate this requirement for input iterators, but that might need a paper. (For forward iterators, *r++ is already required to return reference exactly, and the multi-pass guarantee gives it the proper semantics.)

I also now have a question about the proposed return type of *a and *r++, which says they must be something that "binds to const T&". Does this mean that an iterator with a reference type reference-to-[const?]-volatile-T is no longer considered an iterator? I don't think that's what we want to say. Perhaps these should read "binds to const volatile T& instead, except that has the problem for InputIterators that return prvalues that a prvalue is not bindable to a volatile reference.

Date: 2018-04-23.18:09:53

[ 2017-07 Toronto Monday issue prioritization ]

Priority 2; also could affect the ranges TS

Previous resolution [SUPERSEDED]:

This wording is relative to N4659.

  1. Change Table 95 — "Input iterator requirements", [input.iterators] as indicated:

    Table 107 — Input iterator requirements (in addition to Iterator)
    Expression Return type Operational
    semantics
    Assertion/note pre-/post-condition
    *a reference,
    convertible to T
    that binds to const T&
    […]
    *r++ convertible to T
    that binds to const T&
    { Tauto&& tmp = *r;
    ++r;
    return tmp; }
Date: 2017-05-15.16:39:30

In Table 95 in [input.iterators], it is specified that the expression *a returns reference, which must be convertible to value_type. This is not true for move-only types, which incidentally means that std::vector<std::unique_ptr<int>> does not possess even a lowly InputIterator, which is, of course, absurd.

With the advent of concepts as first-class citizens in the language, getting this right as soon as possible is a priority.

This issue seems to be similar to both LWG 448 and LWG 484, but not the same.

The proposed resolution stems from two considerations outlined below:

Convertibility is too strong for all algorithms

No algorithm in the standard library requires convertibility to value_type. If algorithms require things that smell of that, they specify the assignment or constructibility flavor they need directly. I checked this by going through the specification of each and every one of them in <algorithm> and <numeric>, which highlighted several issues unrelated to this one. These issues are presented in Algorithms with underspecified iterator requirements (LWG 2963).

reference needs to be related to value_type

Algorithms need this for the following reasons:

  • lifetime-extension: served as adequately by T const& as by T. Also works for iterators that return by value. T&& also correctly binds to T const&.

  • passing to predicates: again, served adequately by T const&

  • writing to *result: not provided by the requirement anyway.

  • capture-by-copy: currently implicitly guaranteed, but unused in the standard library (always specified separately). A separate specification can always be made for algorithms that need to capture-by-copy.

We must give due consideration to code that so far required its inputs to be CopyConstructible implicitly by requiring convertibility to T. This is done in the issue LWG 2963, which presents the results of a comb-through of <algorithm> and <numeric> to find algorithms that have this requirement, but where it is not specified. While related issues have been identified, no algorithms seems to require more than T const& convertibility without separately requiring convertibility to T.

Since such code is already compiling today, relaxing this requirement does not break code.

The only code this could possibly break is if, in a concept checking library, the InputIterator concept requirement on reference being convertible to value_type gets relaxed. Such a library, if it offered overloading based on most-specific modeled concept, could now, once fixed, resolve the call to a different algorithm, which could break user code that uses a hypothetical algorithm with a move-only container and was relying to select some other overload for move-only types based on the implicit CopyConstructible assertion provided by the iterator.

In our internal concepts-checking library, we have had this issue "fixed" since the very beginning — move-only types were too important for our internal algorithms library, and also no algorithm in it seems to require something like Iterator::value_type x = *first without also requiring copy-constructibility anyway.

History
Date User Action Args
2022-04-25 15:04:14adminsetmessages: + msg12437
2018-11-12 05:21:03adminsetmessages: + msg10213
2018-11-12 05:21:03adminsetstatus: new -> open
2018-04-23 18:09:53adminsetmessages: + msg9829
2017-07-12 01:30:31adminsetmessages: + msg9330
2017-05-13 13:52:30adminsetmessages: + msg9180
2017-05-10 00:00:00admincreate