This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD Editorial status.
Section: 24.3.9.6 [forward.list.ops] Status: NAD Editorial Submitter: Ed Smith-Rowland Opened: 2008-09-15 Last modified: 2023-02-07
Priority: Not Prioritized
View all other issues in [forward.list.ops].
View all issues with NAD Editorial status.
Discussion:
I was looking at the latest draft on forward_list. Especially the splice methods.
The first one splices a whole list after a given iterator in this. The name is splice_after. I think in [forwardlist.ops] paragraph 40 change:
Effect: Insert the contents of x
beforeafter position, ...
A deeper issue involves the complexity. forward_list has no size and we don't know when we've reached the end except to walk up to it. To splice we would need to hook the end of the source list to the item after position in this list. This would involve walking length of the source list until we got to the last dereference-able element in source. There's no way we could do this in O(1) unless we stored a bogus end in forward_list.
OTOH, the last version of splice_after with iterator ranges we could do in O(1) because we know how to hook the end of the source range to ...
Unless I'm misconceiving the whole thing. Which is possible. I'll look at it again.
I'm pretty sure about the first part though.
[ 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?
We do, however, like the proposed changes and consider them Editorial. Move to NAD Editorial, Pending. Howard to open a new issue to handle the problems with the complexity requirements.
Opened 897.
Proposed resolution:
In [forwardlist.ops] paragraph 40 change:
Effect: Insert the contents of x
beforeafter position, ...