2035. Output iterator requirements are broken

Section: 24.3.5.4 [output.iterators] Status: Open Submitter: Daniel Krügler Opened: 2011-02-27 Last modified: 2016-01-28

Priority: 3

View other active issues in [output.iterators].

View all other issues in [output.iterators].

View all issues with Open status.

Discussion:

During the Pittsburgh meeting the proposal N3066 became accepted because it fixed several severe issues related to the iterator specification. But the current working draft (N3225) does not reflect all these changes. Since I'm unaware whether every correction can be done editorial, this issue is submitted to take care of that. To give one example: All expressions of Table 108 — "Output iterator requirements" have a post-condition that the iterator is incrementable. This is impossible, because it would exclude any finite sequence that is accessed by an output iterator, such as a pointer to a C array. The N3066 wording changes did not have these effects.

[2011-03-01: Daniel comments:]

This issue has some overlap with the issue 2038 and I would prefer if we could solve both at one location. I suggest the following approach:

  1. The terms dereferencable and incrementable could be defined in a more general way not restricted to iterators (similar to the concepts HasDereference and HasPreincrement from working draft N2914). But on the other hand, all current usages of dereferencable and incrementable are involved with types that satisfy iterator requirements. Thus, I believe that it is sufficient for C++0x to add corresponding definitions to 24.3.1 [iterator.requirements.general] and to let all previous usages of these terms refer to this sub-clause. Since the same problem occurs with the past-the-end iterator, this proposal suggest providing similar references to usages that precede its definition as well.

  2. We also need to ensure that all iterator expressions get either an operational semantics in terms of others or we need to add missing pre- and post-conditions. E.g. we have the following ones without semantics: 

    *r++ = o // output iterator
*r--     // bidirectional iterator

    According to the SGI specification these correspond to 

    { *r = o; ++r; }                         // output iterator
{ reference tmp = *r; --r; return tmp; } // bidirectional iterator

    respectively. Please note especially the latter expression for bidirectional iterator. It fixes a problem that we have for forward iterator as well: Both these iterator categories provide stronger guarantees than input iterator, because the result of the dereference operation is reference, and not only convertible to the value type (The exact form from the SGI documentation does not correctly refer to reference).

[2011-03-14: Daniel comments and updates the suggested wording]

In addition to the before mentioned necessary changes there is another one need, which became obvious due to issue 2042: forward_list<>::before_begin() returns an iterator value which is not dereferencable, but obviously the intention is that it should be incrementable. This leads to the conclusion that imposing dereferencable as a requirement for the expressions ++r is wrong: We only need the iterator to be incrementable. A similar conclusion applies to the expression --r of bidirectional iterators.

[ 2011 Bloomington ]

Consensus this is the correct direction, but there are (potentially) missing incrementable preconditions on some table rows, and the Remarks on when an output iterator becomes dereferencable are probably better handled outside the table, in a manner similar to the way we word for input iterators.

There was some concern about redundant pre-conditions when the operational semantic is defined in terms of operations that have preconditions, and a similar level of concern over dropping such redundancies vs. applying a consistent level of redundant specification in all the iterator tables. Wording clean-up in either direction would be welcome.

[2011-08-18: Daniel adapts the proposed resolution to honor the Bloomington request]

There is only a small number of further changes suggested to get rid of superfluous requirements and essentially non-normative assertions. Operations should not have extra pre-conditions, if defined by "in-terms-of" semantics, see e.g. a != b or a->m for Table 107. Further, some remarks, that do not impose anything or say nothing new have been removed, because I could not find anything helpful they provide. E.g. consider the remarks for Table 108 for the operations dereference-assignment and preincrement: They don't provide additional information say nothing surprising. With the new pre-conditions and post-conditions it is implied what the remarks intend to say.

[ 2011-11-03: Some observations from Alexander Stepanov via c++std-lib-31405 ]

The following sentence is dropped from the standard section on OutputIterators:

