c++ - Splice_after执行forward_list

Question

在 forward_list 中有一个函数 splice_after ( for reference )，特别是给定链接中的函数 #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 的前导。