Complexity of std::list::splice and other list containers

Question

I have some code which deals with various std::list objects, and I am currently using a very inefficient method of transferring content between them (I'm iterating through arbitrary sections of one list, and moving the elements one by one into the second list). I wrote this code some time ago before I was aware of the std::list::splice function, which I now intend to replace my code with, for example:

list<string> list1, list2;

list1.push_back("a");
list1.push_back("b");
list1.push_back("c"); // list1: "a", "b", "c"

list<string>::iterator iterator1 = list1.begin();
iterator1++: // points to "b"

list2.push_back("x");
list2.push_back("y");
list2.push_back("z"); // list2: "x", "y", "z"

list<string>::iterator iterator2 = list2.begin();
iterator2++; // points to "y"

list1.splice(iterator1, list2, iterator2, list2.end());

// list1: "a", "y", "z", "b", "c"
// list2: "x"

I have a question regarding the complexity of the splice function. According to this source:

http://www.cplusplus.com/reference/stl/list/splice/

It should have linear complexity in the range between the first and last elements being spliced in (iterator2 and list2.end() in my example), and the source suggests that this is because of iterator advance. I can live with this but I had been hoping for constant complexity.

My assumption (before I found this source) was that the splice function do something like this:

1. Sever the link between "x" and "y"
2. Sever the link between "z" and list2.end()
3. Form a link between "x" and list2.end()
4. Sever the link between "a" and "b"
5. Form a link between "a" and "y"
6. Form a link between "y" and "b"

Thus restoring both lists to complete chains.

The same principle would then apply to lists of arbitrary size. I'm not sure I see where there is the need for the splice function to advance any iterators, since I am providing it with all the iterators it needs to do it's job.

So my question is, how does the C++ specification deal with this? Does it break and re-form the links only at the start and end points of the splice, or does it advance through each link one by one? If the latter, do any other list containers (e.g. from QT) provide the former? My code resides inside the inner loop of a simulation program, so giving it constant rather than linear complexity would be quite valuable.

Answer 1

This was a very contentious topic during the standardization of C++11. The problem is that all standard containers, including lists, also have a constant-time size operation.

Before C++11, many implementations made size linear time and splice between different lists constant time. C++11 now requires that size be constant and splice be linear.

The problem is that, if the length of the spliced range isn't counted one-by-one, then the containers cannot keep track of how many elements were removed and added, and the next call to size would need to recover this information in O(N) time — using the larger N of the entire sequence, not just the spliced part.

A non-standard list container can supply the desired operation, because so long as you don't need O(1) size, your argument is correct.

As for other libraries… I'm not aware of one, but Boost should have one. (I checked, it doesn't, so someone go get started!) Since you clearly understand how to write your own, doing so might be less effort than contending with such a large library as Qt.

If you don't need thread safety, you could implement a wrapper around std::list in which each container only owns a subrange of a singleton list. This would eliminate most of the programming effort in replicating the standard interface.