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

Question

Читая о forward_list в FCD C ++ 11 и N2543 , я наткнулся на одну конкретную перегрузку splice_after (слегка упрощенную и пусть cit будет 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) одну из сильных сторон этой простой структуры данных? Поэтому мне интересно - нет ли на * 1029 операции, которая склеивает / объединяет / объединяет произвольное количество элементов в 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)?

Answer 1

Позвольте мне сначала привести исправленную версию вашего алгоритма сращивания 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

Теперь мы видим, что для объединения до конца списка that нам нужно предоставить итератор для один перед end(). Однако такого постоянного итератора не существует. Таким образом, в основном линейные затраты возникают из-за обнаружения конечного итератора, так или иначе: либо вы предварительно вычисляете его за O (n) время и используете свой алгоритм, либо вы просто склеиваете по одному, также в линейном времени.

(Предположительно, вы могли бы реализовать свой собственный односвязный список, в котором будет храниться дополнительный итератор для before_end, который вы должны будете обновлять во время соответствующих операций.)

Answer 2

В LWG произошли серьезные споры по этому вопросу.См. LWG 897 для ознакомления с документацией по этой проблеме.

Answer 3

Ваш алгоритм завершается ошибкой, когда вы передаете end() как last, потому что он попытается использовать узел с одним последним концом и связать его с другим списком.Было бы странным исключением разрешить использование end() в каждом алгоритме, кроме этого.

Также я думаю, что first.next = &last; должно быть first.next = last.next;, так как иначе last будет в обоих списках.