Why is splicing an entire list or a range linear for std::forward_list?

Question

Splicing a range from one list to another can be accomplished in constant time, at the expense of making size()'s complexity linear.

C++11 has changed that in case of std::list by requiring size() to be constant time. This broke, for example, gcc's implementation, see [C++0x] std::list::size complexity.

Apart from the range splice(), is there any other reason why size() could not be made constant time in the earlier, C++03 conforming std::list implementations?

Why is splicing an entire list or a range linear for std::forward_list?

See splice_after(), cases (1) and (3). See also 23.3.4.6 forward_list operations [forwardlist.ops] in the standard draft N3485. The std::forward_list doesn't even implement size().

I know forward_list is a singly linked list but I don't see why one couldn't do the range splice_after() in constant time. I am probably missing something trivial here...

---

EDIT: OK, It was at least partly my misunderstanding, I expected that 4 would not remain in the source list. Code:

#include <algorithm>
#include <iostream>
#include <forward_list>

using namespace std;

void dump_list(const forward_list<char>& l) {
    for(char c : l)
        cout << c << ' ';
    cout << '\n';
}

int main()
{
    forward_list<char> trg = {'a','b','c'};
    forward_list<char> src = {'1','2','3','4'};

    auto first = src.begin();
    auto last  = find(src.begin(), src.end(), '4');
    cout << "first = " << *first << ", last = " << *last << "\n\n";

    trg.splice_after(trg.begin(), src, first, last);

    cout << "Target after splice:\n";
    dump_list(trg);

    cout << "Source after splice:\n";
    dump_list(src);

    cout << endl;
    return 0;
}

Output:

first = 1, last = 4
Target after splice:
a 2 3 b c
Source after splice:
1 4 

Answer 1

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.

Answer 2

The range splice is the only reason that size wouldn't have been constant time in previous C++ standards. In fact the Sun CC compiler chose to make size constant time and all versions of splice linear.

Splicing an entire forward list is linear because you have to traverse the list you're merging to be able to link it's last node back into the list you're splicing into. I can't figure out why the range splice is linear though.

EDIT: As @Xeo points out, the range-based version also requires linear time because last is not included in the range and it needs to search from first to find the iterator before last.