2962. Iterators of Containers of move-only types do not model InputIterator

Section: 24.3.5.3 [input.iterators] Status: Open Submitter: Gašper Ažman Opened: 2017-05-10 Last modified: 2022-04-25

Priority: 2

View other active issues in [input.iterators].

View all other issues in [input.iterators].

View all issues with Open status.

Discussion:

In Table 95 in 24.3.5.3 [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:

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.

[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", 24.3.5.3 [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; }

[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.

[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", 24.3.5.3 [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; }

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

Proposed resolution:

This wording is relative to N4910.

  1. Change 24.3.5.3 [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; }