Why is splicing an entire list or a range linear for std::forward_list?
In the case of a forward_list, how would you make the range splice_after constant time? In the source list, you only have the iterators. To remove the nodes from the source forward linked list, you will need the node immediately before last
, so you need to search the source linearly for that linked list node. Hence, why it's linear in the distance between first
and last
The version that uses the entire source list still needs to search for the node immediately before the end of the source, so that it can be modified to point to the element after the splice in the destination. So it also requires linear time in the size of the source.