This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.

### 897. Forward_list issues... Part 2

Section: 99 [forwardlist.modifiers] Status: Resolved Submitter: Howard Hinnant Opened: 2008-09-22 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [forwardlist.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:

   - SGI slist returns an iterator referencing the element after the erased range.
   - CodeWarrior slist returns an iterator referencing the element before the erased range.

   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 Editorial Resolved, addressed by N2988.

Proposed resolution:

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

Change 99 [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 99 [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).