Нет операции O (1) для объединения элементов из двух forward_lists?

Когда вы читаете о forward_list в FCD из С++ 11 и N2543, я наткнулся на одну конкретную перегрузку splice_after (слегка упрощенное и пусть cit be const_iterator):

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

Поведение заключается в том, что после pos все между (first,last) перемещается на this. Таким образом:

  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

Описание включает в себя сложность:

Сложность: O (расстояние (первое, последнее))

Я вижу, что это потому, что нужно настроить PREDECESSOR(last).next = pos.next, а forward_list не позволяет это произойти в O (1).

Хорошо, но не присоединяется к двум односвязным спискам в O (1) одной из сильных сторон этой простой структуры данных? Поэтому мне интересно - нет операции на forward_list, которая связывает/объединяет/объединяет произвольное число элементов в O (1)?

Алгоритм был бы довольно простым, конечно. Нужно просто имя для операции (псевдокод): ( Обновлено, интегрируя ответ Kerreks)

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

Результат немного отличается, потому что не перемещается (first,last), а (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   

Я бы подумал, что это такая же разумная операция, как и первая, что люди хотели бы сделать - особенно если она имеет преимущество O (1).

• Я пропускаю операцию, которая является O (1) для многих элементов?
• Или мое предположение неверно, что (first,last] может быть полезным в качестве перемещенного диапазона?
• Или есть ошибка в алгоритме O (1)?

Ответы

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

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

    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