c++ - splice_after 实现 forward_list

Question

其中forward_list有一个函数splice_after（供参考），具体来说，给出的链接中的函数#3。list考虑到单个链接，将如何实施。

作为一个练习，当我实现它时，我必须迭代列表直到我到达之前的节点first（以便我可以连接first到last），然后再次直到我到达之前的节点last（以便我可以将当​​前列表的节点连接到节点之前last）。这对我来说似乎效率不高，并且想知道是否有更好的方法可以在没有迭代的情况下做到这一点？

Answer 1

我怀疑你误读了有点微妙的范围规范，它说“（first，last）”被移动，而不是“[first，last）”（注意左括号/括号）。也就是说，顾名思义，拼接操作仅在第一个对象之后开始。

该函数的实现实际上非常简单（如果您忽略迭代器的常量性以及它可能需要处理不同的分配器的事实）：

void splice_after(const_iterator pos, forward_list& other,
                  const_iterator first, const_iterator last) {
    node* f = first._Node->_Next;
    node* p = f;
    while (p->_Next != last._Node) { // last is not included: find its predecessor
        p = p->_Next;
    }
    first._Node->Next = last._Node;  // remove nodes from this
    p->_Next = pos._Node->_Next;     // hook the tail of the other list onto last
    pos._Node->_Next = f;            // hook the spliced elements onto pos
}

该操作具有线性复杂度，因为它需要找到 的前身last。

Answer 2

（社区维基，请贡献）

 A -> B -> C -> D -> E
           ^
           ^ pos points to C

在other列表中

 U -> V -> W -> X -> Y -> Z
      ^              ^
      ^ first        ^ last

称呼.splice(pos, other, first, last)

我们要将 W 和 X 移到顶部列表中。即之间的一切，但不包括，first和last。最终A->B->C->W->X->D->E在顶部和U->V->Y->Z底部。

auto copy_of_first_next = first->next;
first->next = last;
// the `other` list has now been emptied

auto copy_of_pos_next = pos->next;
pos -> next = first;
while(first->next != last) ++first;
// `first` now points just before `last`
first->next = copy_of_pos_next