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
