No O(1) operation to join elements from two forward_lists?

Question

When reading about forward_list in the FCD of C++11 and N2543 I stumbled over one specific overload of splice_after (slightly simplified and let cit be const_iterator):

void splice_after(cit pos, forward_list<T>& x, cit first, cit last);

The behavior is that after pos everything between (first,last) is moved to this. Thus:

  this: 1 2 3 4 5 6           x: 11 12 13 14 15 16
          ^pos                      ^first   ^last
will become:
  this: 1 2 13 14 3 4 5 6     x: 11 12       15 16
          ^pos                      ^first   ^last

The description includes the complexity:

Complexity: O(distance(first, last))

I can see that this is because one needs to adjust PREDECESSOR(last).next = pos.next, and the forward_list does not allow this to happen in O(1).

Ok, but isn't joining two singly linked lists in O(1) one of the strengths of this simple data structure? Therefore I wonder -- is there no operation on forward_list that splices/merges/joins an arbitrary number of elements in O(1)?

The algorithm would be quite simple, of course. One would just need a name for the operation (pseudocode): (Updated by integrating Kerreks answer)

temp_this  =   pos.next;
temp_that  =  last.next;
  pos.next = first.next;
 last.next =  temp_this;
first.next =  temp_that;

The result is a bit different, because not (first,last) is moved, but (first,last].

  this: 1 2 3 4 5 6 7               x: 11 12 13 14 15 16 17
          ^pos                            ^first      ^last
will become:
  this: 1 2 13 14 15 16 3 4 5 6 7   x: 11 12             17
          ^pos       ^last                ^first   

I would think this is an as reasonable operation like the former one, that people might would like to do -- especially if it has the benefit of being O(1).

• Am I overlooking a operation that is O(1) on many elements?
• Or is my assumption wrong that (first,last] might be useful as the moved range?
• Or is there an error in the O(1) algorithm?

Answer 1

Let me first give a corrected version of your O(1) splicing algorithm, with an example:

temp_this  =   pos.next;
temp_that  =  last.next;

  pos.next = first.next;
 last.next =  temp_this;
first.next =  temp_that;

(A sanity check is to observe that every variable appears precisely twice, once set and once got.)

Example:

    pos.next                           last.next
    v                                  v
1 2 3 4 5 6 7        11 12 13 14 15 16 17 #    
  ^                     ^           ^     ^
  pos                   first       last  end             


becomes:

This:     1 2 13 14 15 16 3 4 5 6 7

That:   11 12             17

Now we see that in order to splice up to the end of that list, we need to provide an iterator to one before the end(). However, no such iterator exists in constant time. So basically the linear cost comes from discovering the final iterator, one way or another: Either you precompute it in O(n) time and use your algorithm, or you just splice one-by-one, also in linear time.

(Presumably you could implement your own singly-linked list that would store an additional iterator for before_end, which you'd have to keep updated during the relevant operations.)

Answer 2

There was considerable debate within the LWG over this issue. See LWG 897 for some of the documentation of this issue.