没有O(1)操作来连接两个forward_lists中的元素？

Question

当读取关于forward_list在C++ 11的FCD和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)这个简单数据结构的优势之一的两个单链表？因此我想知道 - 在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,您必须在相关操作期间保持更新.)

Answer 2

当您传入end()as时，您的算法会失败last，因为它将尝试使用最后一位节点并将其重新链接到另一个列表中。end()如果允许在除了这个算法之外的所有算法中使用，这将是一个奇怪的例外。

我也认为first.next = &last;需要，first.next = last.next;因为否则last将出现在两个列表中。