Нет операции 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)?

Ответ 1

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

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

Ответ 2

Позвольте мне сначала дать исправленную версию вашего алгоритма сплайсинга 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, нам нужно предоставить итератор до 1 перед end(). Однако такой итератор не существует в постоянное время. Таким образом, в основном линейные затраты возникают от обнаружения конечного итератора, так или иначе: либо вы предварительно компилируете его в O (n) времени, либо используете свой алгоритм, либо просто соединяетесь один за другим, также в линейном времени.

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

Ответ 3

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