c++ - 没有 O(1) 操作来连接来自两个 forward_lists 的元素？

Question

在阅读 C++11 和 N2543 的 FCD 中的 forward_list 时我偶然发现了一个特定的 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

描述包括复杂性:

Complexity: O(distance(first, last))

我可以看到这是因为需要调整 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)算法有错误？

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 存储一个额外的迭代器，您必须在相关操作期间保持更新。)