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.
Section: 24.3.10.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(i) 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:
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.
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.
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(i). (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(i) 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, orAn iterator equal toend()
if no such element existsposition
.iterator erase_after(const_iterator position, const_iterator last);Requires: All iterators in the range
are dereferenceable.
[(position,last)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
isbefore_begin()
or a dereferenceable iterator in the range[begin(), end))
.&x != this
.Effects: Inserts the contents of
x
afterposition
, andx
becomes empty. Pointers and references to the moved elements ofx
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 intox
.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
isbefore_begin()
or a dereferenceable iterator in the range[begin(), end))
.(first,last)
is a valid range inx
, 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)
afterposition
and removes the elements fromx
. Pointers and references to the moved elements ofx
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 intox
.Complexity: Ο(1).