"In particular, the following two conditions should hold: first, any iterator value should be assigned through before it is incremented (this is, for an output iterator i, i++; i++; is not a valid code sequence); second, any value of an output iterator may have at most one active copy at any given time (for example, i = j; *++i = a; *j = b; is not a valid code sequence)."

[ 2011-11-04: Daniel comments and improves the wording ]

In regard to the first part of the comment, the intention of the newly proposed wording was to make clear that for the expression 

*r = o

we have the precondition dereferenceable and the post-condition incrementable. And for the expression 

++r

we have the precondition incrementable and the post-condition dereferenceable or past-the-end. This should not allow for a sequence like i++; i++; but I agree that it doesn't exactly say that.

In regard to the second point: To make this point clearer, I suggest to add a similar additional wording as we already have for input iterator to the "Assertion/note" column of the expression ++r:

"Post: any copies of the previous value of r are no longer required to be dereferenceable or incrementable."

The proposed has been updated to honor the observations of Alexander Stepanov.

[2015-02 Cologne]

The matter is complicated, Daniel volunteers to write a paper.

Proposed resolution:

  1. Add a reference to 24.3.1 [iterator.requirements.general] to the following parts of the library preceding Clause 24 Iterators library: (I stopped from 23.2.8 [unord.req] on, because the remaining references are the concrete containers)

    1. 16.4.4.3 [swappable.requirements] p5:

      -5- A type X satisfying any of the iterator requirements (24.2) is ValueSwappable if, for any dereferenceable (24.3.1 [iterator.requirements.general]) object x of type X, *x is swappable.

    2. 16.4.4.6 [allocator.requirements], Table 27 — "Descriptive variable definitions", row with the expression c:

      a dereferenceable (24.3.1 [iterator.requirements.general]) pointer of type C*

    3. 20.2.3.3 [pointer.traits.functions]:

      Returns: The first template function returns a dereferenceable (24.3.1 [iterator.requirements.general]) pointer to r obtained by calling Ptr::pointer_to(r); […]

    4. 27.4.3.4 [string.iterators] p. 2:

      Returns: An iterator which is the past-the-end value (24.3.1 [iterator.requirements.general]).

    5. 28.3.4.6.2.3 [locale.time.get.virtuals] p. 11:

      iter_type do_get(iter_type s, iter_type end, ios_base& f,
  ios_base::iostate& err, tm *t, char format, char modifier) const;

      Requires: t shall be dereferenceable (24.3.1 [iterator.requirements.general]).

    6. 23.2.2 [container.requirements.general] p. 6:

      […] end() returns an iterator which is the past-the-end (24.3.1 [iterator.requirements.general]) value for the container. […]

    7. 23.2.4 [sequence.reqmts] p. 3:

      […] q denotes a valid dereferenceable (24.3.1 [iterator.requirements.general]) const iterator to a, […]

    8. 23.2.7 [associative.reqmts] p. 8 (I omit intentionally one further reference in the same sub-clause):

      […] q denotes a valid dereferenceable (24.3.1 [iterator.requirements.general]) const iterator to a, […]

    9. 23.2.8 [unord.req] p. 10 (I omit intentionally one further reference in the same sub-clause):

      […] q and q1 are valid dereferenceable (24.3.1 [iterator.requirements.general]) const iterators to a, […]

  2. Edit 24.3.1 [iterator.requirements.general] p. 5 as indicated (The intent is to properly define incrementable and to ensure some further library guarantee related to past-the-end iterator values):

    -5- Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array, so for any iterator type there is an iterator value that points past the last element of a corresponding sequence. These values are called past-the-end values. Values of an iterator i for which the expression *i is defined are called dereferenceable. Values of an iterator i for which the expression ++i is defined are called incrementable. The library never assumes that past-the-end values are dereferenceable or incrementable. Iterators can also have singular values that are not associated with any sequence. […]

  3. Modify the column contents of Table 106 — "Iterator requirements", 24.3.5.2 [iterator.iterators], as indicated:

    Table 106 — Iterator requirements
    Expression Return type Operational semantics Assertion/note
    pre-/post-condition
    *r reference   pre: r is dereferenceable.
    ++r X&   pre: r is incrementable.

  4. Modify the column contents of Table 107 — "Input iterator requirements", 24.3.5.3 [input.iterators], as indicated [Rationale: The wording changes attempt to define a minimal "independent" set of operations, namely *a and ++r, and to specify the semantics of the remaining ones. This approach seems to be in agreement with the original SGI specification — end rationale]:

    Table 107 — Input iterator requirements (in addition to Iterator)
    Expression Return type Operational semantics Assertion/note
    pre-/post-condition
    a != b contextually
    convertible to bool    		 !(a == b) pre: (a, b) is in the domain
    of ==.
    *a convertible to T   pre: a is dereferenceable.
    The expression
    (void)*a, *a is equivalent
    to *a.
    If a == b and (a,b) is in
    the domain of == then *a is
    equivalent to *b.
    a->m   (*a).m pre: a is dereferenceable.
    ++r X&   pre: r is dereferenceableincrementable.
    post: r is dereferenceable or
    r is past-the-end.
    post: any copies of the
    previous value of r are no
    longer required either to be
    dereferenceable, incrementable,
    or to be in the domain of ==.
    (void)r++   (void)++r equivalent to (void)++r
    *r++ convertible to T { T tmp = *r;
    ++r;
    return tmp; }     		 

  5. Modify the column contents of Table 108 — "Output iterator requirements", 24.3.5.4 [output.iterators], as indicated [Rationale: The wording changes attempt to define a minimal "independent" set of operations, namely *r = o and ++r, and to specify the semantics of the remaining ones. This approach seems to be in agreement with the original SGI specification — end rationale]:

    Table 108 — Output iterator requirements (in addition to Iterator)
    Expression Return type Operational semantics Assertion/note
    pre-/post-condition
    *r = o result is not used   pre: r is dereferenceable.
    Remark: After this operation
    r is not required to be
    dereferenceable and any copies of
    the previous value of r are no
    longer required to be dereferenceable
    or incrementable.
    post: r is incrementable.
    ++r X&   pre: r is incrementable.
    &r == &++r.
    Remark: After this operation
    r is not required to be
    dereferenceable.
     Remark: After this operation
    r is not required to be
    incrementable and any copies of
    the previous value of r are no
    longer required to be dereferenceable
    or incrementable.
    post: r is dereferenceable
    or r is past-the-end    incrementable.
    r++ convertible to const X& { X tmp = r;
    ++r;
    return tmp; }         		Remark: After this operation
    r is not required to be
    dereferenceable.
    post: r is incrementable.
    *r++ = o result is not used { *r = o; ++r; } Remark: After this operation
    r is not required to be
    dereferenceable.
    post: r is incrementable.

  6. Modify the column contents of Table 109 — "Forward iterator requirements", 24.3.5.5 [forward.iterators], as indicated [Rationale: Since the return type of the expression *r++ is now guaranteed to be type reference, the implied operational semantics from input iterator based on value copies is wrong — end rationale]

    Table 109 — Forward iterator requirements (in addition to input iterator)
    Expression Return type Operational semantics Assertion/note
    pre-/post-condition
    r++ convertible to const X& { X tmp = r;
    ++r;
    return tmp; }         		 
    *r++ reference { reference tmp = *r;
    ++r;
    return tmp; }    		  

  7. Modify the column contents of Table 110 — "Bidirectional iterator requirements", 24.3.5.6 [bidirectional.iterators], as indicated:

    Table 110 — Bidirectional iterator requirements (in addition to forward iterator)
    Expression Return type Operational semantics Assertion/note
    pre-/post-condition
    --r X&   pre: there exists s such that
    r == ++s.
    post: r is dereferenceableincrementable.
    --(++r) == r.
    --r == --s implies r == s.
    &r == &--r.
    r-- convertible to const X& { X tmp = r;
    --r;
    return tmp; }         		 
    *r-- reference { reference tmp = *r;
    --r;
    return tmp; }