897. Forward_list issues... Part 2

Section: 23.3.7.5 [forward.list.modifiers] Status: Resolved Submitter: Howard Hinnant Opened: 2008-09-22 Last modified: 2023-02-07

Priority: Not Prioritized

View all other issues in [forward.list.modifiers].

View all issues with Resolved status.

Discussion:

This issue was split off from 892 at the request of the LWG.

[ San Francisco: ]

This issue is more complicated than it looks.

paragraph 47: replace each (first, last) with (first, last]

add a statement after paragraph 48 that complexity is O(1)

remove the complexity statement from the first overload of splice_after

We may have the same problems with other modifiers, like erase_after. Should it require that all iterators in the range (position, last] be dereferenceable?

There are actually 3 issues here:

  1. What value should erase_after return? With list, code often looks like: 

    for (auto i = l.begin(); i != l.end();)
{
    // inspect *i and decide if you want to erase it
    // ...
    if (I want to erase *i)
        i = l.erase(i);
    else
        ++i;
}

    I.e. the iterator returned from erase is useful for setting up the logic for operating on the next element. For forward_list this might look something like: 

    auto i = fl.before_begin();
auto ip1 = i;
for (++ip1; ip1 != fl.end(); ++ip1)
{
    // inspect *(i+1) and decide if you want to erase it
    // ...
    if (I want to erase *(i+1))
        i = fl.erase_after(i);
    else
        ++i;
    ip1 = i;
}

    In the above example code, it is convenient if erase_after returns the element prior to the erased element (range) instead of the element after the erase element (range).

    Existing practice:

    There is not a strong technical argument for either solution over the other.

  2. With all other containers, operations always work on the range [first, last) and/or prior to the given position.

    With forward_list, operations sometimes work on the range (first, last] and/or after the given position.

    This is simply due to the fact that in order to operate on *first (with forward_list) one needs access to *(first-1). And that's not practical with forward_list. So the operating range needs to start with (first, not [first (as the current working paper says).

    Additionally, if one is interested in splicing the range (first, last), then (with forward_list), one needs practical (constant time) access to *(last-1) so that one can set the next field in this node to the proper value. As this is not possible with forward_list, one must specify the last element of interest instead of one past the last element of interest. The syntax for doing this is to pass (first, last] instead of (first, last).

    With erase_after we have a choice of either erasing the range (first, last] or (first, last). Choosing the latter enables: 

    x.erase_after(pos, x.end());

    With the former, the above statement is inconvenient or expensive due to the lack of constant time access to x.end()-1. However we could introduce: 

    iterator erase_to_end(const_iterator position);

    to compensate.

    The advantage of the former ((first, last]) for erase_after is a consistency with splice_after which uses (first, last] as the specified range. But this either requires the addition of erase_to_end or giving up such functionality.

  3. As stated in the discussion of 892, and reienforced by point 2 above, a splice_after should work on the source range (first, last] if the operation is to be Ο(1). When splicing an entire list x the algorithm needs (x.before_begin(), x.end()-1]. Unfortunately x.end()-1 is not available in constant time unless we specify that it must be. In order to make x.end()-1 available in constant time, the implementation would have to dedicate a pointer to it. I believe the design of N2543 intended a nominal overhead of foward_list of 1 pointer. Thus splicing one entire forward_list into another can not be Ο(1).

[ Batavia (2009-05): ]

We agree with the proposed resolution.

Move to Review.

[ 2009-07 Frankfurt ]

We may need a new issue to correct splice_after, because it may no longer be correct to accept an rvalues as an argument. Merge may be affected, too. This might be issue 1133. (Howard: confirmed)

Move this to Ready, but the Requires clause of the second form of splice_after should say "(first, last)," not "(first, last]" (there are three occurrences). There was considerable discussion on this. (Howard: fixed)

Alan suggested removing the "foward_last<T. Alloc>&& x" parameter from the second form of splice_after, because it is redundant. PJP wanted to keep it, because it allows him to check for bad ranges (i.e. "Granny knots").

We prefer to keep x.

Beman. Whenever we deviate from the customary half-open range in the specification, we should add a non-normative comment to the standard explaining the deviation. This clarifies the intention and spares the committee much confusion in the future.

Alan to write a non-normative comment to explain the use of fully-closed ranges.

Move to Ready, with the changes described above. (Howard: awaiting note from Alan)

[ 2009-10 Santa Cruz: ]

NAD EditorialResolved, addressed by N2988.

Proposed resolution:

Wording below assumes issue 878 is accepted, but this issue is independent of that issue.

Change [forwardlist.modifiers]: 

iterator erase_after(const_iterator position);

Requires: The iterator following position is dereferenceable.

Effects: Erases the element pointed to by the iterator following position.

Returns: An iterator pointing to the element following the one that was erased, or end() if no such element exists An iterator equal to position. 

iterator erase_after(const_iterator position, const_iterator last);

Requires: All iterators in the range [(position,last) are dereferenceable.

Effects: Erases the elements in the range [(position,last).

Returns: An iterator equal to position last

Change [forwardlist.ops]: 

void splice_after(const_iterator position, forward_list<T,Allocator>&& x);

Requires: position is before_begin() or a dereferenceable iterator in the range [begin(), end)). &x != this.

Effects: Inserts the contents of x after position, and x becomes empty. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

Throws: Nothing.

Complexity: Ο(1) Ο(distance(x.begin(), x.end()))

...

void splice_after(const_iterator position, forward_list<T,Allocator>&& x, 
                  const_iterator first, const_iterator last);

Requires: position is before_begin() or a dereferenceable iterator in the range [begin(), end)). (first,last) is a valid range in x, and all iterators in the range (first,last) are dereferenceable. position is not an iterator in the range (first,last).

Effects: Inserts elements in the range (first,last) after position and removes the elements from x. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

Complexity: Ο(1).